Python的List是如何实现的？

Question

是链表还是数组？我环顾四周，只发现人们在猜测。我的C知识还不够好，无法看源代码。

Answer 1

实际上，C 代码非常简单。扩展一个宏，修剪掉一些不相关的注释，基本结构在 < code>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 是请求的大小（不一定是 allocated + 1 因为您可以 >扩展任意数量的元素，而不是逐个追加它们）。

另请参阅 Python 常见问题解答 。

Answer 2

我建议Laurent Luce 的文章“Python 列表实现”。对我来说真的很有用，因为作者解释了如何在 CPython 中实现该列表，并为此使用了优秀的图表。

列出对象C结构

CPython 中的列表对象由以下 C 结构表示。 ob_item 是指向列表元素的指针列表。 allocate 是内存中分配的槽数。

typedef 结构 {
    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) 并看看内部发生了什么。

...

流行

当弹出最后一个元素时：l.pop()，将调用listpop()。 list_resize 在 listpop() 内部调用，如果新大小小于分配大小的一半，则列表将缩小。

您可以观察到插槽 4 仍然指向整数，但重要的是列表的大小现在为 4。
让我们再弹出一个元素。在 list_resize() 中，size – 1 = 4 – 1 = 3 小于已分配插槽的一半，因此列表缩小为 6 个插槽，列表的新大小现在为 3。

您可以观察到插槽 3 和 4 仍然指向一些整数，但重要的是列表的大小现在为 3。

...

删除
Python 列表对象有一个删除特定元素的方法：l.remove(5)。

Answer 3

这是一个动态数组。实际证明：无论索引如何，索引都需要相同的时间（当然差异极小（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 4

这取决于实现，但 IIRC：

• CPython 使用指针数组
• Jython 使用 ArrayList
• IronPython 显然也使用数组。您可以浏览源代码来找出答案。

因此它们都具有 O(1) 随机访问。

Answer 5

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

Answer 6

根据文档,

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

Answer 7

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

为了理解为什么该方法是 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 = O(2^n) = O(a) 总插入次数（即 O(1) 摊销时间）。另外，应该注意的是，如果表允许删除，则必须以不同的因子（例如 3x）进行表收缩

Answer 8

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 但我们的主列表已更改。这意味着列表没有指定为复制列表指定为其参考。

Answer 9

我发现这篇文章对于理解如何使用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]