240

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

4

9 回答 9

288

实际上，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 常见问题解答。

于 2010-10-18T10:39:40.133 回答
73

这是一个动态数组。实际证明：无论索引如何，索引都需要（当然差异极小（0.0013 µsecs！））相同的时间：

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

于 2010-10-12T18:04:10.837 回答
54

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

列表对象 C 结构

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

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).在此处输入图像描述

于 2017-07-20T10:50:05.363 回答
45

这取决于实现，但 IIRC：

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

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

于 2010-10-12T17:59:29.740 回答
40

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

于 2010-10-12T18:00:23.480 回答
26

According to the documentation,

Python’s lists are really variable-length arrays, not Lisp-style linked lists.

于 2012-06-01T15:07:33.230 回答
5

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

为了理解为什么该方法是 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 倍）进行表收缩

于 2013-10-22T03:00:45.573 回答
2

Python 中的列表类似于数组，您可以在其中存储多个值。List 是可变的，这意味着您可以更改它。您应该知道的更重要的事情是，当我们创建一个列表时，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，但我们的主列表已更改。那意味着的列表没有分配为副本列表分配为其参考。

于 2019-08-20T12:36:15.723 回答
-2

在 CPython 中，列表是作为动态数组实现的，因此当我们追加时，不仅添加了一个宏，而且分配了更多空间，因此每次都不应添加新空间。

于 2020-03-19T14:31:24.407 回答