🔴 Сложный ⏱️ 45 минут

Связные списки

📋 Содержание урока

Связные списки 🔗

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

В прошлом уроке ты разобрался со стеками и очередями — абстрактными типами данных, которые определяют, что можно делать (push/pop, enqueue/dequeue), но не говорят, как это устроено внутри. Связный список — один из способов реализовать и стек, и очередь (наряду с массивом), и одновременно самостоятельная структура данных со своими правилами игры. Понимание связного списка закрывает разрыв между «я умею пользоваться list в Python» и «я понимаю, почему list.insert(0, x) работает медленно, а deque.appendleft(x) — быстро».

Если ты пришёл в этот курс ради машинного обучения, честный вопрос звучит так: а где связный список в реальном ML-коде? Ответ отрезвляющий — почти нигде. Тензоры PyTorch, массивы NumPy, столбцы pandas.DataFrame требуют непрерывного блока памяти, потому что именно непрерывность даёт векторизацию, использование SIMD-инструкций процессора и эффективную работу кэша. Связный список, наоборот, разбрасывает данные по памяти произвольно — для тензорных вычислений это прямой удар по производительности. Ты не найдёшь LinkedList в реализации градиентного спуска.

Но связный список — не мёртвый академический артефакт. Он живёт внутри инструментов, которыми ты пользуешься каждый день: collections.deque в Python, очереди задач в системах потоковой обработки данных, реализация кэша давно неиспользуемых элементов (LRU), история отмены действий в редакторах. А главное — принцип, который он воплощает предельно чисто («что мы выигрываем, если откажемся от непрерывной памяти?»), это фундаментальная инженерная интуиция: у любой структуры данных есть цена, и выбор структуры — это выбор, за что именно платить. Наработать эту интуицию — и есть цель сегодняшнего урока.

История

Связный список — одна из старейших структур данных в истории программирования, и придумана она была не ради абстрактной красоты, а для решения конкретной проблемы: как работать со списками произвольной, заранее неизвестной длины, если память компьютера ограничена и фрагментирована. В 1955–1956 годах Аллен Ньюэлл, Клиффорд Шоу и Герберт Саймон разрабатывали язык обработки информации IPL для программы «Логик-теоретик» — одной из первых программ искусственного интеллекта, умевшей доказывать теоремы формальной логики. Чтобы представлять списки символов и списки списков — структуры, которые не помещались в жёсткие рамки массивов фиксированного размера тогдашних языков, — они встроили связный список прямо в язык как базовый тип данных.

По-настоящему связный список прославился благодаря Джону Маккарти, который в 1958 году создал язык Lisp — один из первых языков искусственного интеллекта и второй по возрасту высокоуровневый язык программирования в истории после Фортрана. В основе Lisp лежит одна простая идея: любые данные (числа, списки, даже сам код программы) можно представить через cons-ячейки — маленькие блоки из двух указателей, первый из которых хранит значение, а второй — ссылку на следующую такую ячейку. Это связный список, доведённый до предельной концептуальной простоты, и он оказался настолько удачной абстракцией, что определил облик всего языка на десятилетия вперёд. Не случайно само название Lisp — сокращение, расшифровывающееся как «обработка списков».

С тех пор связные списки прошли путь от единственного способа хранить последовательности до одной из многих специализированных опций. С появлением языков, где массивы умеют динамически расти (как list в Python, устроенный внутри как динамический массив), связный список перестал быть «списком по умолчанию» и стал инструментом, который выбирают осознанно — когда точно знают, за что платят его особенностями.

Односвязный список: устройство и базовые операции

Интуиция

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

Именно этот компромисс определяет всю природу связного списка: вставка в начало (и вообще в любое место, если у тебя уже есть ссылка на нужный узел) стоит одинаково дёшево независимо от размера структуры, а доступ к произвольному элементу по номеру стоит тем дороже, чем структура больше, потому что единственный способ куда-то попасть — пройти весь путь от начала.

Определение

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

Примеры с разбором

Пример 1: создание, обход и вставка в начало.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):
        """Вставка в начало списка — O(1)"""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def to_list(self):
        """Обход списка для отладки — O(n)"""
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

