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

Question

我尝试过一些快速实验，将本地Python的性能与链接列表实现(如this )进行比较。

在不应该使用本机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.000000001e-05
• python = 0.005576
• 非本机链表= 3.90000000001e-05

因此，我想知道为什么Python没有本地链接列表数据结构。在Python的例子中，从算法上讲，使用链接列表而不是标准列表来加速标准库的某些方面可能是有用的。

我的理解是，列表数据结构是该语言的一个关键构建块，它使代码更易于维护，并且更容易优化，以便将精力集中在该数据结构上。

还有别的原因吗？

Answer 1

实际上，Python没有本机链接列表实现，我也想知道原因。

您可能需要考虑的一种选择是collections.deque (=“双端队列”)，它在两端提供非常快的固定时间O(1)插入。事实上，对于特定的例子来说，deque比链接列表更好的选择，因为您不需要插入中间。

但是，总的来说，重要的是要记住，deque是一个与链接列表不同的数据结构。链表还提供中间的固定时间O(1)插入，而deque只在中间提供线性时间O(n)插入。换句话说，在deque中间插入元素所需的时间与deque的当前长度n成正比，对于足够大的n，它将比链表慢。

collections.deque与真链表的比较

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

这就是为什么在collections.deque中间插入的是O(n)而不是O(1)：您仍然需要修改整个内存的一半左右才能容纳新元素N：

before inserting N: [ABCDE]⇄[FGHIJ]⇄[KLM__]
after inserting N:  [ABCDE]⇄[FGNHI]⇄[JKLM_]
changed memory:                ^^^   ^^^^

相反，对于真正的链接列表(=单个元素)，在中间插入一个新元素N只需分配一个新节点和更新四个指针的值，这是一个性能独立于链接列表当前大小的操作：

before inserting N: [A]⇄[B]⇄[C]⇄[D]⇄[E]⇄[F]⇄[G]⇄    [H]⇄[I]⇄[J]⇄[K]⇄[L]⇄[M]
after inserting N:  [A]⇄[B]⇄[C]⇄[D]⇄[E]⇄[F]⇄[G]⇄[N]⇄[H]⇄[I]⇄[J]⇄[K]⇄[L]⇄[M]
changed memory:                                ^ ^ ^                           

折衷之处在于，deque具有更好的内存局部性，并且需要较少的独立内存分配。例如，在上面的deque中插入新元素N根本不需要任何新的内存分配。这就是为什么在实践中，尤其是当你经常在结尾而不是中间插入时，一个deque实际上是一个比一个链接列表更好的选择。

注意，在deque中间插入元素是O(n)，在开头或结尾插入新元素是O(1)：

before:                [ABCDE]⇄[FGNHI]⇄[JKLM_]

prepending P:  [____P]⇄[ABCDE]⇄[FGNHI]⇄[JKLM_]
                    ^ ^

prepending Q:  [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLM_]
                   ^

appending R:   [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLMR]
                                            ^

appending S:   [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLMR]⇄[S____]
                                              ^ ^

注意事项

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

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

其中：

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

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

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

这意味着，只有当您将这些节点句柄保持在某个特定的问题时，链接列表才有价值。它还使API变得不那么方便，尽管每个操作都是O(1)，如果您仔细的话，则常量通常要大得多。因此，在实践中，它们并不经常有用，这可能就是为什么它们不是Python中内置的链接列表的原因。

Answer 2

这只是因为构建列表占用了大部分时间，而不是附加方法。因此，当它不是一个线性时间操作时，(ex : n^2操作)追加方法将比构建方法更重要，这将导致您想要看到的结果。