Связный список против массива: вагоны поезда или ряд в кинотеатре

Массив хранит элементы рядом и по номерам; связный список — россыпью, связанной стрелочками.

Массив силён там, где список слаб, и наоборот. Вопрос не «что лучше», а «что вы будете делать чаще — читать или менять середину».

Массив: ряд в кинотеатре

Массив — это участок памяти, где элементы лежат подряд, плечом к плечу, как пронумерованные кресла в ряду. Знаете номер места — подходите прямо к нему, не считая остальные. Поэтому доступ к arr[500] мгновенный: компьютер вычисляет адрес по формуле «начало плюс номер» и сразу попадает в нужную ячейку.

Но у соседства есть цена. Чтобы вставить нового зрителя в середину ряда, всем правее придётся подвинуться на кресло. Если в массиве миллион элементов и вы вставляете в начало — сдвинуть нужно почти миллион. Дорого.

Сильные и слабые места массива

Массив отлично читает по индексу и компактно лежит в памяти, что любит процессор: соседние элементы он подтягивает в кеш заранее. Зато вставка и удаление в середине медленные — мешает тот самый сдвиг.

Связный список: вагоны поезда

Связный список устроен иначе. Элементы (их называют узлами) разбросаны по памяти где попало, а держатся вместе за счёт стрелочек: каждый узел хранит своё значение и ссылку на следующий. Получается цепочка вагонов — у каждого вагона есть сцепка со следующим, но номеров мест нет.

Чтобы вставить новый узел в середину, не нужно никого двигать: достаточно перецепить две стрелки — предыдущий узел теперь смотрит на новичка, а новичок на того, кто шёл следом. Быстро и дёшево, сколько бы элементов ни было.

Сильные и слабые места списка

Список молниеносно вставляет и удаляет в середине, если вы уже стоите в нужном месте. Зато добраться до «пятисотого» узла можно только пройдя от головы по стрелочкам все 499 предыдущих — прямого доступа по номеру нет. И памяти он ест больше: на каждый элемент — ещё и ссылка.

Сравним лоб в лоб

Список своими руками

Узел — это просто значение плюс ссылка на следующего. На Python модель умещается в несколько строк:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None      # стрелка на следующий узел

# Собираем цепочку: 10 -> 20 -> 30
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

# Вставляем 15 между 10 и 20 — двигать никого не надо
node = Node(15)
node.next = head.next     # 15 теперь смотрит на 20
head.next = node          # 10 теперь смотрит на 15

# Проходим по цепочке от головы
cur = head
while cur:
    print(cur.value, end=" -> ")
    cur = cur.next
print("None")

Обратите внимание: вставка 15 — это две строчки перецепления стрелок, и неважно, миллион узлов в списке или три. Зато чтобы найти, например, четвёртый элемент, мы вынуждены идти по next с самого начала.

Так что же выбрать

Если вы часто читаете элементы по номеру и редко меняете структуру — берите массив (в Python это обычный list, он именно массив). Если вы постоянно вставляете и удаляете в середине, а доступ по номеру не нужен — связный список в своей стихии. На нём, кстати, строят очереди, стеки и более сложные структуры.

Мораль такая: у структур данных нет «лучшей» — есть подходящая под задачу. Понимать их сильные и слабые стороны важнее, чем помнить, как они устроены внутри.