LinkedList如何添加(int,E)O(1)复杂度？

Question

从链表标签维基摘录:

链表是一种数据结构,其中元素包含对下一个(以及可选的前一个)元素的引用.链接列表提供在任何位置的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符号？

Answer 1

这是因为您正在阅读的文章将"转到该索引"视为单独的操作.本文假设您已经在要执行的索引add(int,E).

总结:

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

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

Answer 2

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

\n\n

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

\n\n

链表的这个属性是它们相对于数组列表的最大优势，例如\xe2\x80\x93，如果你想从聊天室的用户列表中删除一个用户，你可以存储一个指向该用户位置的指针在用户的用户列表中，以便当他想要离开房间时，可以将其作为O(1)操作来实现。

\n