为什么Python没有本地链接列表实现？

Question

我曾尝试一些简单的实验机Python列表的性能链表实现,如比较本.

本机python列表总是比非本机链表更快(根据理论).

from linkedlist import *
import time
a = LinkedList()
b = []
for i in range(1000000):
    b.append(i)
    a.add_first(i)
t0 = time.clock()
a.remove(10)
t1 = time.clock()
b.remove(10)
t2 = time.clock()
print t1-t0
print t2-t1

我在上面的测试中得到的结果是:

• 原生链表= 2.00000000001e-05

• python list = 0.005576

• 非本地链表= 3.90000000001e-05

所以,我想知道为什么Python没有原生的Linked List数据结构.在Python的情况下,它在我看来,从算法来讲,使用Linked List而不是标准列表来加速标准库的某些方面可能是有用的.

我的理解是List数据结构是该语言的一个关键构建块,它使代码更易于维护,并且易于优化以专注于该数据结构.

还有其他原因吗？

Answer 1

Python有collections.deque,这是一个原生的双向链表.

Answer 2

事实上，Python 没有原生链表实现，我也很想知道为什么。

\n\n

您可能需要考虑的一种替代方案是collections.deque(=“双端队列”)，它在两端提供非常快速的恒定时间 O(1) 插入。事实上，对于您的具体示例，双端队列是比链表更好的选择，因为您不需要在中间插入。

\n\n

然而，一般来说，重要的是要记住，双端队列是与​​链表不同的数据结构。链表还提供常数时间 O(1) 的中间插入，而双端队列仅提供线性时间 O(n) 的中间插入。换句话说，在双端队列中间插入一个元素所花费的时间与双端队列当前的长度n成正比，并且对于足够大的n，它会比链表慢。

\n\n

collections.deque 和真正的链表之间的比较

\n\n

在内部，collections.deque实际上是使用链表实现的。然而，这是一个实现细节，更重要的是，它被实现为固定大小的元素块的链表，而不是单个元素的链表。

\n\n

这就是为什么在 collections.deque 中间插入是 O(n) 而不是 O(1)：您仍然需要修改整个双端队列的大约一半内存以容纳新元素 N：

\n\n

before inserting N: [ABCDE]\xe2\x87\x84[FGHIJ]\xe2\x87\x84[KLM__]\nafter inserting N:  [ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLM_]\nchanged memory:                ^^^   ^^^^\n

\n\n

相反，对于真正的链表（=单个元素），在中间插入一个新元素 N 只需分配一个新节点并更新四个指针的值，该操作的性能与当前元素的大小无关。链接列表：

\n\n

before inserting N: [A]\xe2\x87\x84[B]\xe2\x87\x84[C]\xe2\x87\x84[D]\xe2\x87\x84[E]\xe2\x87\x84[F]\xe2\x87\x84[G]\xe2\x87\x84    [H]\xe2\x87\x84[I]\xe2\x87\x84[J]\xe2\x87\x84[K]\xe2\x87\x84[L]\xe2\x87\x84[M]\nafter inserting N:  [A]\xe2\x87\x84[B]\xe2\x87\x84[C]\xe2\x87\x84[D]\xe2\x87\x84[E]\xe2\x87\x84[F]\xe2\x87\x84[G]\xe2\x87\x84[N]\xe2\x87\x84[H]\xe2\x87\x84[I]\xe2\x87\x84[J]\xe2\x87\x84[K]\xe2\x87\x84[L]\xe2\x87\x84[M]\nchanged memory:                                ^ ^ ^                           \n

\n\n

权衡是双端队列具有更好的内存局部性并且需要更少的独立内存分配。例如，在上面的双端队列中插入新元素 N 根本不需要任何新的内存分配。这就是为什么在实践中，特别是如果您经常在末端而不是中间插入，双端队列实际上是比链表更好的选择。

\n\n

请注意，在双端队列中间插入元素的时间复杂度为 O(n)，而在开头或末尾插入新元素的时间复杂度为 O(1)：

\n\n

before:                [ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLM_]\n\nprepending P:  [____P]\xe2\x87\x84[ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLM_]\n                    ^ ^\n\nprepending Q:  [___QP]\xe2\x87\x84[ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLM_]\n                   ^\n\nappending R:   [___QP]\xe2\x87\x84[ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLMR]\n                                            ^\n\nappending S:   [___QP]\xe2\x87\x84[ABCDE]\xe2\x87\x84[FGNHI]\xe2\x87\x84[JKLMR]\xe2\x87\x84[S____]\n                                              ^ ^\n

\n\n

注意事项

\n\n

当然，对于链表插入实际上是 O(1)，这假设您已经拥有要在h其之前或之后插入新节点的节点的句柄n。在 LinkedList 的假设实现中，这可能如下所示：

\n\n

n = linkedlist.insertbefore(h, "some value")\n

\n\n

在哪里：

\n\n

type(h)     # => <class \'Node\'>\ntype(n)     # => <class \'Node\'>\nn.value     # => "some value"\nn.next == h # => True\n

\n\n

如果没有这样的句柄，那么像这样的函数insert(i, x)仍然是 O(n)，因为查找第 i 个元素是 O(n)，即使插入操作本身是 O(1)。insert(i, x)以下是我们假设的 LinkedList 上的一些假设实现：

\n\n

def insert(self, i, x):\n    node = self.node_from_index(i)       # Find the i-th node: O(n)\n    return self.insertbefore(node, x)    # Insert and return new node: O(1)\n

\n\n

这意味着只有当您保留这些节点句柄时，链表才值得用于某些问题。它还使 API 不太方便，尽管如果你小心的话，每个操作都是 O(1)，但常数通常要大得多。因此在实践中，它们并不经常有用，这可能就是为什么它们不是 Python 中的内置链表的原因。

\n