Was ist die zugrunde liegende Datenstruktur für Python-Listen?

Question

Welche typische Datenstruktur wird verwendet, um den integrierten Listendatentyp von Python zu implementieren?

Answer 1

Listenobjekte sind als Arrays implementiert. Sie sind für schnelle Operationen mit fester Länge optimiert und verursachen O (n) Speicherbewegungskosten für pop (0) und Operationen (0, v), die sowohl die Größe als auch die Position der zugrunde liegenden Datendarstellung ändern.

Siehe auch: http://docs.python.org/library/collections.html#collections.deque

Btw, ich finde es interessant, dass die Python-Tutorial auf Datenstrukturen empfehlen Pop mit (0) einer Warteschlange zu simulieren, aber nicht O (n) oder die deque Option erwähnen .

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; 

Wie in der folgenden Zeile zu sehen ist, wird die Liste als ein Array von Zeigern auf PyObjects erklärt.

PyObject **ob_item; 

Answer 3

Im Jython implementation, es ist ein ArrayList<PyObject>.