Списки против массивов: когда что использовать

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

Операция	Массив/Срез	Связный список
Доступ по индексу	`O(1)`	`O(n)`
Поиск	`O(n)`	`O(n)`
Вставка в начало	`O(n)`	`O(1)`
Вставка в конец	`O(1)` амор.	`O(1)` (с tail)
Вставка в середину	`O(n)`	`O(1)` *
Удаление из начала	`O(n)`	`O(1)`
Удаление из середины	`O(n)`	`O(1)` *
Память на элемент	1 слово	2–3 слова (+ ptr)
Кэш-дружественность	✓ высокая	✗ низкая

* при наличии указателя на узел

Кэш и производительность

Массивы — непрерывная область памяти. Процессор загружает соседние элементы в кэш-линию (64 байта). Связный список — узлы разбросаны по heap, каждый переход по next — потенциальный cache miss.

На практике для n < 1000 массив быстрее списка даже для вставок в начало из-за кэш-эффекта.

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

✓ Частые вставки/удаления в середину при наличии указателя
✓ Размер неизвестен, данные не нужны по индексу
✓ Реализация очередей и деков (container/list)
✓ LRU-кэш (список + map)

✗ Случайный доступ по индексу
✗ Числовые вычисления и сортировка
✗ Небольшие наборы данных

LRU-кэш как пример

Классическая комбинация: двусвязный список (порядок использования) + map (быстрый доступ):

type LRU[K comparable, V any] struct {
    cap   int
    list  *list.List
    index map[K]*list.Element
}

func (c *LRU[K, V]) Get(key K) (V, bool) {
    if e, ok := c.index[key]; ok {
        c.list.MoveToFront(e)
        return e.Value.(*entry[K, V]).val, true
    }
    var zero V
    return zero, false
}

Упражнения

№	Задание	Сложность
1	Упражнение 1	easy
2	Упражнение 2	easy
3	Упражнение 3	medium
4	Упражнение 4	medium