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

什么是用于实现Python的内置列表数据types的典型底层数据结构？

Answer 1

列表对象被实现为数组。 它们针对快速固定长度操作进行了优化，并为pop（0）和insert（0，v）操作带来了改变底层数据表示大小和位置的O（n）内存移动成本。

另见： http : //docs.python.org/library/collections.html#collections.deque

顺便说一下，我觉得有趣的是，数据结构的Python教程build议使用pop（0）来模拟队列，但不提O（n）或deque选项。

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

Answer 2

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; 

Answer 3

在Jython实现中 ，它是一个ArrayList<PyObject> 。