ll = SinglyLinkedList()
ll.push_front(30)
ll.push_front(20)
ll.push_front(10)
print(ll.to_list())  # [10, 20, 30]

Каждый вызов push_front создаёт новый узел и переставляет всего одну ссылку — self.head. Независимо от того, сколько элементов уже в списке — три или три миллиона, — эта операция выполняет одинаковое число шагов: это и есть O(1). Обход to_list, наоборот, обязан посетить каждый узел ровно один раз — O(n).

Пример 2: вставка в конец — где прячется скрытая ловушка сложности.

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # отдельная ссылка на последний узел

    def append_naive(self, value):
        """Вставка в конец БЕЗ хранения хвоста — O(n)"""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:  # идём до последнего узла
            current = current.next
        current.next = new_node

    def append_fast(self, value):
        """Вставка в конец С хранением хвоста — O(1)"""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

append_naive вынужден пройти весь список, чтобы найти последний узел, — O(n) на каждую вставку и O(n²) суммарно при добавлении n элементов по одному. append_fast хранит отдельную ссылку self.tail на последний узел и обновляет её при каждой вставке — теперь вставка в конец такая же дешёвая, как и вставка в начало, O(1). Разница между этими двумя версиями — наглядный пример того, как один «лишний» указатель радикально меняет асимптотику алгоритма.

Пример 3: поиск и удаление по значению.

class SinglyLinkedList:
    # ... head и push_front как в примере 1 ...

    def remove(self, value):
        """Удаление первого узла с заданным значением — O(n)"""
        if self.head is None:
            return False
        if self.head.value == value:  # удаляем саму голову
            self.head = self.head.next
            return True
        prev = self.head
        current = self.head.next
        while current is not None:
            if current.value == value:
                prev.next = current.next  # "перепрыгиваем" через current
                return True
            prev = current
            current = current.next
        return False

Чтобы удалить узел из середины односвязного списка, недостаточно знать сам узел — нужен указатель на предыдущий узел prev, потому что удаление — это переприсоединение prev.next в обход удаляемого узла. Поскольку список хранит ссылки только «вперёд», единственный способ найти prev — пройти список от головы, сравнивая значения. Отсюда и сложность O(n): поиск нужного узла занимает O(n), а само «перепрыгивание» — O(1). Итоговая сложность операции определяется её самым медленным шагом.

Почему это важно

В ML-практике связный список сам по себе почти не встречается в вычислительном ядре — NumPy и PyTorch спроектированы вокруг непрерывной памяти. Но понимание того, почему list.insert(0, x) в Python стоит O(n) (нужно физически сдвинуть все элементы на одну позицию), а push_front связного списка — O(1), напрямую объясняет, почему collections.deque — правильный выбор для очереди сообщений или буфера скользящего окна признаков в потоковом пайплайне, а обычный list — нет.

Двусвязный список: движение в обе стороны

Интуиция

Односвязный список — это цепочка людей, где каждый знает только следующего. Двусвязный список — та же цепочка, но теперь каждый человек держит за руку не только следующего, но и предыдущего. Цена очевидна: каждому нужно запоминать на одну связь больше. Но выгода велика — теперь по цепочке можно идти в обе стороны, а если тебе кто-то указал прямо на нужного человека посреди цепочки, ты можешь мгновенно «вынуть» его, отсоединив от соседа слева и соседа справа, не разыскивая, кто стоял перед ним.

Это меняет главное узкое место односвязного списка: удаление узла по прямой ссылке на него (а не по значению) становится настоящим O(1), потому что предыдущий узел уже доступен напрямую через node.prev — искать его перебором не нужно.

Определение

Определение. Двусвязный список — линейная структура данных, в которой каждый узел хранит три поля: значение, указатель на следующий узел (next) и указатель на предыдущий узел (prev). Первый узел имеет prev = None, последний — next = None. Двусвязный список обычно хранит ссылки и на голову (head), и на хвост (tail), что позволяет эффективно работать с обоими концами структуры и обходить её в любом направлении.

Примеры с разбором

Пример 1: реализация с prev/next и O(1) вставками с обеих сторон.

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def push_front(self, value):
        """Вставка в начало — O(1)"""
        node = DNode(value)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    def push_back(self, value):
        """Вставка в конец — O(1)"""
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node

