在Java中，为什么链表中的插入或删除是一个常数时间操作？这不是误导吗？
假设我们已经有一个指向该节点的指针，则在列表的特定点插入或删除元素是一个常数时间操作。 - 来自有关链接列表的维基百科文章
单个链表中的链表遍历总是从头部开始。我们必须继续前进，直到满足给定的条件。
因此，除非我们处理的是头节点，否则任何操作的最坏情况都将是 O(n)。
我们不能直接访问链表中的给定指针。那么为什么说是常数时间操作呢？
编辑： 即使我们有一个指向节点的指针，我们也只能从头开始，对吗？那么它是如何实现恒定时间运行的呢
Insertion or deletion of an element at a specific point of a list, assuming that we have a pointer to the node already, is a constant-time operation.
- from the Wikipedia Article on Linked list
Linked list traversal in a single linked list always starts from the head. We have to keep going till we satisfy a given condition.
So that will make any operation worst case O(n) unless we are dealing with the head node.
We CANNOT DIRECTLY go to a given pointer in a linked list. So why is it said that it is a constant time operation?
EDIT:
Even if we have a pointer to the node, we have to start from the head only right? So how is it constant time operation
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
首先：Sun JDK 中实现的
LinkedList有效地具有到最后一个元素以及第一个元素的链接（只有一个head条目，但是head.previous指向最后一个元素）。这意味着即使在最坏的情况下，通过列表导航到索引指示的元素也应该需要 n/2 次操作。它也是一个双向链表。除此之外：插入到
LinkedList的开头或结尾的时间复杂度仅为 O(1)，因为您不需要遍历所有元素。在其他任何地方插入/删除取决于您的具体操作方式！如果您使用
Iterator（用于添加的ListIterator），然后操作也可以是 O(1) ，因为Iterator将已经拥有对相关条目的引用。但是，如果您使用
add(int, E)或删除(int)，那么LinkedList将必须找到相关条目（O(n)）并然后删除该元素（O(1)） ，所以整个操作将是 O(n)。First of: the
LinkedListimplemented in the Sun JDK effectively has a link to the last element as well as to the first element (there's only aheadentry, buthead.previouspoints to the last element). This means that even in the worst case navigating through a list to an element indicated by an index should take n/2 operations. It's also a doubly linked list.Apart from that: inserting into the beginning or end of a
LinkedListis trivially O(1), because you don't need to traverse all elements.Inserting/removing anywhere else depends on how exactly you do it! If you use an
Iterator(of aListIteratorfor adding) then the operation can be O(1) as well, as theIteratorwill already have a reference to relevant entry.If, however, you are using
add(int, E)orremove(int), then theLinkedListwill have to find the relevant entry (O(n)) and then remove the element (O(1)), so the entire operation will be O(n).您自己说过：“假设我们已经有一个指向该节点的指针”。这避免了您认为导致线性时间的遍历。
诚然，维基百科文本有点含糊，因为涉及两个节点：一个正在插入，另一个在列表中插入。
You said it yourself: "assuming we have a pointer to the node already". That avoids the traversal you identify as the cause of the linear time.
Admittedly, the Wikipedia text is a bit ambiguous, since there are two nodes involved: the one being inserted, and the one in the list where to insert it.
“假设我们已经有一个指向节点的指针，这是一个恒定时间操作”
您似乎错过了第一个假设。
" assuming that we have a pointer to the node already, is a constant-time operation"
You missed the first assumption, it seems.
你没有抓住我认为的重点。只是插入和删除的时间是恒定的，而不是找到插入或删除的点！
时间是恒定的，因为您只需设置对列表中的上一个和下一个项目的引用（链接） - 而对于 ArrayList 来说，在插入的情况下，您需要为（至少）另外一个项目分配内存并将现有数据传输到新分配的数组中（或者通过删除，一旦删除了该项目，您就必须移动数组中的元素）。
You are missing the point I think here. It is just the INSERTION and DELETION that have a constant time not the finding the point of insertion or deletion as well!
The time is constant because you simply need to set the references (links) to the previous and next item in the list -- whereas for instance with ArrayList, in the case of insertion you need to allocate memory for (at least) one more item and transfer the existing data into the newly allocated array (or with deletion you have to shift elements in the array around once you deleted the item).