Python的列表是如何实现的？

Question

Python的列表是如何实现的？

是链表还是数组？我四处搜寻，只发现有人在猜测。我的C知识还不够好，不能看源代码。

Answer 1

是个动态阵列..实际证明：索引使用(当然，与极小的差异(0.0013！)同时，无论索引是什么：...>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使用链接列表(它们会破坏许多被广泛使用的库的性能)，我会感到惊讶，因为它们假设列表是动态数组。

Answer 2

实际上，C代码非常简单。扩展一个宏并删除一些不相关的注释，基本结构在listobject.h，它将列表定义为：typedef&nbsp;struct&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;PyObject_HEAD &nbsp;&nbsp;&nbsp;&nbsp;Py_ssize_t&nbsp;ob_size; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Vector&nbsp;of&nbsp;pointers&nbsp;to&nbsp;list&nbsp;elements.&nbsp;&nbsp;list[0]&nbsp;is&nbsp;ob_item[0],&nbsp;etc.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;PyObject&nbsp;**ob_item; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;ob_item&nbsp;contains&nbsp;space&nbsp;for&nbsp;'allocated'&nbsp;elements.&nbsp;&nbsp;The&nbsp;number &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;currently&nbsp;in&nbsp;use&nbsp;is&nbsp;ob_size. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Invariants: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;<=&nbsp;ob_size&nbsp;<=&nbsp;allocated &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;len(list)&nbsp;==&nbsp;ob_size &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ob_item&nbsp;==&nbsp;NULL&nbsp;implies&nbsp;ob_size&nbsp;==&nbsp;allocated&nbsp;==&nbsp;0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;Py_ssize_t&nbsp;allocated;}&nbsp;PyListObject;PyObject_HEAD包含引用计数和类型标识符。因此，它是一个过分配的向量/数组。当数组满时调整大小的代码在listobject.c..它实际上并不是数组的两倍，而是通过分配new_allocated&nbsp;=&nbsp;(newsize&nbsp;>>&nbsp;3)&nbsp;+&nbsp;(newsize&nbsp;<&nbsp;9&nbsp;?&nbsp;3&nbsp;:&nbsp;6);new_allocated&nbsp;+=&nbsp;newsize;每一次，newsize请求的大小(不一定)allocated + 1因为你可以extend由任意数目的元素代替append一个接一个地给他们看)。另见Python常见问题.

Answer 3

在CPython中，列表是指针数组。Python的其他实现可以选择以不同的方式存储它们。