Массив или список: выбор по операциям

Коротко

Массив и связный список - две реализации одного абстрактного типа «последовательность» с ЗЕРКАЛЬНЫМИ профилями. Массив: доступ по индексу O(1), вставка/удаление в середине O(n). Список: доступ O(n), вставка/удаление на месте O(1). Выбор - по тому, каких операций у тебя БОЛЬШЕ. Но у таблицы порядков роста есть скрытая поправка: массив лежит в памяти плотно, процессор грузит его пачками, поэтому на практике динамический массив обгоняет связный список даже там, где асимптотика вроде бы за список. Список берут, когда вставок/удалений не с края действительно много и место известно заранее.

Если ты выбираешь между массивом и связным списком по профилю нужных операций и знаешь про поправку на локальность памяти (почему массив часто быстрее, чем обещает асимптотика), листай до «Теперь сам».

Как думаешь, какая структура «лучше» - массив или список

Вопрос поставлен неверно, и это главный урок главы. «Лучше» само по себе не бывает: массив и связный список - зеркальные, каждый силён ровно там, где другой слаб. Массив мгновенно берёт i-й, но дорого правит середину; список дёшево правит на месте, но медленно ищет i-й. Правильный вопрос - не «какая лучше вообще», а «каких операций БОЛЬШЕ в моей задаче». Ответ на него и выбирает структуру.

На что это похоже

Две сумки. Рюкзак с одним отделением: вещи лежат плотно, любую видно сразу сверху - но чтобы достать нижнюю, надо вынуть всё над ней. Органайзер с кучей кармашков: добавить или вынуть вещь из своего кармашка мгновенно, но чтобы найти нужную, приходится обшарить кармашки по очереди. Что удобнее - зависит не от сумки, а от того, что ты делаешь чаще: достаёшь по месту или перекладываешь. Так и со структурами: выбор диктует не сама структура, а профиль твоих действий.

Механизм: сравнить профили и посчитать, чего больше

Положи два профиля рядом.

операция	массив (динамический)	связный список
взять/поставить `i`-й	`O(1)`	`O(n)`
добавить в конец	`O(1)` аморт.	`O(1)`
вставить/удалить в начале	`O(n)`	`O(1)`
вставить/удалить на месте (узел известен)	`O(n)`	`O(1)`
найти по значению	`O(n)`	`O(n)`
память на элемент	только значение	значение + ссылка(и)

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

Правило

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

Разбор: поправка на локальность памяти

Таблица порядков роста не всё говорит. Массив лежит непрерывным куском, и процессор читает память не по одному байту, а блоками (кеш-линиями): взяв a[i], он заодно подтягивает соседей a[i+1], a[i+2] - и следующий шаг прохода уже готов, без обращения к медленной памяти. У связного списка узлы разбросаны, каждый «следующий» - прыжок в непредсказуемое место, и процессор ждёт память заново. На проходе по миллиону элементов эта разница даёт МАССИВУ фору в разы, хотя по асимптотике проход у обоих O(n). Поэтому на практике list (динамический массив) - разумный выбор по умолчанию, а связный список достают, когда его O(1)-правки на месте реально перевешивают. Асимптотика говорит про порядок роста, а не про множитель - а локальность прячется именно в множителе.

Разбор: когда список всё-таки выигрывает

Пример, где связный список на месте. Тебе нужна структура, из которой часто выдёргивают элементы из СЕРЕДИНЫ по уже имеющейся ссылке (скажем, список активных задач, и у тебя на руках прямая ссылка на задачу, которую надо убрать). В массиве каждое такое удаление - сдвиг хвоста O(n), серия из n удалений - O(n²). В двусвязном списке удаление по известной ссылке - перецепка O(1), серия - O(n). Обрати внимание на условие «по известной ссылке»: список выигрывает не потому, что он «гибче», а потому, что здесь нет ни индексации, ни поиска места - только правка на месте, а это ровно его сильная сторона. Убери условие (пусть место надо искать по индексу) - и преимущество испарится: проход O(n) съест выгоду.

Что ломается без этого

Первая ошибка - выбирать структуру «по привычке» или по вере, что одна «вообще лучше». Лучше бывает только под ПРОФИЛЬ операций. Вторая - верить одной асимптотике и брать связный список ради «дешёвых вставок», забыв про локальность: на реальных данных массив с его плотной укладкой часто обгоняет список даже на операциях, где список асимптотически не хуже. Третья - взять связный список ради O(1)-вставки, но всё равно лазить в него по индексу: list[i] в цикле превращает мнимую экономию в O(n²). Структуру надо не только выбрать, но и ПОЛЬЗОВАТЬСЯ ей в её сильных операциях.

Зачем это в работе

Именно поэтому в большинстве языков структура последовательности по умолчанию - это динамический массив (list, ArrayList, vector), а не связный список: он покрывает самый частый профиль (доступ по индексу, проход, добавление в конец) и выигрывает за счёт локальности. Связный список прячут внутрь специализированных структур - деки (deque), очередей, - где нужны дешёвые операции с концов или удаление по ссылке. Инженерное умение здесь двойное: прочитать профиль своей задачи по таблице И помнить, что на реальном железе плотная память бьёт разбросанную, поэтому «по асимптотике выгоднее» не всегда значит «на практике быстрее».

Теперь сам

Ты пишешь структуру, где будет ОЧЕНЬ много обращений a[i] по случайным индексам и проходов подряд, а вставки - только в конец. Массив или связный список? А если бы, наоборот, обращений по индексу не было вовсе, зато шли постоянные удаления из середины по готовой ссылке?

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

Главное

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