Конспект: массив и связный список

Понятия

Массив - элементы непрерывным куском памяти, одного размера. Адрес i-го = начало + i · размер, поэтому индексация O(1). Плата за непрерывность - сдвиг: вставка/удаление в середине O(n). Статический массив фиксированного размера.

Динамический массив - массив, который при заполнении выделяет вдвое больший буфер и копирует старое. Это list в Python. append амортизированно O(1) (доказано в прошлом разделе), индексация O(1), сдвиг середины O(n) - как у обычного массива.

Узел - элемент связного списка: значение плюс ссылка(и) на соседний узел.

Связный список - элементы узлами вразброс по памяти, порядок держат ссылки. Индексация/поиск O(n) (проход от головы), вставка/удаление на месте O(1) (перецепка ссылок). Профиль зеркален массиву.

Двусвязный список - у узла ссылка и на следующего, и на предыдущего: дёшев шаг назад и удаление узла по прямой ссылке, ценой лишней ссылки в каждом узле.

Локальность памяти - процессор читает память блоками; плотный массив он грузит пачками, разбросанные узлы списка - нет. Влияет на множитель, не на порядок роста.

Что унести

Массив и связный список - две реализации одного АТД «последовательность» с зеркальными профилями:

Выбор - по профилю: каких операций больше, там и смотри, где они дёшевы. Много индексации и проходов - массив; много правок не с края по известному месту - список. Поиск по значению O(n) у обоих, в выборе не помогает.

Поправка на локальность: плотная память бьёт разбросанную. Оттого структура по умолчанию - динамический массив; связный список прячут внутрь дек и очередей. «Выгоднее по асимптотике» ≠ «быстрее на практике».

У массива дёшев конец и дорого начало/середина. Нужен обратный порядок - не вставляй в начало поэлементно (insert(0, x) даёт Θ(n²)), а копи в конец append-ом и переверни разом (Θ(n)). Пользуйся структурой в её сильных операциях.

Ловушки джокера

Выбрал по привычке, а не по профилю. «Лучше вообще» не бывает: массив и список зеркальны, каждый силён там, где другой слаб.

Правишь массив не с конца в цикле. insert(0, x) или pop(0) в цикле - сдвиг хвоста на каждом шаге, Θ(n²).

Лазишь по связному списку индексом. list[i] в цикле - проход i шагов каждый раз, Θ(n²). По списку ходят одним подрядным проходом.

Взял список ради «дешёвых вставок», забыв про локальность. На реальных данных плотный массив часто обгоняет список даже там, где тот асимптотически не хуже.

Спутал разовое копирование при удвоении с ценой индексации. Удвоение меняет цену только append (амортизированно O(1)); индексация O(1) всегда.

Проверь себя

Почему индексация массива O(1), а вставка в середину O(n)?

Почему у связного списка всё наоборот - индексация O(n), вставка на месте O(1)?

Чем двусвязный список отличается от односвязного и за что платит?

Как выбирать между массивом и списком - и при чём тут локальность памяти?

Почему обратный порядок дешевле собрать через append + reverse, а не вставками в начало?