Python 列表的底层数据结构是什么？

小开

CPython:

typedef struct {
PyObject_VAR_HEAD
/* 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
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;

如下面一行所示，该列表被声明为指向 PyObjects的指针数组。

PyObject **ob_item;

小开

在 Jython 实现里，是 ArrayList<PyObject>。

小开

最佳答案

列表对象实现为数组。它们是为快速而优化的固定长度的操作，产生 O (n) 弹出(0)和插入(0，v)更改的操作的大小和位置基础数据表示法。

参见: Http://docs.python.org/library/collections.html#collections.deque

顺便说一句，我发现 Python 数据结构教程建议使用 pop (0)来模拟队列，但是没有提到 O (n)或 deque 选项，这很有趣。

Http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

小开

尽管这可能是显而易见的，但值得指出的是 Python 列表是 Dynamic数组(而不是 Static数组)。这是在求职面试问题/学术界出现的一个重要区别。

因为数组是动态的，Python 在声明时会保留大量的内存，例如:

somelist = []

因为已经预留了额外的内存，所以执行 somelist.append()只是写到下一个保留内存槽，因此大部分时间是 O(1)。对于静态数组，数组通常是满的(即。如果有4个字节，那么数组大小为4) ，并且附加将始终是 O(n)，因为它们需要保留一组全新的内存(现在可能是5个字节)并将内容复制过来。

小开

该列表是 python 中的一个内置数据结构。但是可以用来创建用户定义的数据结构。由列表创建的两个主要用户定义数据结构是堆栈和队列。