LinkedList 的 add(int, E) 的 O(1) 复杂度如何？

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) 时间的情况，当然不是常数时间。

我错过了什么？我误解了大 O 符号吗？

原文由 wchargin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

好吧，它们确实支持在任意位置进行恒定时间插入——但 前提是 您碰巧有一个指向列表条目的指针，您希望在其之后或之前插入一些内容。当然，如果您只有索引，这将不起作用，但这不是您通常在优化代码中所做的。

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

链表的这个特性是它们与数组列表等相比的最大优势——例如，如果你想从聊天室的用户列表中删除一个用户，你可以在用户中存储一个指向该用户在用户列表中的位置的指针，以便，当他想离开房间时，可以实现为 O(1) 操作。

原文由 thejh 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是因为您正在阅读的文章将“获取该索引”视为单独的操作。本文假定您已经在要执行 add(int, E) 的索引处。

总结：

插入或删除操作 = O(1)

在第 n个索引处查找节点 = O(n)

原文由 Thanakron Tandavas 发布，翻译遵循 CC BY-SA 3.0 许可协议