¿Cuál es la estructura de datos subyacente para las listas de Python?

Question

¿Cuál es la estructura de datos subyacente típica utilizada para implementar el tipo de datos de lista integrado de Python?

Answer 1

Los objetos de lista se implementan como matrices . Están optimizados para operaciones de longitud fija e incurren O (n) costos de movimiento de memoria para pop (0) y operaciones de inserción (0, v) que cambian tanto el tamaño como la posición de la representación de datos subyacente .

Consulte también: http://docs.python.org/library/collections.html#collections.deque

Por cierto, me parece interesante que el tutorial de Python en las estructuras de datos recomienda el uso de pop (0) para simular una cola, pero no menciona O (n) o la opció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; 

Como puede verse en la línea siguiente, la lista se declara como una matriz de punteros a PyObjects.

PyObject **ob_item; 

Answer 3

En el Jython implementation, es una ArrayList<PyObject>.