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

Answer 1

这是因为你正在阅读的文章将“到达该索引”视为单独的操作。文章假定你已经在执行add(int, E)时所需的索引上。

总之：

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

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

- Thanakron Tandavas

---

根据这个答案 https://dev59.com/SXbZa4cB1Zd3GeqPHpgz#18679284，找到第n个节点的时间复杂度是O(1)。我还不确定哪一个答案是正确的 :| - João Matos

@JoãoMatos，那个特定的答案是回答一个有关 addLast() 方法复杂度的问题。由于 Java 的 LinkedList 是双向链表并维护对第一个和最后一个元素的指针，addLast() 的时间复杂度是 O(1)。在任意索引位置查找节点仍然是 O(n)。 - harperska

Answer 2

他们支持在任意位置进行常数时间插入 - 但是仅当你恰好拥有一个指向要在其之后或之前插入内容的列表条目的指针时才能实现。当然，如果你只有索引，那么这种方法是行不通的，但这通常不是优化代码中的做法。

在Java中，您也可以使用列表迭代器来实现此操作，但仅限于使用列表迭代器。

与ArrayList等相比，链表的最大优点就是这个属性 - 例如，如果你想从聊天室的用户列表中删除一个用户，你可以在用户中存储指向用户列表中该用户位置的指针，这样，当他想离开房间时，就可以将其实现为O(1)操作。

- thejh

---

换句话说，LinkedList<E>.add(int, E) 的时间复杂度不是 O(1)，但 ListIterator<E>.add 是（对于来自 LinkedList 的迭代器而言）。 - sepp2k

Answer 3

将新节点链接到任何节点的操作是O(1)，但寻找（帮助循环）所关注的索引的操作肯定是O(n)。

没有什么魔法;)

- Mik378

Answer 4

你引用的维基页面说：

O(1)在任何位置插入和删除

然后你问：

我很惊讶地读到这个 - 这个列表如何在随机索引处插入

混淆之处在于，术语“位置”和“索引”并不是用来表示同一件事情。维基谈论的是迭代器或指针，而不是索引。

- NPE

---

虽然 position 有点模糊...而 "insert ... at" 暗示了索引解释。我建议编辑标签 wiki 来澄清，你觉得怎么样？ - thejh

@thejh：我个人认为这很清楚。然而，考虑到至少有一个人觉得它令人困惑，我不认为澄清会有什么坏处。 - NPE

Answer 5

对于那些通过谷歌搜索并想知道add(index, elem)的完整答案的人。

答案是：

finding element + insert
    O(index)    +  O(1)

这不是 O(n) + O(1)，因为你只迭代到索引而不是列表的所有元素。

希望这可以帮助。

- Anna Klein