Коротко: в подавляющем большинстве практических задач предпочтительнее динамический массив (std::vector, ArrayList). Ниже — почему и когда именно.
Время выполнения (асимптотика)
- Случайный доступ: вектор — $O(1)$ (по индексу), связный список — $O(n)$.
- Добавление в конец: вектор — амортизированно $O(1)$ (при увеличении ёмкости, напр., удвоении), связный список — $O(1)$ при наличии указателя на хвост, но без кеш-выгоды.
- Вставка/удаление в середине при известном указателе/итераторе: связный список — $O(1)$, вектор — $O(n)$ (сдвиг элементов).
- Поиск по значению: вектор и список — $O(n)$ (но вектор обычно быстрее на константе).
- Суммарная стоимость ресайзов (при факторе роста $c>1$): копирование суммарно даёт амортизированную стоимость вставки $O(1)$ (например, при удвоении суммарная копия ≈ $2n$, поэтому средняя стоимость на элемент постоянна).
Локальность памяти и практическая скорость
- Вектор хранит данные подряд — отличная локальность, кэш-дружелюбность, возможность векторизации и быстрой memcpy/memmove. Это даёт большую практическую скорость при переборах, сортировках и массовых операциях.
- Связный список хранит узлы в разрозненных областях памяти — много промахов кэша, плохая предсказуемость, тяжело векторизуется. На практике даже при тех же асимптотиках операции обычно медленнее.
Память
- Для элемента размера $s$ и указателя размером $p$: узел двусвязного списка занимает примерно $s+2p$ (плюс выравнивание и заголовки аллокатора). Для мелких $s$ (например, $s=4$, $p=8$) накладные расходы значительны.
- Вектор использует $s\times$ capacity плюс небольшой служебный оверхед; накладных указателей нет.
Итераторы и стабильность адресов
- Вектор: при перераспределении все указатели/итераторы/ссылки становятся невалидными; можно избежать, используя reserve.
- Список: адреса узлов стабильны после вставки (пока узел не удалён), что удобно, если храните постоянные ссылки на элементы.
Практические сценарии, где выбирать вектор
- Нужен быстрый случайный доступ (индексация).
- Частые последовательные переборы, сортировки, агрегирование, SIMD/массовые операции.
- Стек/динамический массив/буфер — push_back/pop_back.
- Малые элементы и ограниченная память (меньшая накладная память).
- Использование стандартных алгоритмов, требующих random-access итераторов (std::sort, бинарный поиск).
Когда лучше связный список
- Чаще делаете частые вставки/удаления в середине и у вас уже есть указатель/итератор на позицию, и важна стабильность адресов.
- Нужны операции splice (перемещение подсписков) в $O(1)$.
- Реализация специфичных структур (например, intrusive list) или некоторых concurrent/lock-free решений.
Резюме
- Выбирайте динамический массив по умолчанию: он быстрее на практике благодаря локальности и низкой памяти, поддерживает $O(1)$ доступ и амортизированное $O(1)$ добавление в конец.
- Используйте связный список только при явной необходимости в $O(1)$-вставках/удалениях по известному указателю, splice‑операциях или когда стабильность адресов элементов критична.