LinkedList如何添加（int，E）O（1）复杂度？
从链表标签维基摘录：
链表是一种数据结构，其中元素包含对下一个（以及可选的前一个）元素的引用。 链接列表提供在任何位置的O（1）插入和移除 ，O（1）列表串联，以及前（和可选后）位置的O（1）访问以及下一元素访问的O（1）。 随机访问具有O（N）复杂性并且通常是未实现的。
（强调我的）
我很惊讶地读到这一点 – 如何将列表插入一个复杂度低于简单读取索引的随机索引？
所以我查看了java.util.LinkedList的源代码 。 add(int, E)方法是：
public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); }
addBefore(E, Entry方法只是指针重新分配，但也有entry(int)方法 ：
if (index = size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry e = header; if (index > 1)) { for (int i = 0; i index; i--) e = e.previous; } return e; }
即使是半尺寸优化，这里的for循环（一个或另一个）在我看来是一个死的赠品，这个方法（因此add(int, E) ）在O（n的最小最坏情况下）运行）时间，当然不是恒定的时间。
我错过了什么？ 我是否误解了大O符号？
好吧，它们确实支持在任意位置进行常量插入 – 但前提是你碰巧有一个指向列表条目的指针，之后或者在其前面插入一些东西。 当然，如果你只有索引，这将不起作用，但这不是你通常在优化代码中做的。
在Java中，您也可以这样做，但只使用列表迭代器 。
与arraylists相比，链接列表的这一属性是它们的最大优势 – 例如，如果要从聊天室的用户列表中删除用户，可以在用户列表中存储指向用户位置的指针，以便，当他想要离开房间时，可以实现为O(1)操作。
这是因为您正在阅读的文章将“转到该索引”视为单独的操作。 本文假设您已经在要执行的索引add（int，E）。
总结：
插入或删除操作= O（1）
在第 n 个索引处查找节点= O（n）
将新节点链接到任何节点的操作是O（1），但查找 （有助于循环）相关索引的操作肯定是O（n）。
没有魔力;）
你引用的wiki页面说：
O（1）在任何位置插入和移除
然后你问：
我很惊讶地看到这个 – 如何在随机索引中插入列表
这就是混乱：术语位置和索引并不是用来表示相同的东西。 wiki讨论迭代器或指针，而不是索引。