В обеих операциях требуется обновить на одну ссылку больше, чем в односвязном списке (нужно связать не только «вперёд», но и «назад»), но асимптотика остаётся O(1) — количество шагов не зависит от размера списка.

Пример 2: удаление узла по прямой ссылке за O(1) — главное преимущество двусвязного списка.

def remove_node(self, node):
    """Удаление узла, если известна прямая ссылка на него — O(1)"""
    if node.prev is not None:
        node.prev.next = node.next
    else:
        self.head = node.next  # удаляем голову

    if node.next is not None:
        node.next.prev = node.prev
    else:
        self.tail = node.prev  # удаляем хвост

Если у тебя уже есть ссылка на узел (например, она хранится в хэш-таблице — эта идея пригодится в следующем уроке про хэш-таблицы), удаление занимает четыре присваивания указателей независимо от позиции узла и размера списка. В односвязном списке для того же действия пришлось бы искать предыдущий узел перебором — O(n). Это и есть ключевое структурное отличие двусвязного списка.

Пример 3: кэш давно неиспользуемых элементов (LRU) — практическое применение двусвязного списка вместе с хэш-таблицей.

class LRUCache:
    """Кэш, вытесняющий давно неиспользуемые элементы, O(1) на операцию"""
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}          # ключ -> узел двусвязного списка
        self.dll = DoublyLinkedList()

    def get(self, key):
        if key not in self.map:
            return None
        node = self.map[key]
        self.dll.remove_node(node)        # O(1): убираем узел с текущего места
        self.dll.push_front(node.value)   # O(1): кладём как самый свежий
        self.map[key] = self.dll.head
        return node.value

    def put(self, key, value):
        if key in self.map:
            self.dll.remove_node(self.map[key])
        elif len(self.map) >= self.capacity:
            oldest = self.dll.tail          # давно неиспользуемый — в хвосте
            self.dll.remove_node(oldest)    # O(1) благодаря двусвязности
            del self.map[oldest.value]
        self.dll.push_front(value)
        self.map[key] = self.dll.head

Такой кэш держит «свежие» элементы у головы, а «устаревшие» — у хвоста; каждое обращение перемещает элемент к голове. Всё это работает за O(1) только потому, что двусвязный список позволяет удалить произвольный узел без поиска его соседей. Подобный кэш используется, например, для хранения недавно вычисленных эмбеддингов или результатов дорогих запросов к модели, чтобы не пересчитывать их заново при повторном обращении.

Почему это важно

Компромисс двусвязного списка предельно честный: он тратит примерно на треть больше памяти на узел (дополнительный указатель prev), но взамен даёт O(1)-удаление по ссылке и обход в обе стороны. Именно двусвязный список лежит в основе collections.OrderedDict и внутреннего устройства collections.deque в Python — а значит, каждый раз, когда ты используешь deque для скользящего окна признаков или буфера очереди задач в потоковом ML-пайплайне, ты пользуешься ровно этим компромиссом.

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

Интуиция

Вопрос «что лучше — массив или связный список?» некорректен сам по себе, потому что универсального победителя нет — есть только разные цены за разные операции. Массив — это шкафчики с номерами: мгновенный доступ по номеру, но чтобы вставить новый шкафчик посередине ряда, нужно сдвинуть все остальные. Связный список — это цепочка: вставка в любое известное место мгновенная, но чтобы узнать, что лежит в «пятом от начала» звене, нужно пройти всю цепочку. Выбор структуры данных — это по сути ответ на вопрос: какая операция в твоей задаче происходит чаще всего, и за какую именно операцию ты готов заплатить?

Определение

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

Операция Динамический массив (list) Односвязный список Двусвязный список
Доступ по индексу O(1) O(n) O(n)
Поиск по значению O(n) O(n) O(n)
Вставка в начало O(n) O(1) O(1)
Вставка в конец O(1)* O(1) при хранении хвоста O(1)
Вставка/удаление по известной ссылке в середине O(n) — сдвиг элементов O(n) — нужен поиск prev O(1)
Удаление в начале O(n) O(1) O(1)
Удаление в конце O(1) O(n) без обратной ссылки O(1)
Память на элемент минимум, без накладных расходов данные + 1 указатель данные + 2 указателя
Локальность в кэше процессора высокая (непрерывный блок) низкая (узлы разбросаны) низкая (узлы разбросаны)

