Связные списки и персистентные структуры

Массив [4,9,12,7,5] позволяет прочитать пятый элемент как A[4]. Цепочка head → 4 → 9 → 12 → 7 → 5 требует четырёх переходов next. Узлы могут лежать в памяти далеко друг от друга: соседство хранится в ссылках, а не определяется близостью адресов.

head — ссылка на первый узел. Сам узел хранит value (значение) и next (ссылку на следующий). null означает, что следующего узла нет. Известная ссылка даёт быстрый доступ к полям одного узла; произвольный номер позиции ещё нужно найти.

В учебном коде Python и Rust номера в массиве next моделируют ссылки. Например next[4]=1 означает переход из узла #4 в #1, даже если значение лежит не в соседней ячейке. Option<usize> в Rust и None в Python моделируют ссылку или её отсутствие.

Стоимость доступа определена. Теперь проследим одно локальное изменение ссылок в односвязном списке.

В цепочке 4 → 9 → 12 поле value первого узла равно 4, next ссылается на узел со значением 9. head ссылается на 4, а next узла 12 равен null. Новый узел 7 сначала должен запомнить старую ссылку на 9; иначе после замены ссылки у 4 старый хвост будет недоступен.

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

Односвязный список (Singly linked list) — Последовательность узлов, где каждый хранит значение и ссылку next на следующий узел.

Ссылка head указывает на первую вершину. Для обхода достаточно повторять x = x.next до null. Поиск i-го элемента требует i переходов: O(i).

y.next = x.next
x.next = y

Для цепочки 4 → 9 → 12 вставка 7 после узла 4 сначала сохраняет y.next = x.next, а затем устанавливает x.next = y. Меняя присваивания местами, легко создать ссылку y на самого себя и потерять старый хвост. Удаление узла после известного x аналогично: x.next = x.next.next, если следующий узел существует.

def reverse_links(next_node, head):
    previous = None
    while head is not None:
        following = next_node[head]
        next_node[head] = previous
        previous, head = head, following
    return previous

values = [1, 2, 3]
links = [1, 2, None]
head = reverse_links(links, 0)
result = []
while head is not None:
    result.append(values[head])
    head = links[head]
print(*result)

fn reverse_links(next: &mut [Option<usize>], mut head: Option<usize>) -> Option<usize> {
    let mut previous = None;
    while let Some(i) = head {
        let following=next[i]; next[i]=previous;
        previous=Some(i); head=following;
    }
    previous
}
fn main() {
    let values=[1,2,3]; let mut next=[Some(1),Some(2),None];
    let mut head=reverse_links(&mut next,Some(0)); let mut result=Vec::new();
    while let Some(i)=head { result.push(values[i].to_string()); head=next[i]; }
    println!("{}",result.join(" "));
}

3 2 1

Быстрая вставка после известного узла не решила удаление самого узла. Для этого добавим обратные связи.

Сначала обход и вставка

Перед разворотом всей цепочки реализуйте два коротких действия: дойти по next до нужного узла и вставить после известного узла, сохранив хвост. Массив next_node моделирует ссылки между узлами; None завершает цепочку.

def find_node(values, next_node, head, target):
	# Напишите решение
	pass

def insert_after(next_node, head, x):
	# Напишите решение
	pass

def reverse_links(next_node, head):
	# Напишите решение
	pass

Сначала обычный список 4 ↔ 9 ↔ 12. Удаляя 9, меняем 4.next на 12 и 12.prev на 4. Если удаляется голова, head становится правым соседом; у хвоста меняется tail. У единственного узла оба внешних указателя становятся null. Sentinel позволит объединить эти крайние случаи одним кодом.

В односвязном списке перед удалением нужен предшественник. Сохраним обратную ссылку prev и получим возможность отсоединять известный узел локально. Затем уберём особые случаи первого и последнего элементов с помощью sentinel.

Двусвязный список (Doubly linked list) — Список, где у каждого узла есть ссылки prev и next.

Добавление или удаление известного узла выполняется изменением постоянного числа связей. Циклическая структура с фиктивной вершиной (sentinel) устраняет специальные случаи головы и хвоста.

x.prev.next = x.next
x.next.prev = x.prev
// отсоединить x / освободить память при необходимости

Sentinel не хранит пользовательское значение и замыкает пустой список сам на себя. Для любого живого узла сохраняются равенства x.next.prev = x и x.prev.next = x. Они дают простой способ проверять корректность после вставки и удаления. После удаления ссылка на узел больше не должна использоваться как ссылка на член списка.

