29

从标签维基摘录：

链表是一种数据结构，其中元素包含对下一个（也可以是前一个）元素的引用。链表在任何位置提供 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 符号吗？

4

4 回答 4

21

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

总结：

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

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

于 2013-03-31T17:40:27.267 回答
5

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

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

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

于 2013-03-31T17:35:16.143 回答
4

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

没有魔法;)

于 2013-03-31T17:42:35.127 回答
2

你引用的wiki页面说：

O(1) 在任意位置插入和移除

然后你问：

读到这个我很惊讶——列表如何插入随机索引

这里存在混淆：术语位置和索引没有被用来表示相同的东西。wiki 讨论的是迭代器或指针，而不是索引。

于 2013-03-31T17:42:36.510 回答