*амортизированно; при заполнении выделенного блока требуется реаллокация за O(n)

Примеры с разбором

Пример 1: цена вставки в начало на практике.

import time

def insert_front_array(n):
    arr = []
    start = time.perf_counter()
    for i in range(n):
        arr.insert(0, i)  # каждый вызов сдвигает все элементы — O(n)
    return time.perf_counter() - start

def insert_front_linked(n):
    ll = SinglyLinkedList()
    start = time.perf_counter()
    for i in range(n):
        ll.push_front(i)  # O(1) на каждую вставку
    return time.perf_counter() - start

# суммарная сложность вставки n элементов в начало массива — O(n^2),
# суммарная сложность вставки n элементов в начало связного списка — O(n)

list.insert(0, i) физически копирует все существующие элементы на одну позицию правее при каждом вызове — n вставок дают суммарно O(n²) операций копирования. push_front связного списка не двигает ничего, кроме одной ссылки, — n вставок дают суммарно O(n). На больших n разница становится не теоретической, а вполне заметной по секундомеру.

Пример 2: почему связный список — плохой выбор для числовых вычислений.

import numpy as np

# Непрерывный массив: элементы лежат подряд в памяти
arr = np.arange(1_000_000, dtype=np.float64)
result = arr * 2.0  # процессор обрабатывает блоками (SIMD), кэш почти не промахивается

# Условный связный список тех же чисел потребовал бы:
# - обхода миллиона указателей вразброс по памяти;
# - кэш-промаха почти на каждом шаге, потому что соседние по логике
#   узлы физически не соседствуют в памяти;
# - невозможности применить векторные инструкции процессора к разрозненным ячейкам

Именно поэтому NumPy, PyTorch и любая тензорная библиотека строятся вокруг непрерывных буферов памяти, а не связных списков. Компромисс «быстрая вставка ценой медленного доступа» в задачах, где нужен именно быстрый массовый доступ и векторные операции (а это почти вся числовая часть ML), играет против связного списка — поэтому ты его там и не видишь.

Пример 3: где связный список всё же выигрывает — очередь задач в потоковом пайплайне.

from collections import deque

# Буфер задач на обработку потока событий (например, мини-батчи
# для онлайн-обучения модели, поступающие из очереди сообщений)
task_queue = deque()

def on_new_event(event):
    task_queue.append(event)          # O(1) — добавление в конец

def process_next():
    if task_queue:
        event = task_queue.popleft()  # O(1) — извлечение из начала
        return event

Здесь произвольный доступ по индексу не нужен вообще — задачи всегда добавляются в конец и забираются с начала. Для такого шаблона использования deque (двусвязный список блоков) выигрывает у обычного list: list.pop(0) стоил бы O(n) на каждое извлечение, а deque.popleft() — O(1). Это ровно тот случай, когда компромисс связного списка работает в твою пользу.

Почему это важно

Умение быстро прочитать таблицу компромиссов и спросить себя «какая операция у меня в горячем пути — доступ по индексу или вставка/удаление на краях» — это ровно тот инженерный навык, который отличает код, работающий только на маленьких данных, от кода, не деградирующего при росте объёма данных на порядки. В пайплайнах обработки данных для ML это напрямую проявляется в выборе очереди задач, буфера сообщений или структуры для инкрементального накопления батчей.

Кольцевой связный список: список, замкнутый сам на себя

Интуиция

Представь плейлист с включённым повтором: когда трек заканчивается, следующий — снова первый, и так по кругу бесконечно. Обычный список на этом месте вернул бы None и остановился, но кольцевой связный список устроен так, что последний узел указывает не на «конец», а обратно на первый узел — цепочка замыкается в кольцо, и обход можно продолжать сколь угодно долго.

Определение

Определение. Кольцевой связный список — связный список (односвязный или двусвязный), в котором указатель последнего узла ссылается не на None, а на первый узел структуры, образуя замкнутый цикл. У списка нет выделенного «конца» — единственный способ понять, что обход завершил полный круг, — сравнить текущий узел с узлом, с которого начался обход.

