Python 列表的底层数据结构是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/914233/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the underlying data structure for Python lists?
提问by Nixuz
What is the typical underlying data structure used to implement Python's built-in list data type?
用于实现 Python 内置列表数据类型的典型底层数据结构是什么？
采纳答案by e1i45
List objects are implemented as arrays. They are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
列表对象被实现为数组。它们针对快速固定长度操作进行了优化，并且会为 pop(0) 和 insert(0, v) 操作带来 O(n) 内存移动成本，这会改变底层数据表示的大小和位置。
See also: http://docs.python.org/library/collections.html#collections.deque
另见：http: //docs.python.org/library/collections.html#collections.deque
Btw, I find it interesting that the Python tutorial on data structures recommends using pop(0) to simulate a queue but does not mention O(n) or the deque option.
顺便说一句，我觉得有趣的是，关于数据结构的 Python 教程推荐使用 pop(0) 来模拟队列，但没有提到 O(n) 或 deque 选项。
http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues
http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues
回答by Georg Sch?lly
CPython:
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;
As can be seen on the following line, the list is declared as an array of pointers to PyObjects.
从下一行可以看出，该列表被声明为指向 的指针数组PyObjects。
PyObject **ob_item;
回答by nategood
In the Jython implementation, it's an ArrayList<PyObject>.
在Jython 实现中，它是一个ArrayList<PyObject>.
