Связный список и массив: в чём разница и что выбрать

Короткий ответ

По умолчанию берите массив (динамический массив: list в Python, Array в JavaScript). Он даёт быстрый доступ по индексу, быстрый обход и компактную память.

Связный список выбирайте, только когда главная операция — вставка или удаление в позиции, на которую у вас уже есть ссылка, а произвольный доступ нужен редко.

Как они лежат в памяти

• Массив — один непрерывный блок памяти. Элемент i находится по адресу start + i * size, адрес вычисляется мгновенно.
• Связный список — отдельные узлы, разбросанные по памяти. Каждый узел хранит значение и указатель на следующий (а в двусвязном списке — ещё и на предыдущий). Чтобы добраться до элемента i, нужно пройти i указателей от головы.

Динамический массив держит запас ёмкости. Когда место кончается, он выделяет блок побольше и копирует туда всё содержимое. Это происходит редко, поэтому добавление в конец стоит амортизированно O(1).

Сравнение по Big O

Главная деталь: O(1) у списка предполагает, что узел у вас уже есть. Если его сначала нужно найти по индексу или значению, проход стоит O(n), и преимущество исчезает.

Локальность кэша: почему массив выигрывает на практике

Процессор загружает память кусками — кэш-линиями. Когда вы читаете элемент массива, соседние элементы подтягиваются вместе с ним, и следующие чтения очень быстрые. Аппаратный prefetcher тоже хорошо угадывает последовательный доступ.

Узлы списка разбросаны, поэтому каждый шаг может промахнуться мимо кэша и ждать основную память. Из-за этого даже операции с одинаковым Big O, например обход всех элементов, на массиве часто работают заметно быстрее. Для небольших и средних коллекций сдвиг элементов массива нередко дешевле, чем переходы по указателям.

Оба варианта в коде

Массивы в Python и JavaScript — это сразу динамические массивы:

nums = [10, 20, 30]
nums.append(40)      # амортизированно O(1)
nums.insert(0, 5)    # O(n): все элементы сдвигаются вправо
print(nums[2])       # O(1)

Минимальный односвязный список на JavaScript:

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor() { this.head = null; }

  prepend(value) {            // O(1)
    this.head = new Node(value, this.head);
  }

  insertAfter(node, value) {  // O(1), если узел уже есть
    node.next = new Node(value, node.next);
  }

  *[Symbol.iterator]() {
    for (let n = this.head; n; n = n.next) yield n.value;
  }
}

const list = new LinkedList();
list.prepend(3);
list.prepend(1);
list.insertAfter(list.head, 2);
console.log([...list]); // [1, 2, 3]

Когда связный список действительно выигрывает

• LRU-кэш. Хеш-таблица указывает на узлы двусвязного списка. При каждом обращении узел переносится в начало за O(1), самый старый удаляется с хвоста за O(1).
• Очереди и деки с частыми добавлениями с обоих концов. collections.deque в Python построен из связанных блоков именно поэтому. Удаление из начала обычного массива — O(n).
• Перенос фрагментов. Переместить целую цепочку элементов в другой список — это несколько изменений указателей, без копирования.
• Стабильные ссылки. Узлы не перемещаются в памяти, указатели на них остаются валидными. Динамический массив при росте переезжает.
• Списки свободных блоков в аллокаторах и ядрах ОС, где узлы встроены в сами объекты.

Частые ошибки

• Выбрать список «потому что вставка O(1)», а потом вставлять по индексу — это всё равно O(n).
• Использовать array.shift() или list.pop(0) как очередь на больших данных — для этого есть deque и очереди.
• Забыть про накладные расходы: каждый узел несёт указатели и служебные данные аллокатора.
• Писать свой список, когда в стандартной библиотеке уже есть подходящая структура.