Примеры с разбором

Пример 1: циклический обход по кругу — распределение задач между воркерами.

class CircularNode:
    def __init__(self, value):
        self.value = value
        self.next = None

def make_circular(values):
    """Собирает кольцевой список из последовательности значений"""
    if not values:
        return None
    head = CircularNode(values[0])
    current = head
    for v in values[1:]:
        current.next = CircularNode(v)
        current = current.next
    current.next = head  # замыкаем кольцо
    return head

def round_robin(head, steps):
    """Распределяет steps задач по кругу между узлами (воркерами)"""
    current = head
    for i in range(steps):
        print(f"Задача {i} -> воркер {current.value}")
        current = current.next

workers = make_circular(["A", "B", "C"])
round_robin(workers, 7)  # A, B, C, A, B, C, A — цикл повторяется бесконечно

Без кольцевой связи пришлось бы вручную проверять конец списка и возвращаться к началу отдельной веткой кода. Кольцевая структура делает возврат к началу естественным следствием самой связи next — планировщик задач или диспетчер воркеров крутится по кругу без специальной логики «сброса».

Пример 2: обнаружение цикла — алгоритм Флойда («черепаха и заяц»).

def has_cycle(head):
    """Определяет, есть ли цикл в списке (не обязательно полностью кольцевом)"""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # черепаха идёт на один узел
        fast = fast.next.next     # заяц идёт на два узла
        if slow is fast:          # встретились — есть цикл
            return True
    return False  # заяц дошёл до None — цикла нет

Два указателя движутся с разной скоростью; если список кольцевой (или в нём случайно образовался цикл из-за ошибки в коде), быстрый указатель рано или поздно догонит медленный внутри кольца — они окажутся в одном узле. Если цикла нет, быстрый указатель первым дойдёт до None. Это O(n) по времени и O(1) по дополнительной памяти — заметно эффективнее, чем хранить множество уже посещённых узлов.

Пример 3: кольцевой буфер для потоковых данных.

class CircularBuffer:
    """Кольцевой буфер фиксированного размера для скользящего окна метрик"""
    def __init__(self, size):
        self.buffer = [None] * size
        self.size = size
        self.index = 0

    def add(self, value):
        self.buffer[self.index] = value
        self.index = (self.index + 1) % self.size  # возврат к началу по кругу

# Хранит последние N значений метрики (например, задержку ответа модели),
# перезаписывая самые старые по кругу — без сдвига элементов
metrics = CircularBuffer(5)
for latency in [12, 15, 9, 20, 11, 14]:
    metrics.add(latency)

Кольцевой принцип здесь реализован поверх массива, через индекс по модулю размера, а не через указатели узлов, — это показывает, что «кольцевая» логика не привязана исключительно к связным спискам, но исходная идея (после последнего элемента — снова первый) та же самая, что и в кольцевом связном списке.

Почему это важно

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

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Определи асимптотическую сложность операции «вставка нового элемента в начало односвязного списка» и объясни, почему она не зависит от текущей длины списка.

Задание 2. Напиши функцию length(head), подсчитывающую число узлов односвязного списка, и определи её сложность.

Задание 3. Напиши функцию поиска элемента по значению в односвязном списке. Укажи сложность в лучшем и в худшем случае.

Задание 4. Дан односвязный список 5 -> 3 -> 8 -> 1. Опиши по шагам, что произойдёт в памяти при вызове push_front(10), и укажи итоговый список.

Задание 5. Объясни, почему list.insert(0, x) в Python работает за O(n), а push_front связного списка — за O(1), хотя обе операции формально «вставляют элемент в начало».

Задание 6. Напиши итеративную функцию реверса односвязного списка.

Задание 7. Сколько указателей нужно физически изменить при удалении узла из середины односвязного списка, если предыдущий узел уже известен?

Задание 8. Список из n элементов хранится как массив, как односвязный список и как двусвязный список. Сравни, сколько дополнительной памяти (в указателях на узел) требует каждый вариант сверх памяти на сами значения.

Задание 9. Напиши функцию, находящую последний узел односвязного списка, если отдельная ссылка на хвост не хранится. Определи сложность.

