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

Question

来自 linked-list标签维基摘录:

A linked list is a data structure in which the elements contain references to the next (and optionally the previous) element. Linked lists offer O(1) insert and removal at any position, O(1) list concatenation, and O(1) access at the front (and optionally back) positions as well as O(1) next element access. Random access has O(N) complexity and is usually unimplemented.

^{(强调我的)}

我很惊讶地读到这个 ​​- 列表插入 的随机索引比简单地读取那个索引的复杂度要低吗？

所以我查看了 the source code for java.util.LinkedList . add(int, E) method是:

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

addBefore(E, Entry<E> method只是指针重新分配，但还有 entry(int) method :

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 符号吗？

Answer 1

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

总结:

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

在第 n^th 索引处找到节点 = O(n)