Согласованные prev/next позволяют не только удалять узлы, но и соединять целые контейнеры за постоянное число переназначений.

Есть два уже найденных контейнера: A содержит 4 ↔ 9, B содержит 12 ↔ 7. Чтобы получить A: 4 ↔ 9 ↔ 12 ↔ 7, соединяем хвост A с головой B и хвост B с sentinel A. Значения не копируются, но B перестаёт быть независимым списком. Проверить наличие 7 без готовой ссылки по-прежнему требует обхода.

Список задаёт последовательность, однако его можно использовать как контейнер элементов множества, если порядок не важен. При этом быстрые перестановки ссылок не превращают поиск произвольного значения в O(1).

Лекция показывает, как с помощью циклического двусвязного списка представлять коллекцию с операциями создания, добавления, удаления известного элемента, выдачи произвольного элемента и объединения списков.

Если у каждого множества известен указатель на его фиктивный узел, конкатенация двух непустых списков сводится к постоянному числу переназначений prev/next.

Слияние двух списков с известными концами может переназначить O(1) ссылок, но это разрушающая конкатенация: исходные списки перестают быть двумя независимыми контейнерами. Уникальность значений и обновление поля «владелец» у каждого узла в эту оценку не входят. Если нужно отвечать, принадлежат ли элементы одному множеству, потребуется другая структура — DSU из следующей лекции.

Прежде чем переходить к версиям, реализуем на узлах два интерфейса, уже знакомых по массивам.

Сравним новую память с уже знакомым интерфейсом. Чтобы получить стек, достаточно одного конца списка; очередь требует обоих. Здесь особенно полезно проверить переход от одного элемента к пустому состоянию.

Стек реализуется вставкой/удалением первого узла списка. Для FIFO-очереди удобно хранить указатель на голову и хвост; при добавлении к хвосту и удалении из головы обе операции занимают O(1).

Правильная реализация должна обновлять tail, когда удаляется последний элемент. Фиктивная вершина часто уменьшает число проверок.

enqueue(x):
    tail.next = new Node(x)
    tail = tail.next

dequeue():
    assert head.next != null
    x = head.next.value
    head.next = head.next.next
    if head.next == null: tail = head
    return x

В схеме с фиктивным head очередь из одного пользовательского узла имеет head.next = tail. После его удаления tail возвращается к sentinel head; следующая вставка снова присоединяется к живой очереди. В схеме без sentinel единственный узел действительно задаётся head=tail, а пустое состояние head=tail=null. Не смешивайте эти два соглашения.

class NodeQueue:
    def __init__(self):
        self.nodes = []
        self.head = self.tail = None
    def push(self, value):
        i = len(self.nodes)
        self.nodes.append([value, None])
        if self.tail is None:
            self.head = i
        else:
            self.nodes[self.tail][1] = i
        self.tail = i
    def pop(self):
        if self.head is None:
            return None
        value, self.head = self.nodes[self.head]
        if self.head is None:
            self.tail = None
        return value

q = NodeQueue()
q.push(4)
q.push(9)
first, second = q.pop(), q.pop()
q.push(7)
print(first, second, q.pop())

#[derive(Default)]
struct NodeQueue { nodes: Vec<(i64,Option<usize>)>, head: Option<usize>, tail: Option<usize> }
impl NodeQueue {
    fn push(&mut self,value:i64) {
        let i=self.nodes.len(); self.nodes.push((value,None));
        if let Some(tail)=self.tail { self.nodes[tail].1=Some(i); }
        else { self.head=Some(i); }
        self.tail=Some(i);
    }
    fn pop(&mut self)->Option<i64> {
        let i=self.head?; let (value,next)=self.nodes[i]; self.head=next;
        if self.head.is_none() { self.tail=None; }
        Some(value)
    }
}
fn main() { let mut q=NodeQueue::default();q.push(4);q.push(9);let a=q.pop().unwrap();let b=q.pop().unwrap();q.push(7);println!("{} {} {}",a,b,q.pop().unwrap()); }

4 9 7

Мы научились менять текущее состояние. Следующий шаг — сохранить прежнее состояние доступным после изменения.

История документа: V0 пустая, V1 добавляет запись 5, V2 добавляет 8. Вернитесь к V1 и вместо 8 добавьте 3 — появится отдельная V3. Должны оставаться доступны и [5,8], и [5,3], и исходная [5]. Сначала попробуйте ветвление в модели, затем назовём такую структуру персистентной.

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

Персистентная структура (Persistent data structure) — Структура, у которой после обновления сохраняется доступ к предыдущим версиям состояния.

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

