← назад к разделу

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

Обязательно

Узлы и ссылки

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

class Node {
    long data;
    Node next;
}

type Node struct {
	data int64
	next *Node
}

class Node {
  data;
  next = null;
}

class Node:
    __slots__ = ("data", "next")

    def __init__(self, data: int, next: "Node | None" = None) -> None:
        self.data = data
        self.next = next

Тип, поле которого ссылается на значение того же типа, называют самоссылочным. Список хранит только ссылку на первый узел (first); от него по next можно дойти до любого. Последний узел ссылается в «никуда» (null в Java и JavaScript, nil в Go, None в Python) — признак конца списка.

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

Что список делает быстро, а что медленно

  • Вставка в начало — O(1). Создаём узел, его next направляем на бывший первый, а first — на новый. Ничего сдвигать не надо, сколько бы элементов ни было.
  • Удаление из начала — O(1). Просто сдвигаем first на второй узел.
  • Удаление узла из середины — дёшево, если он уже найден: у предыдущего узла заменяют next, «перекидывая» ссылку через удаляемый. Никаких сдвигов.
  • Поиск — O(N). Здесь слабость: чтобы найти элемент по значению или дойти до позиции, идут по цепочке от начала.

У массива быстрый доступ по индексу, но дорогая вставка и удаление; у списка — наоборот.

null 37 45 58 12 first

Создаём узел, его next направляем на бывший первый, а first переносим на новый узел. Ни один элемент не сдвигается — O(1) при любой длине.

Проверим на живом списке. Счётчик hops считает шаги по ссылкам next — работу, которую список делает вместо арифметики по индексу.

живой пример

public class LinkedListDemo {
    static class Node {
        int value; Node next;
        Node(int value, Node next) { this.value = value; this.next = next; }
    }

    static Node first;
    static int hops;

    static Node nodeAt(int index) {
        Node node = first;
        for (int i = 0; i < index; i++) { node = node.next; hops++; }
        return node;
    }

    static void print(String label) {
        StringBuilder chain = new StringBuilder();
        for (Node n = first; n != null; n = n.next) chain.append(n.value).append(" -> ");
        System.out.println(label + chain + "null,  шагов: " + hops);
    }

