在Java中，为什么在链接列表中插入或删除是一个恒定时间操作？ 这不是误导吗？

在列表的特定点插入或删除元素，假设我们已经有一个指向节点的指针，是一个恒定时间操作。 – 来自维基百科关于链接列表的文章

单个链表中的链接列表遍历始终从头开始。 我们必须继续前进，直到我们满足特定条件。

因此，除非我们处理头节点，否则这将使任何操作最坏情况为O（n）。

我们无法直接转到链表中的给定指针。 那为什么说它是一个恒定的时间操作？

编辑：即使我们有一个指向节点的指针，我们必须从头开始才对吗？ 那么如何恒定运行呢？

Answer 1

第一个：在Sun JDK中实现的LinkedList实际上有一个指向最后一个元素以及第一个元素的链接（只有一个head目，但head.previous指向最后一个元素）。 这意味着即使在最坏的情况下，通过列表导航到索引指示的元素也应该进行n / 2次操作。 它也是一个双重链表。

除此之外：插入到LinkedList的开头或结尾通常是O（1），因为您不需要遍历所有元素。

在其他任何地方插入/移除取决于您的具体操作方式！ 如果使用Iterator （ ListIterator的Iterator进行添加），那么操作也可以是O（1），因为Iterator已经有相关条目的引用。

但是，如果你使用add(int, E)或remove(int) ，那么LinkedList必须找到相关的条目（O（n）） 然后删除元素（O（1）），所以整个操作将是O（n）。

Answer 2

你自己说：“假设我们已经有一个指向节点的指针”。 这可以避免您认为是线性时间原因的遍历。

不可否认，维基百科的文本有点含糊不清，因为涉及两个节点：一个被插入，另一个插入列表。

Answer 3

“假设我们已经有一个指向节点的指针，那就是一个恒定时间操作”

看来你错过了第一个假设。

Answer 4

你错过了我在这里想到的观点。 只是INSERTION和DELETION有一个恒定的时间，而不是找到插入或删除的点！ 时间是恒定的，因为您只需要将引用（链接）设置为列表中的上一个和下一个项目 – 而例如使用ArrayList，在插入的情况下，您需要为（至少）一个项目分配内存并将现有数据传输到新分配的数组中（或删除后，您必须在删除项目后移动数组中的元素）。