为什么Python没有一个本地链表实现?

I have tried some quick experiment comparing the performance of native Python lists with linked lists implementations such as this.

我尝试了一些快速的实验，将本机Python列表的性能与类似这样的链表实现进行比较。

The native python lists are always faster than the non native linked list in the cases where they should not be (according the theory).

在不应该出现的情况下，本地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

The results I have on the test above are:

我在上面测试的结果是:

• native linked list = 2.00000000001e-05

  本地链接列表= 2.00000000001e-05。

• python list = 0.005576

  python列表= 0.005576

• non native linked list = 3.90000000001e-05

  非本地链表= 3.90000000001e-05

So, I was wondering why Python don't have a native Linked List data structure. In the case of Python, it looks to me that it could be useful algorithmically speaking to have Linked List instead of the standard Lists to speed up some aspects of the standard library.

所以，我想知道为什么Python没有一个本地链表数据结构。在Python的例子中，我认为使用链表而不是标准列表来加速标准库的某些方面是有用的。

My understanding is that the List data structure is a key building block of the language and that it makes the code more maintainable and easily optimizable to focus on that very data structure.

我的理解是，列表数据结构是语言的一个关键构建块，它使代码更易于维护，更易于优化，以专注于数据结构。

Is there any other reason?

还有其他原因吗?

2 个解决方案

#1

Python has collections.deque which is a native doubly-linked list.

Python有collections.deque，它是一个本地的doubly链表。

#2

It's just because building list takes majority of the time rather than append method. So, when it's not a linear time operation as you showed, (ex : n^2 operation) append method will be more significant than building which will lead to the result you want to see.

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