它是链表还是数组?我四处搜寻，只发现人们在猜测。我的C语言知识还不够好，不能看源代码。
当前回答
在CPython中，list是作为动态数组实现的，因此当我们追加时，不仅添加了一个宏，而且分配了更多的空间，这样每次都不应该添加新的空间。
其他回答
它是一个动态数组。实践证明:无论索引如何，索引都需要相同的时间(当然差异非常小(0.0013µs !)):
...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop
...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop
如果IronPython或Jython使用链表，我会感到震惊——它们会破坏许多广泛使用的库的性能，这些库建立在链表是动态数组的假设之上。
在CPython中，列表是指针的数组。Python的其他实现可以选择以不同的方式存储它们。
我发现这篇文章对于理解如何使用python代码实现列表非常有帮助。
class OhMyList:
def __init__(self):
self.length = 0
self.capacity = 8
self.array = (self.capacity * ctypes.py_object)()
def append(self, item):
if self.length == self.capacity:
self._resize(self.capacity*2)
self.array[self.length] = item
self.length += 1
def _resize(self, new_cap):
new_arr = (new_cap * ctypes.py_object)()
for idx in range(self.length):
new_arr[idx] = self.array[idx]
self.array = new_arr
self.capacity = new_cap
def __len__(self):
return self.length
def __getitem__(self, idx):
return self.array[idx]
根据文档，
Python的列表实际上是变长数组，而不是lisp风格的链表。
正如上面其他人所述，列表(当相当大时)是通过分配固定数量的空间来实现的，如果该空间应该被填满，则分配更大数量的空间并复制元素。
To understand why the method is O(1) amortized, without loss of generality, assume we have inserted a = 2^n elements, and we now have to double our table to 2^(n+1) size. That means we're currently doing 2^(n+1) operations. Last copy, we did 2^n operations. Before that we did 2^(n-1)... all the way down to 8,4,2,1. Now, if we add these up, we get 1 + 2 + 4 + 8 + ... + 2^(n+1) = 2^(n+2) - 1 < 4*2^n = O(2^n) = O(a) total insertions (i.e. O(1) amortized time). Also, it should be noted that if the table allows deletions the table shrinking has to be done at a different factor (e.g 3x)
