LinkedList的O（1）复杂度的add（int，E）如何？

Question

从链接列表标签Wiki摘录：

链表是一种数据结构，其中的元素包含对下一个（以及可选的上一个）元素的引用。链接列表可 在任何位置 提供 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<E>方法只是指针的重新分配，但是还有entry(int)方法：

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

即使进行了一半大小的优化，for这里的循环（一个或另一个）对我来说似乎都是死胡同，这种方法（因此add(int, E)）在O（n）时间的最小最坏情况下运行，并且肯定不是恒定的时间。

我想念什么？我是否误解了big-O表示法？

Answer 1

好的，它们确实支持在任意位置进行固定时间插入-但 前提是
您碰巧有一个指向列表条目的指针，您想在列表条目之后或之前插入某个条目。当然，如果只有索引，这将无法正常工作，但这不是您通常在html" target="_blank">优化代码中执行的操作。

在Java中，您也可以这样做，但只能使用列表迭代器。

相较于数组列表，链表的此属性是它们的最大优点–例如，如果要从聊天室的用户列表中删除用户，则可以将指向用户位置的指针存储在用户的用户列表中，以便，当他想离开房间时，可以将其实现为一项O(1)操作。