К какой структуре данных относится список?

#python

Списки в Python, какая это структура данных — массив или список?
    

Ответы

Ответ 1

На самом деле вопрос хороший, т.к. реализация списка может быть через список (хранение
node и ссылок между ними) или через динамический массив. А от этого может зависеть
поведение кода при работе с этой структурой.

Список реализуется через массив: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython

А согласно этому ответу можно посмотреть реализацию списка в стандартной реализации
интерпретатора:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* 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
     */
    Py_ssize_t allocated;
} PyListObject;


Как видно, это реализация через массив.



PS.

Согласно, этому ответу, следующие реализации интерпретатора используют массив как
реализацию списка:


CPython использует массив
Jython использует массив через реализацию списка ArrayList
IronPython тоже использует массив.