根据文档，

Python的列表实际上是变长数组，而不是lisp风格的链表。

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，但是主列表已经改变了。那意味着列表没有赋值为一个复制列表赋值为它的引用。

正如上面其他人所述，列表(当相当大时)是通过分配固定数量的空间来实现的，如果该空间应该被填满，则分配更大数量的空间并复制元素。

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)

实际上，C代码非常简单。扩展一个宏并删除一些不相关的注释，基本结构在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包含引用计数和类型标识符。这是一个过度分配的向量/数组。当数组满时，调整数组大小的代码在listobject.c中。它实际上并没有使数组加倍，而是通过分配来增长

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

到每次的容量，其中newsize是请求的大小(不一定分配+ 1，因为您可以扩展任意数量的元素，而不是逐个添加它们)。

参见Python常见问题解答。

在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使用链表，我会感到震惊——它们会破坏许多广泛使用的库的性能，这些库建立在链表是动态数组的假设之上。