linked-list - 为什么在链表中间插入是O(1)？

Question

根据Wikipedia article on linked lists ，在链表中间插入被认为是 O(1)。我认为这将是 O(n)。您是否不需要找到可能靠近列表末尾的节点？

此分析是否没有考虑节点操作的查找(尽管这是必需的)以及插入本身？

编辑:

Linked lists have several advantages over arrays. Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in an array may require moving half of the elements, or more.

上面的说法对我来说有点误导。如果我错了请纠正我，但我认为结论应该是:

数组:

• 查找插入/删除点 O(1)
• 执行插入/删除 O(n)

链接列表:

• 找到插入/删除点 O(n)
• 执行插入/删除 O(1)

我认为唯一不需要找到位置的情况是如果您保留某种指向它的指针(在某些情况下与头部和尾部一样)。因此，我们不能断然地说链表在插入/删除选项方面总是优于数组。

Answer 1

您是对的，本文将“索引”视为单独的操作。所以插入本身是 O(1)，但到达中间节点是 O(n)。