Предлагаю вашему вниманию статью, основанную на публикации Laurent Luce о реализации работы со списками в CPython. Она может быть полезна начинающим программистам на Python, либо готовящимся к собеседованию. Функции C показаны в сокращенном варианте и с моими комментариями. Полный текст функций можно найти в исходниках CPython 2.7.

Эта статья описывает реализацию объекта списка в CPython, наиболее популярной реализации Python. Списки в Python — это мощный инструмент, и интересно узнать, как они устроены внутри. Взгляните на простой скрипт, который добавляет несколько целых значений в список и выводит их:

>>> l = []
>>> l.append(1)
>>> l.append(2)
>>> l.append(3)
>>> l
[1, 2, 3]
>>> for e in l:
...   print e
...
1
2
3

Как вы можете видеть, список является итерируемым объектом.

C-структура объекта списка

Объект списка в CPython представлен нижеследующей структурой в C. ob_item — это список указателей на элементы списка, allocated — количество выделенной памяти.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Инициализация списка

Давайте посмотрим, что происходит при создании пустого списка, к примеру l = []. Вызывается функция PyList_New(0):

/* 
size - размер списка
*/
PyList_New(Py_ssize_t size)
{
    // Вычисляется реальный размер необходимой памяти
    nbytes = size * sizeof(PyObject *);

    // Инициализируется ob_item
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        memset(op->ob_item, 0, nbytes);
    }

    // Сохраняется количество выделенных ячеек
    op->allocated = size;

    return (PyObject *) op;
}

Важно понимать разницу между выделенной памятью и размером списка. Размер списка — это тоже самое, что и len(l). allocated — это количество выделенной памяти, которое зачастую может быть больше размера списка. Это делается для предотвращения вызовов realloc при каждом добавлении элементов. Мы разберемся в этом подробнее чуть позже.

Добавление элементов

Мы добавляем целое число в список: l.append(1). Что в этот момент происходит? Вызывается функция C PyList_Append(), которая, в свою очередь, вызывает функцию app1():

/*
self - указатель на объект списка
v - указатель на добавляемое значение
*/
app1(PyListObject *self, PyObject *v)
{
    // Если не удалось изменить размер списка, возвращаем ошибку - значение (-1)
    if (list_resize(self, n+1) == -1)
        return -1;

    // После изменения размера списка, устанавливаем значение элемента n в v
    PyList_SET_ITEM(self, n, v);
    
    // При успешном выполнении возвращаем 0
    return 0;
}

Давайте посмотрим на функцию list_resize(). Она выделяет больше памяти, чем нужно для предотвращения частых вызовов list_resize. Выделение памяти задается следующей последовательностью: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

/*
self - указатель на объект списка
newsize - новый размер списка
*/
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    // Если выделенной ранее памяти достаточно для заданного размера - дополнительной памяти не выделяем
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* В противном случае выделяем необходимую память, а также резервируем 
     * дополнительную для следующих увеличений списка
     */
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* Проверяем на переполнение */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    // Выделяем память
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);

    return 0;
}

4 ячейки сейчас выделено для элементов списка и первый из них — это целое число 1. На изображении вы можете увидеть, что l[0] указывает на целое число, которое мы добавили в список. Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память.

Операция добавления элемента в список имеет сложность O(1).



Добавим еще один элемент в список: l.append(2). list_resize вызывается с n+1 = 2, но, так как размер выделенной памяти 4, нет необходимости выделять дополнительную память. То же самое происходить при добавлении еще двух целых чисел: l.append(3), l.append(4). На картинке показано, что мы имеем в итоге:

Вставка

Вставим новое целое число в позицию 1: l.insert(1,5) и посмотрим, что будет происходить на низком уровне. Вызывается функция ins1():

/*
self - указатель на объект списка
where - позиция, в которую вставляется новый элемент
v - указатель на вставляемое значение
*/
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    n = Py_SIZE(self);

    // Изменяем размер списка и возвращаем ошибку в случае неудачи
    if (list_resize(self, n+1) == -1)
        return -1;

    // Если позиция отрицательна, то считаем с конца списка
    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    // Если позиция больше длины списка, то вставляем в конец
    if (where > n)
        where = n;

    // Сдвигаем значения списка от конца до вставляемого элемента
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    // Вставляем новый элемент
    items[where] = v;

    return 0;
}

Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память. Итак, 8 ячеек выделено, но размер списка у нас сейчас 5.

Сложность операции вставки O(n).

Выталкивание

Когда вы выталкиваете элемент из списка, l.pop(), вызывается listpop(). list_resize вызывается внутри listpop() и в случае, если новый размер меньше половины выделенной памяти — то список сжимается.

/*
self - указатель на объект списка
args - параметры, указывающие на выталкиваемый элемент
*/
listpop(PyListObject *self, PyObject *args)
{
    // По умолчанию выталкиваем последний элемент
    Py_ssize_t i = -1;

    // Если список пуст - возвращаем NULL
    if (Py_SIZE(self) == 0) {
        return NULL;
    }

    // Если индекс отрицательный - считаем с конца
    if (i < 0)
        i += Py_SIZE(self);

    v = self->ob_item[i];
    // Если выталкивается последний элемент - вызывает list_resize и возвращаем вытолкнутое значение
    if (i == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        return v; 
    }

    // Если выталкивается элемент из внутренности списка, вызываем специальную функцию для изменения списка
    status = list_ass_slice(self, i, i+1, (PyObject *)NULL);

    return v;
}

Сложность операции O(1).



Вы можете наблюдать, что 4 ячейка все еще указывает на целое, но важно понимать, что размер списка у нас 4.

Вытолкнем еще один элемент. В list_resize(), size-1 = 4-1 = 3 меньше чем половина выделенных ячеек, поэтому список сжимается до 6 ячеек и новый размер списка становится 3.

Вы можете наблюдать, что 3 и 4 ячейка все еще указывают на целое, но важно понимать, что размер списка у нас 3.

Удаление

В Python объект списка имеет метод для удаления элемента с заданным значением: l.remove(5). Вызывается listremove().

/*
self - указатель на объект списка
v - указатель на удаляемое значение
*/
listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;

    // Пробегаемся по списку
    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);

        // Если нашли подходящее значение - удаляем его и возвращаем Python None
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }

    // Если не нашли элемент - возвращаем NULL
    return NULL;
}

Сложность операции удаления — O(n).