Какова основная структура данных для списков Python?

Question

Какова типичная базовая структура данных, используемая для реализации встроенного в список типов данных Python?

Answer 1

Объекты списка реализованы как массивы. Они оптимизированы для быстрых операций с фиксированной длиной и несут O (n) затраты на перемещение памяти для pop (0) и Вставка (0, v) операций, которые меняют как размер, так и местоположение основного представления данных .

Смотрите также: http://docs.python.org/library/collections.html#collections.deque

Btw, я нахожу интересным, что учебник Python на структуры данных рекомендует использовать поп (0) для имитации очереди, но не говоря уже о (п) или дека вариант ,

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 implementation, что это ArrayList<PyObject>.