Задание 10. Объясни разницу в сложности между вставкой в конец списка при наличии хранимой ссылки на хвост и без неё.

Средние (задания 11–20)

Задание 11. Для двусвязного списка сравни количество операций с указателями при вставке в начало (push_front) и при вставке в конец (push_back), если список уже содержит хотя бы один элемент.

Задание 12. Объясни, почему удаление узла по прямой ссылке на него возможно за O(1) в двусвязном списке, но невозможно за O(1) в односвязном списке без дополнительной информации.

Задание 13. Напиши функцию, находящую средний узел односвязного списка за один проход, используя два указателя разной скорости.

Задание 14. Напиши функцию слияния двух уже отсортированных односвязных списков в один отсортированный список.

Задание 15. Сервис хранит историю версий документа, в которую часто вставляются новые версии в произвольное место (по времени создания), но почти никогда не требуется обращение к версии по номеру. Обоснуй выбор между массивом и связным списком.

Задание 16. Нужно хранить таблицу эмбеддингов, к строкам которой модель обращается по числовому индексу миллионы раз за секунду во время обучения. Обоснуй выбор между связным списком и массивом (NumPy-подобной структурой).

Задание 17. Оцени количество операций сравнения в худшем случае при поиске элемента, отсутствующего в односвязном списке из n узлов.

Задание 18. Объясни, зачем кэшу давно неиспользуемых элементов (LRU) одновременно нужны и хэш-таблица, и двусвязный список — почему одной из этих структур недостаточно.

Задание 19. Сравни суммарную сложность вставки n элементов подряд в начало массива (циклом с list.insert(0, x)) и в начало связного списка (циклом с push_front).

Задание 20. Напиши функцию удаления дубликатов из неотсортированного односвязного списка с использованием вспомогательного множества, и определи её сложность по времени и по памяти.

Сложные (задания 21–30)

Задание 21. Объясни математически, почему в алгоритме Флойда («черепаха и заяц») быстрый и медленный указатели обязательно встретятся, если в списке есть цикл.

Задание 22. В кольцевом списке ровно k узлов, черепаха и заяц стартуют одновременно с головы. Через сколько шагов черепахи они впервые встретятся, если оба сразу находятся внутри кольца?

Задание 23. Опиши идею алгоритма реверса односвязного списка группами по k элементов (без полного кода): что происходит с каждой группой и как группы соединяются между собой.

Задание 24. Обсуди, почему связный список — не оптимальный выбор для реализации очереди с приоритетом, если приоритеты элементов часто меняются.

Задание 25. Нужно хранить время отклика последних 1000 запросов к модели в продакшене, постоянно добавляя новое значение и автоматически забывая самое старое. Сравни реализацию на связном списке и на кольцевом буфере поверх массива, обоснуй выбор.

Задание 26. Опиши идею проверки, является ли односвязный список палиндромом, с использованием только O(1) дополнительной памяти.

Задание 27. Объясни, почему collections.deque в Python внутри устроен как двусвязный список блоков фиксированного размера, а не как список из одного значения на узел, и какие преимущества это даёт.

Задание 28. Нужно часто вставлять числа в уже отсортированную последовательность и после каждой вставки быстро находить k-й по порядку элемент. Объясни, почему ни простой массив, ни связный список не идеальны для этой задачи.

Задание 29. Нужно объединить k уже отсортированных связных списков суммарной длины n в один отсортированный список. Сравни сложность наивного последовательного слияния всех списков попарно один за другим и попарного слияния «турниром» (списки сливаются парами, затем пары пар, и так далее).

Задание 30. Проектируется пайплайн онлайн-обучения модели: входящие события нужно (1) временно накапливать в буфере ограниченного размера, отбрасывая самые старые при переполнении, (2) складывать в очередь на последовательную обработку воркерами, (3) кэшировать результаты дорогих вычислений по ключу события с вытеснением давно неиспользуемых. Для каждого из трёх компонентов выбери подходящую структуру данных и обоснуй выбор.

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

❌ Ошибка: Считать, что связный список всегда «эффективнее» массива, потому что вставка в начало у него O(1).

