Связный список

Список из узлов

Питоновский list хранит элементы рядом в памяти. Связный списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. устроен иначе: это цепочка узлов, где каждый узел хранит своё значение и ссылку на следующий узел. Как вагоны поезда: каждый сцеплен со следующим, а последний ни с кем (его ссылка — None).

Чтобы описать узел, заведём простой классШаблон для создания объектов: описывает их данные (атрибуты) и поведение (методы). с двумя полями: value (значение) и next (ссылка на следующий узел).

Обход связного списка

Чтобы пройти по всем узлам, начинают с первого (его называют head, голова) и двигаются по ссылкам next, пока не упрутся в None. Это типичный паттерн «бегунка» (current).

Добавление в начало

Сила связного списка — в дешёвой вставке. Чтобы добавить элемент в начало, создаём новый узел, направляем его next на текущую голову и объявляем его новой головой. Не нужно ничего сдвигать, как в обычном списке.

Вернётся 4. Бегунок проходит все узлы, прибавляя единицу на каждом, пока не дойдёт до None после последнего узла.

⚠️ Частые ошибки новичков

Ошибка. Забыть продвинуть бегунок current = current.next внутри циклаКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно.. Тогда current навсегда останется на первом узле, условие while current всегда истинно и цикл зациклится. Запустите сломанный код (прервите его) и почините, добавив шаг.