What is the basic data structure for Python lists?

Question

What is the typical underlying data structure used to implement Python's built-in list of data types?

Answer 1

List objects are implemented as arrays. They are optimized for fast fixed-length operations and bear the O (n) cost of moving memory for pop (0) and insert (0, v) operations that change both the size and position of the underlying data representation.

See also: http://docs.python.org/library/collections.html#collections.deque

Btw, I'm curious that the Python data structures tutorial recommends using pop (0) to simulate a queue, but does not mention O (n) or the deque option.

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; 

As the next line shows, the list is declared as an array of pointers to PyObjects .

 PyObject **ob_item; 

Answer 3

In the Jython implementation , this is an ArrayList<PyObject> .