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

Массив хранит элементы в непрерывном блоке памяти и даёт доступ по индексу за O(1), а связный список — цепочка узлов с указателями, где вставка и удаление по известному узлу стоят O(1), но доступ по индексу — O(n).

Сравнение операций

• Доступ по индексу: массив O(1), список O(n).
• Вставка и удаление в начало: массив O(n) из-за сдвига, список O(1).
• Вставка в конец: массив амортизированно O(1), список O(1) при хранении указателя на хвост.

Память и кеш процессора

• Массив компактен и дружелюбен к кешу: элементы лежат рядом, prefetch работает.
• Узел списка хранит лишний указатель и разбросан по куче: промахи кеша и больше памяти на элемент.

Когда список оправдан

Частые вставки и удаления по уже имеющемуся итератору на узел (как внутри LRU-кеша) либо когда нельзя перевыделять большой непрерывный блок памяти.

Коротко для собеседования

Массив выигрывает почти всегда: доступ по индексу за O(1) и плотное размещение, которое любит кеш процессора. Список берут, когда нужно много вставок и удалений по уже известному узлу, как в LRU-кеше; в остальных случаях его асимптотические плюсы съедаются промахами кеша.