Персистентный стек: push создаёт новый узел с next = старый top, pop возвращает top.next. Обе операции O(1), старые версии остаются доступны.

Создадим V1 = push(5,V0), V2 = push(8,V1) и V3 = push(3,V1). В V2 и V3 новый только верхний узел; старый узел 5 общий. Ни одно поле старого узла не меняется. Классификацию частичной и полной персистентности можно прочитать в дополнительном блоке следующей главы.

from dataclasses import dataclass

@dataclass(frozen=True)
class Node:
    value: int
    next: 'Node | None' = None

def push(top, value):
    return Node(value, top)

def pop(top):
    return top.next if top is not None else None

v1 = push(None, 5)
v2 = push(v1, 8)
v3 = push(v1, 3)
print(v2.value, v3.value, pop(v2).value)

use std::rc::Rc;
type Link=Option<Rc<Node>>;
struct Node {value:i64,next:Link}
fn push(top:&Link,value:i64)->Link { Some(Rc::new(Node{value,next:top.clone()})) }
fn pop(top:&Link)->Link {top.as_ref().and_then(|node|node.next.clone())}
fn main(){let v1=push(&None,5);let v2=push(&v1,8);let v3=push(&v1,3);println!("{} {} {}",v2.as_ref().unwrap().value,v3.as_ref().unwrap().value,pop(&v2).unwrap().value);}

8 3 5

Сохранение версий будет эффективным только при совместном использовании неизменяемой памяти. Разберём, какие узлы действительно новые.

def stack_versions(commands):
	# Напишите решение
	pass

Если копировать весь список при каждом push, история из q вставок займёт Θ(q²) памяти. Неизменяемость позволяет избежать этого: версии отличаются верхними узлами и совместно используют уже готовый хвост.

Неизменяемый суффикс списка может использоваться несколькими версиями одновременно. При обновлении перезаписывать такой хвост нельзя: это незаметно изменит прошлые версии.

В общем случае персистентность может потребовать копирования пути к изменяемому месту; именно поэтому простой список со вставкой в середину устроен иначе, чем персистентный стек.

В Python неизменяемый узел может хранить пару (value, next). В Rust тот же общий хвост выражается Rc<Node>: clone у Rc копирует счётчик ссылки, а не всё поддерево. При изменении элемента на глубине k приходится скопировать k узлов пути, поэтому O(1) для push нельзя переносить на произвольное редактирование списка.

Вы умеете сохранять версии стека с общим неизменяемым хвостом. Тонкости очереди при ветвлении — необязательное углубление; к практике списков можно перейти сразу.

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 12 из 12

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

Сравнение уже разобранных структур

Ссылка и поиск — разные затраты

При n = q = 200 000 поиск каждого узла обходом может потребовать до 4·10¹⁰ переходов. O(1) для удаления известного узла не спасёт, если этот узел сначала ищется за O(n). Если вход использует id, оцените отображение id → узел отдельно.

Сколько памяти стоит история

q полных копий растущего списка могут содержать Θ(q²) значений. Для персистентного стека q операций push создают q узлов и O(q) ссылок на вершины версий. Копирование пути длины k стоит O(k), а не O(1).

В Python объект узла имеет служебные поля; в Rust Rc несёт счётчик ссылок. Арена из Vec с целыми индексами компактнее, но без списка свободных ячеек сохраняет даже удалённые узлы. Различайте O(текущего размера) и O(всех выделений).

Границы и версия доказательства

Проверьте удаление головы, хвоста, единственного элемента и повторное заполнение пустой очереди. Для циклического списка проверьте prev/next в обе стороны и сохранность sentinel.

При q ветках из версии с n элементами наивная очередь с повторным разворотом даёт Θ(qn). Нужна конструкция с доказанной работой на всё дерево версий либо офлайн-обход истории с откатами. Рекурсивный обход дерева из 200 000 запросов может переполнить стек: используйте явный стек.

Разминка: найти узел, вставить, развернуть

Повторите поиск узла и вставку после него в главе об односвязном списке, затем разверните цепочку. В этих задачах массив next_node моделирует ссылки: next_node[4]=1 означает «узел #4 ссылается на #1». Это не перестановка значений соседних ячеек. None — отсутствие следующего узла.

def reverse_links(next_node, head):
	# Напишите решение
	pass

Основное применение: Reverse Linked List, Merge Two Sorted Lists и Remove Duplicates. Persistent Bookcase — продвинутое необязательное испытание после освоения версий.

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

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.