✅ Правильно: Сравнивать структуры данных по всему набору операций, которые реально нужны в задаче, а не по одной удобной операции.

💡 Почему: У связного списка доступ по индексу и поиск остаются O(n) — если в задаче преобладают именно эти операции, связный список проиграет массиву, несмотря на быструю вставку в начало.

❌ Ошибка: Забывать обновлять указатель tail при вставке или удалении элемента с конца связного списка.

✅ Правильно: Явно обрабатывать оба указателя, head и tail, в каждой операции, которая может затронуть начало или конец списка, включая крайние случаи пустого списка и списка из одного элемента.

💡 Почему: Рассинхронизация tail с реальным последним узлом превращает операции, которые должны быть O(1), обратно в O(n) или приводит к трудноуловимым ошибкам при дальнейших вставках.

❌ Ошибка: Переставлять head = head.next, не сохранив заранее ссылку на прежнюю голову, если она ещё нужна дальше по коду.

✅ Правильно: Сохранять нужную ссылку во временную переменную до того, как связь будет переприсоединена.

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

❌ Ошибка: Пытаться удалить узел в односвязном списке, имея только ссылку на сам удаляемый узел, без ссылки на предыдущий.

✅ Правильно: Либо хранить ссылку на предыдущий узел при обходе, либо использовать двусвязный список, если такое удаление нужно часто.

💡 Почему: Без обратной ссылки единственный способ найти предыдущий узел — заново пройти список от головы, что превращает предполагаемую O(1) операцию в O(n).

❌ Ошибка: Не проверять пустой список и список из одного элемента как отдельные крайние случаи при написании операций вставки и удаления.

✅ Правильно: Явно тестировать реализацию на пустом списке и на списке из одного узла — многие ошибки со связными списками возникают именно на этих границах.

💡 Почему: Операции вроде удаления головы или вставки в пустой список меняют не только соседние узлы, но и сами указатели head/tail, что легко упустить в общем случае кода.

❌ Ошибка: Использовать list.pop(0) в цикле обработки очереди вместо deque.popleft().

✅ Правильно: Для любой очереди, где элементы часто добавляются и забираются с разных концов, использовать collections.deque.

💡 Почему: list.pop(0) в Python стоит O(n), поскольку требует сдвига всех оставшихся элементов, — в цикле обработки потока событий это превращает линейный по своей природе алгоритм в квадратичный.

Главное запомнить

✅ Односвязный список — последовательность узлов, каждый из которых хранит значение и указатель на следующий узел; доступ возможен только в одном направлении, от головы

✅ Вставка и удаление в начале односвязного списка — O(1); доступ по индексу и поиск по значению — O(n)

✅ Двусвязный список добавляет к каждому узлу указатель на предыдущий узел: платит дополнительной памятью, получает взамен O(1)-удаление по прямой ссылке на узел и обход в обе стороны

✅ Связный список — это не про экономию памяти, а про перенос стоимости операций: то, что дёшево в массиве (доступ по индексу), дорого в списке, и наоборот (вставка в начало)

✅ Массив выигрывает там, где нужен частый произвольный доступ по индексу и локальность памяти для векторных вычислений, — поэтому все тензорные библиотеки ML построены на непрерывных массивах

✅ Связный список выигрывает там, где часты вставки и удаления на краях структуры, а произвольный доступ не требуется, — очереди задач, потоковые буферы

✅ Кольцевой связный список — список, у которого последний узел указывает обратно на первый; полезен для циклического распределения задач и буферов с повтором

✅ Алгоритм Флойда («черепаха и заяц») находит цикл в списке за O(n) по времени и O(1) по дополнительной памяти

✅ collections.deque в Python реализован как двусвязный список блоков фиксированного размера — используй его вместо list для очередей с частыми операциями на обоих концах

✅ Выбор структуры данных — это выбор, за какую именно операцию ты готов заплатить; универсальной «самой лучшей» структуры не существует, есть только подходящая под конкретный профиль нагрузки

Связь с другими темами курса

🔙 Откуда пришли: Из урока 253 про стеки и очереди — абстрактные типы данных, которые связный список умеет эффективно реализовывать с обоих концов, если это двусвязный список или связный список с хранимым хвостом.

