它是链表还是数组?我四处搜寻,只发现人们在猜测。我的C语言知识还不够好,不能看源代码。
当前回答
根据文档,
Python的列表实际上是变长数组,而不是lisp风格的链表。
其他回答
我发现这篇文章对于理解如何使用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中的列表类似于数组,可以存储多个值。列表是可变的,这意味着你可以改变它。你应该知道的更重要的事情是,当我们创建一个列表时,Python会自动为该列表变量创建一个reference_id。如果你通过分配其他变量来改变它,主列表也会改变。让我们举个例子:
list_one = [1,2,3,4]
my_list = list_one
#my_list: [1,2,3,4]
my_list.append("new")
#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']
我们添加了my_list,但是主列表已经改变了。那意味着列表没有赋值为一个复制列表赋值为它的引用。
根据文档,
Python的列表实际上是变长数组,而不是lisp风格的链表。
它是一个动态数组。实践证明:无论索引如何,索引都需要相同的时间(当然差异非常小(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的其他实现可以选择以不同的方式存储它们。