Python的列表是如何实现的？
它是一个链表，一个数组？ 我四处搜寻，只发现有人猜测。 我的C知识不足以查看源代码。
这是一个数组。 实践certificate：无论索引如何，索引都需要（当然，差异极小（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使用链表，我会感到震惊的 – 它们会毁掉许多被广泛使用的库的性能，这些库被build立在列表是数组的假设上。
C代码其实很简单。 扩展一个macros并修剪一些不相关的注释，基本结构在listobject.h ，它定义了一个列表：
typedef struct { PyObject_HEAD Py_ssize_t ob_size; /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* ob_item contains space for 'allocated' elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 */ Py_ssize_t allocated; } PyListObject;
PyObject_HEAD包含引用计数和types标识符。 所以，这是一个向量/数组。 当这个数组已满时resize的代码在listobject.c 。 它实际上并不是将数组加倍，而是通过分配来增长
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); new_allocated += newsize;
到newsize是请求的大小（不一定allocated + 1因为你可以extend任意数量的元素，而不是一个接一个地append ）。
另请参阅Python FAQ 。
在CPython中，列表是指针数组。 Python的其他实现可能会select以不同的方式存储它们。
这与实施有关，但是IIRC：
- CPython使用一个指针数组
- Jython使用一个
ArrayList - IronPython显然也使用一个数组。 你可以浏览源代码找出来。
因此，他们都有O（1）随机访问。
根据文件 ，
Python的列表实际上是可变长度的数组，而不是Lisp风格的链表。
正如其他人上面所说的那样，通过分配一定数量的空间来实施清单（当相当大时），并且如果该空间应该填满，则分配更大的空间并复制这些内容。
要理解为什么该方法是O（1）摊销，而不失一般性，假设我们插入了a = 2 ^ n个元素，现在我们必须将表格加倍到2 ^（n + 1）的大小。 这意味着我们正在进行2 ^（n + 1）的操作。 最后一个副本，我们做了2 ^ n个操作。 在此之前，我们做了2 ^（n-1）…一路下降到8,4,2,1。 现在，如果我们把它们相加，我们得到1 + 2 + 4 + 8 + … + 2 ^（n + 1）= 2 ^（n + 2） – 1 <4 * 2 ^ n = n）= O（a）总插入（即O（1）摊销时间）。 另外，应该注意的是，如果表允许删除，则表的缩小必须以不同的因子（例如3x）来完成，
我会build议Laurent Luce的文章“Python列表实现” 。 对我来说真的很有用，因为作者解释了如何在CPython中实现该列表，并为此使用了出色的图表。
列出对象C的结构
CPython中的列表对象由以下C结构表示。 ob_item是列表元素的指针列表。 分配的是在内存中分配的插槽数量。
typedef struct {
PyObject_VAR_HEAD
PyObject ** ob_item;
分配了Py_ssize_t;
} PyListObject;
注意分配的插槽和列表的大小之间的差异是很重要的。 列表的大小与len（l）相同。 分配的插槽数量是在内存中分配的数量。 通常情况下，你会看到分配的可能大于大小。 这是为了避免每次将新元素附加到列表时需要调用realloc。
…
附加
我们将一个整数添加到列表中：l.append（1）。 怎么了？
我们继续添加一个元素：l.append（2）。 list_resize被调用n + 1 = 2，但因为分配的大小是4，所以不需要分配更多的内存。 同样的事情发生时，我们再添加2个整数：l.append（3），l.append（4）。 下图显示了我们到目前为止。
…
插
让我们在位置1插入一个新的整数（5）：l.insert（1,5），看看内部发生了什么。
…
stream行的
当你popup最后一个元素时：l.pop（），listpop（）被调用。 在listpop（）中调用list_resize，如果新的大小小于分配大小的一半，那么这个列表就会被收缩。
你可以观察到slot 4仍然指向整数，但是重要的是现在的list 4的大小。让我们再popup一个元素。 在list_resize（）中，size-1 = 4-1 = 3小于已分配槽的一半，所以列表缩小到6个槽，新的大小现在是3。
你可以观察到，槽3和4仍然指向一些整数，但重要的是现在是3的列表的大小。
…
删除 Python列表对象有一个方法来删除特定的元素：l.remove（5）。