🔜 Куда идём:

  • Хэш-таблицы (урок 255) — связный список станет одним из стандартных способов разрешения коллизий (метод цепочек), а также кирпичиком, из которого строится LRU-кэш вместе с хэш-таблицей
  • Деревья (уроки 256–257) — узел дерева является прямым обобщением узла связного списка: вместо одного указателя next узел дерева хранит сразу несколько ссылок на детей
  • Графы (уроки 259–260) — список смежности, один из стандартных способов представления графа, — это массив связных списков, где i-й список хранит соседей i-й вершины

🎯 В машинном обучении: collections.deque используется для буферов скользящего окна признаков и очередей задач в потоковых пайплайнах; связка «хэш-таблица плюс двусвязный список» лежит в основе LRU-кэшей, которыми кэшируют дорогие вычисления вроде эмбеддингов или ответов модели; сама идея компромисса «быстрая вставка против быстрого доступа» — основа для выбора структур данных в любой инженерной части ML-системы, от буферов данных до систем очередей сообщений.

Интересные факты

📌 Название языка программирования Lisp, созданного Джоном Маккарти в 1958 году, — сокращение от английского словосочетания, означающего «обработка списков». Вся конструкция языка построена вокруг cons-ячеек, то есть связных списков, доведённых до предельной концептуальной простоты, и это определило облик языков программирования для задач искусственного интеллекта на десятилетия вперёд.

📌 collections.deque в Python внутри устроен не как классический учебный двусвязный список из одного значения на узел, а как двусвязный список блоков — каждый «узел» хранит десятки значений подряд. Это сделано специально, чтобы снизить накладные расходы на служебные поля Python-объектов и одновременно улучшить локальность памяти внутри блока.

📌 Стандартный декоратор functools.lru_cache в Python, которым легко пометить любую медленную функцию для автоматического кэширования результатов, под капотом использует ровно ту же связку «хэш-таблица плюс двусвязный список», которую ты реализовал в этом уроке вручную.

📌 Алгоритм обнаружения цикла «черепаха и заяц» придумал американский специалист по информатике Роберт Флойд — тот же человек, чьё имя носит алгоритм Флойда — Уоршелла для поиска кратчайших путей между всеми парами вершин графа, с которым ты встретишься в одном из следующих уроков этого блока.

Лайфхаки и полезные трюки

💡 Если вставки в конец связного списка происходят часто, всегда храни отдельную ссылку на хвост (tail) — без неё каждая такая вставка незаметно превращается из O(1) в O(n).

💡 Для очередей и буферов, где элементы добавляются и забираются с обоих концов, сразу используй collections.deque вместо list — не изобретай связный список вручную там, где стандартная библиотека уже решила задачу эффективно.

💡 При удалении узла в односвязном списке сначала отдельной веткой обработай случай удаления самой головы — это избавляет от путаницы с указателем prev, которого для головы попросту не существует.

💡 Заведи привычку писать вспомогательную функцию вроде to_list() или print_list() для отладки связных списков — визуализация текущего состояния цепочки узлов экономит гораздо больше времени, чем попытка отследить баг по одним только указателям в уме.

💡 Перед выбором структуры данных задай себе один простой вопрос: что в этой задаче происходит чаще — доступ по индексу или вставка/удаление на краях структуры? Ответ почти всегда сразу указывает на массив либо на связный список.

💡 Используй фиктивный (sentinel) узел-заглушку перед головой списка при написании функций вставки и удаления — он убирает специальный случай «операция затрагивает саму голову» и заметно упрощает код, как это сделано в решении задания 14.

Связный список редко встретится тебе внутри слоя нейросети или цикла обучения модели — и это нормально, потому что ML-вычисления живут по законам непрерывной памяти, которые связный список сознательно нарушает ради другого преимущества. Но сама идея, которую он показывает предельно наглядно — что у каждой структуры данных есть цена, и эта цена распределяется между разными операциями по-разному, — будет сопровождать тебя на протяжении всего оставшегося блока курса про алгоритмы и структуры данных. В следующем уроке ты увидишь, как связный список становится частью решения совсем другой задачи: что делать, когда двум разным ключам хэш-таблицы вдруг досталось одно и то же место.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!