Python 的 List 是如何实现的？-IT科技

摘要：问题描述：它是链表还是数组？我搜索了一下，发现人们只是在猜测。我的 C 知识还不够好，无法查看源代码。解决方案 1：实际上，C 代码非常简单。展开一个宏并删除一些不相关的注释，基本结构如下listobject.h，它将列表定义为：typedef struct { PyObject_HEAD P...

问题描述：

它是链表还是数组？我搜索了一下，发现人们只是在猜测。我的 C 知识还不够好，无法查看源代码。

解决方案 1：

实际上，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是请求的大小（不一定allocated + 1，因为您可以extend通过任意数量的元素而不是append逐个地'输入它们）。

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

解决方案 2：

我建议阅读Laurent Luce 的文章“Python 列表实现”。这篇文章对我非常有用，因为作者解释了如何在 CPython 中实现列表，并为此使用了出色的图表。

列表对象 C 结构
CPython 中的列表对象由以下 C 结构表示。ob_item是指向列表元素的指针列表。allocated 是在内存中分配的插槽数。
typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} 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)。

解决方案 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 使用链接列表，我会感到震惊 - 它们会破坏许多基于列表是动态数组的假设而构建的广泛使用的库的性能。

解决方案 4：

这取决于实现，但IIRC：

CPython 使用指针数组
Jython 使用ArrayList
IronPython 显然也使用数组。你可以浏览源代码来了解。

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

解决方案 5：

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

解决方案 6：

根据文献，

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

解决方案 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)）。此外，应该注意的是，如果表允许删除，则必须以不同的倍数（例如 3 倍）缩小表

解决方案 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，但主列表已更改。这意味着列表未指定为其引用的副本列表。

解决方案 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]