    public static void main(String[] args) {
        for (int value : new int[] {58, 45, 37, 21, 16}) first = new Node(value, first);
        first = new Node(12, first);
        print("вставка в начало:     ");
        Node before = nodeAt(2);
        before.next = before.next.next;
        print("удаление из середины: ");
        hops = 0;
        for (int i = 0; i < 5; i++) nodeAt(i);
        System.out.println("пять обращений по индексу: " + hops + " шагов");
    }
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

var first *Node
var hops int

func nodeAt(index int) *Node {
	node := first
	for i := 0; i < index; i++ {
		node = node.next
		hops++
	}
	return node
}

func report(label string) {
	chain := ""
	for n := first; n != nil; n = n.next {
		chain += fmt.Sprintf("%d -> ", n.value)
	}
	fmt.Printf("%s%snil,  шагов: %d\n", label, chain, hops)
}

func main() {
	for _, value := range []int{58, 45, 37, 21, 16} {
		first = &Node{value, first}
	}
	first = &Node{12, first}
	report("вставка в начало:     ")
	before := nodeAt(2)
	before.next = before.next.next
	report("удаление из середины: ")
	hops = 0
	for i := 0; i < 5; i++ {
		nodeAt(i)
	}
	fmt.Println("пять обращений по индексу:", hops, "шагов")
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

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

let first = null;
let hops = 0;

function nodeAt(index) {
  let node = first;
  for (let i = 0; i < index; i++) {
    node = node.next;
    hops++;
  }
  return node;
}

function report(label) {
  let chain = "";
  for (let n = first; n !== null; n = n.next) chain += `${n.value} -> `;
  console.log(`${label}${chain}null,  шагов: ${hops}`);
}

for (const value of [58, 45, 37, 21, 16]) first = new Node(value, first);
first = new Node(12, first);
report("вставка в начало:     ");
const before = nodeAt(2);
before.next = before.next.next;
report("удаление из середины: ");
hops = 0;
for (let i = 0; i < 5; i++) nodeAt(i);
console.log(`пять обращений по индексу: ${hops} шагов`);
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

class Node:
    def __init__(self, value: int, next: "Node | None") -> None:
        self.value = value
        self.next = next


first = None
hops = 0


def node_at(index: int) -> Node:
    global hops
    node = first
    for _ in range(index):
        node = node.next
        hops += 1
    return node


def report(label: str) -> None:
    chain = ""
    n = first
    while n is not None:
        chain += f"{n.value} -> "
        n = n.next
    print(f"{label}{chain}None,  шагов: {hops}")


for value in (58, 45, 37, 21, 16):
    first = Node(value, first)
first = Node(12, first)
report("вставка в начало:     ")
before = node_at(2)
before.next = before.next.next
report("удаление из середины: ")
hops = 0
for i in range(5):
    node_at(i)
print(f"пять обращений по индексу: {hops} шагов")
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

Вставка в начало не стоила ни одного шага. Удаление из середины потребовало двух — дойти до предшественника, перецепка ссылки бесплатна. Пять обращений по индексу обошлись в десять шагов: каждое начинается заново от начала.

В коде выше есть неудобство, которое растёт с каждой операцией: пустой список и вставка в самое начало это особые случаи, у них нет предшественника, и каждый метод начинает с проверки, что список пуст. Приём против этого называется фиктивной головой (sentinel): заводят пустой узел-заглушку, на который first указывает всегда, а настоящие данные начинаются с first.next. Тогда у любого узла есть предшественник, вставка и удаление пишутся одной веткой, и проверок на пустоту нет. Дальше по разделу тот же приём встретится в префиксных суммах, где лишний нулевой элемент убирает особый случай для отрезка с начала.

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

Node reverse(Node head) {
    Node prev = null;
    while (head != null) {
        Node next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

func reverse(head *Node) *Node {
	var prev *Node
	for head != nil {
		next := head.next
		head.next = prev
		prev = head
		head = next
	}
	return prev
}

function reverse(head) {
  let prev = null;
  while (head !== null) {
    const next = head.next;
    head.next = prev;
    prev = head;
    head = next;
  }
  return prev;
}

def reverse(head):
    prev = None
    while head is not None:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

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

Двусвязный список

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

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

Список как основа для других структур

Стек и очередь можно построить не на массиве, а на списке: push/pop стека — это вставка/удаление в начале списка, обе O(1). Преимущество — не нужно заранее знать размер: список растёт по мере надобности.

Здесь всплывает абстрактный тип данных (ADT): стек определяется не тем, как он устроен внутри, а тем, что умеет — push, pop, peek. А внутри может быть массив или список, пользователю всё равно. Поведение описано отдельно от реализации, поэтому внутреннее устройство меняют, не трогая код вокруг.

Ещё список можно держать отсортированным: новый элемент вставляют не в начало, а на нужное по порядку место. При этом:

  • вставка становится O(N) (надо пройти до места вставки), но по-прежнему без сдвигов — только перекинуть пару ссылок;
  • минимальный (или максимальный) элемент всегда в начале, его выемка мгновенна.

Сортированный список удобен как простая приоритетная очередь.

Итераторы

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

В Java эта роль разделена надвое. Обычный Iterator умеет только идти вперёд (hasNext, next) и убрать то, на чём стоит (remove) — вставлять он не может. Всё остальное живёт в его расширенной версии ListIterator: add вставляет прямо в текущую позицию, set заменяет элемент, а previous двигает палец назад. Берут его у списка методом listIterator():

ListIterator<String> it = names.listIterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.isBlank()) {
        it.remove();
    } else {
        it.set(name.trim());
    }
}

Удалить или вставить прямо во время обхода через names.remove(...) нельзя: список бросит ConcurrentModificationException; итератор это единственный законный способ менять список на ходу.

В Go у списка container/list роль итератора играет сам узел, *list.Element: у него есть Next() и Prev(), а вставлять и удалять «здесь» умеет список по указателю на узел: l.InsertBefore(v, e), l.InsertAfter(v, e), l.Remove(e), всё за O(1). Обход пишут обычным циклом:

for e := names.Front(); e != nil; {
	next := e.Next()
	name := e.Value.(string)
	if strings.TrimSpace(name) == "" {
		names.Remove(e)
	} else {
		e.Value = strings.TrimSpace(name)
	}
	e = next
}

Строка next := e.Next() до удаления обязательна: Remove обнуляет ссылки удалённого узла, и e.Next() после него вернёт nil, обход молча оборвётся на первом пустом имени. Исключения, как в Java, здесь не будет, поэтому ошибка тише. С Go 1.23 в языке появились и настоящие итераторы, функции вида iter.Seq[T], по которым работает for range; у среза они называются slices.All и slices.Values, а для своего списка такую функцию пишут сами.

В JavaScript итератор это протокол, а не класс: у объекта есть метод [Symbol.iterator](), который возвращает объект с методом next(), а тот отдаёт пары { value, done }. По такому протоколу работают for...of, оператор ... и Array.from. Удалять и вставлять через итератор нельзя, он умеет только идти вперёд; поэтому для своего списка проще всего написать генератор, а менять список отдельными методами по ссылке на узел:

class LinkedList {
  head = null;

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

const cleaned = [...names].map((n) => n.trim()).filter((n) => n !== "");

Менять массив прямо во время for...of тоже опасно, но по-другому: исключения не будет, а splice сдвинет соседей, и следующий элемент цикл перепрыгнет. Поэтому в JavaScript чаще строят новый массив через map и filter, чем правят старый на ходу.

В Python итератор это протокол: у объекта есть __iter__, который возвращает итератор, а у того __next__, который отдаёт следующее значение или бросает StopIteration. По нему работают for, распаковка и list(...). Удалять и вставлять через итератор нельзя, он умеет только идти вперёд; для своего списка итератор проще всего написать генератором, а менять список отдельными методами по ссылке на узел:

class LinkedList:
    def __init__(self) -> None:
        self.head = None

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node.value
            node = node.next


cleaned = [n.strip() for n in names if n.strip()]

Менять list или deque прямо во время обхода тоже нельзя: list.remove внутри for молча пропускает соседа удалённого, а deque бросает RuntimeError: deque mutated during iteration. Поэтому в Python строят новый список включением, как выше, или обходят копию for n in list(names):.

Как это сделано в стандартной библиотеке

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

Эталонная реализация — LinkedList. Внутри ровно то, что мы разбирали, в двусвязном варианте: узел с полями item, next и prev, а сам класс держит ссылки на первый и последний узлы. Поэтому он честно делает всё, что обещает теория: добавить или убрать элемент с любого конца — O(1) при любой длине. Он же реализует интерфейс Deque, то есть годится и как стек, и как очередь.

Дальше оговорки. get(i) — O(N): индексов у узлов нет, надо шагать по ссылкам (LinkedList идёт с ближнего конца, но это делит работу пополам, а не меняет порядок роста). remove(i) и add(i, v) — тоже O(N): до места сначала надо дойти. O(1) остаётся у перецепки ссылок, а не у операции целиком.

По таблице сложностей LinkedList должен обыгрывать ArrayList на вставках и удалениях в середине — на практике он проигрывает почти всегда. Причина в железе. Элементы ArrayList лежат в памяти подряд: процессор подтягивает их в кеш пачками, а сдвиг делает одной операцией копирования памяти. Узлы LinkedList разбросаны по куче, каждый шаг по next — прыжок в непредсказуемое место, промах кеша и ожидание памяти. Плюс узел — отдельный объект с тремя ссылками и заголовком: около 24 байт на узел (заголовок 12 байт и три ссылки по четыре) сверх самого значения, которое тоже отдельный объект. У ArrayList<Integer> на элемент уходит ссылка в 4 байта плюс объект Integer в 16, у int[] четыре байта на всё. То есть миллион чисел это 4 МБ в массиве, около 20 МБ в ArrayList<Integer> и около 40 МБ в LinkedList<Integer>. В итоге линейный сдвиг выходит дешевле, чем «бесплатная» перецепка после долгой прогулки по ссылкам.

Практический вывод простой: по умолчанию берут ArrayList, а если нужны стек или очередь — ArrayDeque, а не LinkedList.

Грабля напоследок — обход по индексу:

// так не надо
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

// так надо
for (Long value : list) {
    process(value);
}

На ArrayList первый цикл O(N), на LinkedList — O(N²): каждый get идёт от края по ссылкам. На сотне элементов разницы не видно, на сотне тысяч цикл встаёт намертво. for-each и итератор двигаются по next на один шаг, а не отсчитывают путь заново от края.

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

Внутри list.List ровно то, что мы разбирали, в двусвязном варианте: узел Element с полями next, prev, ссылкой на список и значением Value, а сам список держит кольцо с фиктивной головой. Поэтому он честно делает всё, что обещает теория: PushFront, PushBack, InsertBefore, InsertAfter и Remove по указателю на узел — O(1) при любой длине. Он годится и как стек, и как очередь, и как дек.

Дальше оговорки. Доступа по индексу у него нет вовсе, даже медленного: до нужного узла шагают циклом от Front() или Back(), и это O(N). Значение хранится как any: при чтении нужно утверждение типа e.Value.(string), компилятор ничего не проверяет, а число или структура при укладке в any упаковываются в отдельный объект в куче.

По таблице сложностей список должен обыгрывать срез на вставках и удалениях в середине — на практике он проигрывает почти всегда. Причина в железе. Элементы среза лежат в памяти подряд: процессор подтягивает их в кеш пачками, а сдвиг copy делает одной операцией копирования памяти. Узлы списка разбросаны по куче, каждый шаг по next — прыжок в непредсказуемое место, промах кеша и ожидание памяти. Плюс узел — отдельный объект: три указателя и интерфейс из двух слов, 40 байт на узел сверх самого значения, которое в any тоже лежит отдельно. То есть миллион чисел это 8 МБ в []int и около 60 МБ в container/list, да ещё столько же объектов для сборщика мусора. В итоге линейный сдвиг выходит дешевле, чем «бесплатная» перецепка после долгой прогулки по ссылкам.

Практический вывод простой: по умолчанию берут срез, а если нужны стек или очередь — срез или канал, а не container/list. Список остаётся для редкого случая, когда на узлы держат указатели снаружи и удаляют их по этим указателям, как в кеше с вытеснением давно не использованного.

Грабля напоследок — удаление во время обхода:

// так не надо
for e := l.Front(); e != nil; e = e.Next() {
	if stale(e.Value) {
		l.Remove(e) // после Remove e.Next() вернёт nil, обход оборвётся
	}
}

// так надо
for e := l.Front(); e != nil; {
	next := e.Next()
	if stale(e.Value) {
		l.Remove(e)
	}
	e = next
}

Remove обнуляет ссылки у удалённого узла, чтобы он не держал соседей для сборщика мусора, и первый цикл молча останавливается на первом же удалении: исключения, как в Java, не будет, просто часть списка останется необработанной.

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

Написать список несложно: класс Node с value, next и, для двусвязного, prev, класс списка с head и tail. Тогда он честно делает всё, что обещает теория: добавить или убрать узел с любого конца — O(1) при любой длине, и по ссылке на узел вставить или удалить в середине тоже O(1).

Дальше оговорки. Доступа по индексу нет: до нужного узла шагают по next, и это O(N). Итератор пишут сами через [Symbol.iterator], иначе for...of по списку не пройдёт.

По таблице сложностей список должен обыгрывать Array на вставках и удалениях в середине — на практике он проигрывает почти всегда. Причина в железе. Элементы массива лежат в памяти подряд: процессор подтягивает их в кеш пачками, а сдвиг в splice делает одной операцией копирования памяти. Узлы списка разбросаны по куче, каждый шаг по next — прыжок в непредсказуемое место, промах кеша и ожидание памяти. Плюс узел — отдельный объект движка V8 с заголовком и полями: десятки байт на узел сверх самого значения. Массив из одних целых V8 хранит плотно, по четыре или восемь байт на число; список из миллиона узлов это десятки мегабайт и миллион объектов для сборщика мусора. В итоге линейный сдвиг выходит дешевле, чем «бесплатная» перецепка после долгой прогулки по ссылкам.

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

Грабля напоследок — обход по индексу:

// так не надо
for (let i = 0; i < list.size; i++) {
  process(list.get(i));
}

// так надо
for (const value of list) {
  process(value);
}

На массиве первый цикл O(N), на списке — O(N²): каждый get идёт от головы по ссылкам. На сотне элементов разницы не видно, на сотне тысяч цикл встаёт намертво. for...of двигается по next на один шаг, а не отсчитывает путь заново от края.

Классического связного списка в стандартной библиотеке Python нет, ближайший родственник — collections.deque. И именно здесь чаще всего выбирают структуру по таблице сложностей и промахиваются.

Внутри deque не цепочка одиночных узлов, а двусвязный список блоков по 64 указателя: концы дёшевы, append, appendleft, pop и popleft — O(1) при любой длине, а память растёт и освобождается блоками. Он годится и как стек, и как очередь, и как дек.

Дальше оговорки. d[i] — O(N): индексов у блоков нет, надо шагать по цепочке (deque идёт с ближнего конца, но это делит работу пополам, а не меняет порядок роста). insert(i, v) и del d[i] в середину — тоже O(N): до места сначала надо дойти, а потом сдвинуть элементы внутри блоков. Вставка «по ссылке на узел» за O(1), как в учебном списке, здесь невозможна вовсе: узлы наружу не отдаются.

По таблице сложностей учебный список должен обыгрывать list на вставках и удалениях в середине — на практике он проигрывает почти всегда. Причина в железе. Элементы list лежат в памяти подряд: процессор подтягивает их в кеш пачками, а сдвиг делает одной операцией копирования памяти. Узлы самодельного списка разбросаны по куче, каждый шаг по next — прыжок в непредсказуемое место, промах кеша и ожидание памяти. Плюс узел — отдельный объект Python: с __slots__ около 56 байт, без них ещё словарь атрибутов, сверх самого значения, которое тоже отдельный объект по 28 байт на небольшое число. То есть миллион чисел это 8 МБ ссылок плюс 28 МБ объектов int в list и вдвое-втрое больше в самодельном списке. В итоге линейный сдвиг выходит дешевле, чем «бесплатная» перецепка после долгой прогулки по ссылкам.

Практический вывод простой: по умолчанию берут list, для стека тоже list, для очереди и дека — deque, а свой список пишут только в учебных целях или когда нужны ссылки на узлы снаружи, как в кеше с вытеснением давно не использованного; и там обычно берут OrderedDict с move_to_end, у которого это уже сделано.

Грабля напоследок — обход по индексу:

# так не надо
for i in range(len(d)):
    process(d[i])

# так надо
for value in d:
    process(value)

На list первый цикл O(N), на deque — O(N²): каждый d[i] идёт от края по блокам. На сотне элементов разницы не видно, на сотне тысяч цикл встаёт намертво. Обычный for двигается на один шаг, а не отсчитывает путь заново от края.

Дополнительно: при первом чтении можно пропустить

Глубже: цикл в списке: быстрый и медленный указательрасширенное

Связный список может замкнуться сам на себя: последний узел ссылается на один из предыдущих. Обход такого списка не заканчивается никогда, а память под «посещённые» узлы тратить не хочется. Приём Флойда обходится двумя указателями: медленный шагает на один узел, быстрый на два. Если цикла нет, быстрый упрётся в конец списка; если есть, оба крутятся по кольцу, и быстрый рано или поздно догонит медленного.

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

func hasCycle(head *Node) bool {
	slow, fast := head, head
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next
		if slow == fast {
			return true
		}
	}
	return false
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

def has_cycle(head) -> bool:
    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

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

Коротко

  • Связанный список — цепочка узлов; каждый хранит данные и ссылку на следующий. Держится на связях, а не на позициях.
  • Вставка и удаление в начале — O(1), без сдвигов и без заранее заданного размера. Поиск — O(N): надо идти по цепочке.
  • Двусвязный список добавляет ссылку на предыдущий узел — обход в обе стороны, удобная основа для дека.
  • Список — основа для стека и очереди; отсюда ADT: структура определяется поведением, а не внутренним устройством.
  • Сортированный список держит элементы по порядку; итератор даёт контролируемый доступ к середине.
  • Кольцо в списке или цепочке ссылок ищут быстрым и медленным указателем: O(N) времени, O(1) памяти.
  • Фиктивная голова убирает особые случаи пустого списка и вставки в начало; разворот списка перецепляет next назад за один проход с тремя ссылками.
  • В Java по умолчанию берут ArrayList, для стека и очереди — ArrayDeque: разбросанные узлы LinkedList проигрывают кешу процессора.
  • Память: узел LinkedList около 24 байт плюс объект-значение; миллион чисел это 4 МБ в int[], около 20 в ArrayList<Integer> и около 40 в LinkedList.
  • В Go по умолчанию берут срез, для стека и очереди — срез или канал: разбросанные узлы container/list проигрывают кешу процессора, а Value там any.
  • Память: узел container/list около 40 байт плюс упакованное значение; миллион чисел это 8 МБ в []int и около 60 МБ в списке. При удалении во время обхода Next() берут до Remove.
  • В JavaScript списка в языке нет, по умолчанию берут Array, для очереди — индекс головы, кольцо или denque: узлы самодельного списка проигрывают кешу процессора.
  • Итератор для своего списка пишут через [Symbol.iterator] и генератор; обход по индексу через get(i) квадратичен.
  • В Python по умолчанию берут list, для очереди и дека — collections.deque: внутри у него блоки по 64 элемента, концы O(1), середина O(N).
  • Память: узел самодельного списка около 56 байт даже со __slots__ плюс объект int на 28 байт; for i in range(len(d)): d[i] на деке квадратичен.

Что почитать дальше