Связный список относится к линейным структурам данных: каждый элемент списка лежит в памяти отдельно и хранит значение и ссылку на следующий. Поэтому вставка и удаление в начале списка стоят O(1), а доступ по индексу стоит O(n): до нужного элемента приходится идти от первого. Код прогнан на 64-битном CPython 3.14.3 под Windows 10.

- Что такое связный список
- Виды: односвязный, двусвязный и кольцевой список
- Односвязный список
- Двусвязный список
- Кольцевой список
- Сложность операций, преимущества и недостатки по сравнению с массивом
- Реализация связного списка на Python
- Двусвязный список на Python
- Где применяется связный список
- Частые вопросы
- Чем связный список лучше массива?
- Как найти цикл в связном списке?
- Можно ли развернуть список рекурсией?
- Зачем писать связный список самому, если есть deque?
Что такое связный список
Связный список (linked list) состоит из узлов (node). Каждый узел содержит два поля: value с данными и next со ссылкой на следующий узел. В Python next хранит ссылку на объект, в C и C++ эту ссылку хранят указателем; дальше «указатель» значит то же, что ссылка. У последнего узла next равен None в Python или null в Java и C#: так программа понимает, что список кончился. Указатель на первый узел хранят в head (голова списка), в реализации ниже есть ещё tail, указатель на хвост списка.
head tail
| |
[10 | next] -> [20 | next] -> [30 | next] -> None
Элементы списка лежат в памяти где угодно, порядок задают только ссылки. Чтобы вставить новый элемент, достаточно переставить пару указателей, остальные элементы списка не сдвигаются. Зато номера у элемента нет: чтобы взять пятый, программа последовательно проходит первые четыре элемента по цепочке next.
Виды: односвязный, двусвязный и кольцевой список
Односвязный список
В односвязном списке у элемента одна ссылка, на следующий. Пройти такой список можно только вперёд, от head к концу. Чтобы удалить элемент из списка, нужно переписать next у предыдущего элемента, а предыдущий находится только обходом списка с начала.
Двусвязный список
В двусвязном списке каждый узел содержит два указателя: next на следующий и prev на предыдущий элемент. Список проходится в обе стороны, а известный узел удаляется за O(1): оба соседа доступны через его поля. Платят за это лишним указателем в каждом узле.
Кольцевой список
В кольцевом (циклическом) списке последний узел указывает не на None, а обратно на первый. Кольцевым бывает и односвязный, и двусвязный список. Обход такого списка останавливают по возврату к стартовому элементу: условие while current здесь не станет ложным никогда.

Сложность операций, преимущества и недостатки по сравнению с массивом
list в Python внутри устроен как динамический массив: непрерывный блок ссылок переменной длины. Односвязный список в таблице хранит head и tail.
| Операция | Односвязный | Двусвязный | list (массив) |
|---|---|---|---|
| Доступ по индексу k | O(n) | O(n) | O(1) |
| Вставка в начало | O(1) | O(1) | O(n) |
| Вставка в конец | O(1), если хранить tail | O(1) | O(1) амортизированно |
| Вставка после известного узла | O(1) | O(1) | O(n — k) |
| Удаление первого элемента | O(1) | O(1) | O(n) |
| Удаление последнего элемента | O(n) | O(1) | O(1) |
| Удаление известного узла | O(n), ищем предыдущий | O(1) | O(n — k) |
| Поиск по значению | O(n) | O(n) | O(n) |
O(1) у вставки и удаления в середине списка честное, только когда узел уже найден. Если задача звучит как «вставить после элемента со значением X» или «удалить пятый элемент», сначала идёт поиск за O(n), затем сама вставка или удаление, и в сумме операция стоит O(n), как у массива.
На нашей машине 100 000 вставок в начало через list.insert(0, x) заняли 5-6 секунд, через push_front из класса ниже около 0,06 секунды, через deque.appendleft около 0,01 секунды. Зато 1000 обращений по индексу у list из 100 000 элементов уложились меньше чем в миллисекунду, а проход по связному списку до тех же индексов занял около 3 секунд.

Ещё один недостаток связного списка касается памяти. Мы замерили через tracemalloc 100 000 элементов без учёта самих значений. Массив [0] * 100_000 тратит на элемент одну ссылку, 8 байт. Узел-объект с двумя полями стоит 88 байт, тот же узел с __slots__ 48 байт. Цифра для list относится к массиву, созданному сразу нужной длины.
Реализация связного списка на Python
Класс Node хранит значение и указатель next, класс LinkedList хранит head и tail. Методы: добавление элемента в начало, в конец и после узла, поиск, удаление по значению, разворот и обход через for.
class Node:
def __init__(self, value, next_node=None):
self.value = value # полезные данные
self.next = next_node # ссылка на следующий узел или None
class LinkedList:
def __init__(self):
self.head = None # первый элемент
self.tail = None # последний элемент
def push_front(self, value): # O(1)
self.head = Node(value, self.head)
if self.tail is None:
self.tail = self.head
def append(self, value): # O(1) благодаря tail
node = Node(value)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
def insert_after(self, prev, value): # O(1), узел уже найден
prev.next = Node(value, prev.next)
if prev is self.tail:
self.tail = prev.next
def find(self, value): # O(n)
current = self.head
while current and current.value != value:
current = current.next
return current
def remove(self, value): # O(n) из-за поиска
prev, current = None, self.head
while current and current.value != value:
prev, current = current, current.next
if current is None:
return False
if prev is None:
self.head = current.next
else:
prev.next = current.next
if current is self.tail:
self.tail = prev
return True
def reverse(self): # O(n), без лишней памяти
prev, current = None, self.head
self.tail = self.head
while current:
next_node = current.next
current.next = prev
prev, current = current, next_node
self.head = prev
def __iter__(self):
current = self.head
while current:
yield current.value
current = current.next
def __str__(self):
return " -> ".join(map(str, self)) + " -> None"
linked = LinkedList()
linked.append(20)
linked.append(30)
linked.push_front(10)
print(linked)
linked.insert_after(linked.find(20), 25)
print(linked)
print(linked.remove(30), linked.remove(99))
linked.reverse()
print(linked, "| head:", linked.head.value, "| tail:", linked.tail.value)
Вывод программы:
10 -> 20 -> 30 -> None
10 -> 20 -> 25 -> 30 -> None
True False
25 -> 20 -> 10 -> None | head: 25 | tail: 10
push_front создаёт новый узел, чей next указывает на прежнюю голову, и делает его новым head. Если список был пуст, этот же элемент становится и tail. append добавляет элемент в конец списка за O(1) только благодаря tail: без него пришлось бы идти от первого элемента до последнего.
find проверяет элементы списка по очереди, начиная с head, пока не встретит нужное значение или None. Не нашёл, значит вернул None, и передать такой результат в insert_after нельзя: упадёт AttributeError: 'NoneType' object has no attribute 'next'. remove разбирает три случая: удаляемый элемент первый (сдвигаем head), в середине (предыдущий элемент начинает ссылаться на следующий за ним, в обход удаляемого) и последний (tail переходит на предыдущий). Для отсутствующего значения метод возвращает False, это второе значение в третьей строке вывода.
Строки про tail в remove легко забыть. Мы убрали их и прогнали append(1), append(2), remove(2), append(3): печать дала 1 -> None. Тройка повисла на удалённом узле, потому что tail по-прежнему указывал на него.
reverse разворачивает список одним проходом с переменными prev, current (текущий узел) и next_node. На каждом шаге элемент начинает указывать назад, а next_node держит ссылку на остаток списка, иначе он потеряется. Бывший первый элемент списка становится tail.

Двусвязный список на Python
Двусвязный список удобен, когда элементы удаляют из середины списка, а ссылку на узел программа получила заранее. Здесь append возвращает созданный узел, и unlink убирает его из списка без обхода.
class Node:
def __init__(self, value):
self.value = value
self.prev = None # предыдущий узел
self.next = None # следующий узел
class DoublyLinkedList:
def __init__(self):
self.head = self.tail = None
def append(self, value):
node = Node(value)
if self.tail is None:
self.head = node
else:
node.prev, self.tail.next = self.tail, node
self.tail = node
return node # пригодится для удаления за O(1)
def unlink(self, node): # O(1), обход не нужен
if node.prev is None:
self.head = node.next
else:
node.prev.next = node.next
if node.next is None:
self.tail = node.prev
else:
node.next.prev = node.prev
def backward(self):
current = self.tail
while current:
yield current.value
current = current.prev
doubly = DoublyLinkedList()
first = doubly.append(10)
middle = doubly.append(20)
last = doubly.append(30)
doubly.unlink(middle)
print(list(doubly.backward()))
doubly.unlink(first)
doubly.unlink(last)
print(doubly.head, doubly.tail)
Вывод программы:
[30, 10]
None None
unlink переписывает указатели соседей. Нет prev, значит элемент был первым, и сдвигается head; нет next, значит последним, и сдвигается tail. После удаления всех трёх элементов список пуст: оба поля равны None. В односвязном списке для обхода с конца, как в backward, пришлось бы сначала развернуть список или сложить значения в другую структуру.

Где применяется связный список
Свой связный список в рабочем коде Python писать незачем. Для очереди и очереди с двумя концами есть collections.deque: в CPython он устроен как двусвязный список блоков по 64 ссылки. Вставка и удаление с обоих краёв стоят O(1), доступ по индексу быстрый у концов и замедляется до O(n) к середине. list.pop(0) и list.insert(0, x) на длинных данных стоят O(n), для очереди их не берите; стеку хватает list.append и list.pop().
Второе применение: LRU-кеш, который выбрасывает давно не использованный элемент. Словарь находит запись по ключу за O(1), а двусвязный список хранит порядок обращений, и элемент из середины переносится в конец без обхода. Так устроены OrderedDict и functools.lru_cache с ограниченным maxsize. Разбор самого декоратора lru_cache есть в статье про декораторы Python. Почему поиск по ключу в словаре стоит O(1), объясняет статья про хеш-таблицу.
from collections import OrderedDict, deque
queue = deque([2, 3])
queue.appendleft(1)
queue.append(4)
print(queue.popleft(), queue.pop(), queue)
cache = OrderedDict(a=1, b=2) # LRU-кеш на два элемента
cache.move_to_end("a") # обратились к "a"
cache["c"] = 3
if len(cache) > 2:
cache.popitem(last=False) # выбросили самый давний
print(list(cache))
Вывод программы:
1 4 deque([2, 3])
['a', 'c']
Обращение к "a" сделало его свежим, поэтому при вставке "c" ушёл "b".
В других языках программирования связный список есть в стандартной библиотеке: LinkedList в Java и C# двусвязный, std::list в C++ обычно реализован как двусвязный, std::forward_list как односвязный.
Частые вопросы
Чем связный список лучше массива?
Вставкой после известного узла и удалением в начале списка: O(1) без сдвига остальных элементов. Удаление известного узла за O(1) даёт только двусвязный список. В доступе по индексу и расходе памяти выигрывает массив, поэтому по умолчанию в Python берут list, а для двух концов deque.
Как найти цикл в связном списке?
Двумя указателями: медленный идёт на один элемент за шаг, быстрый на два. Быстрый дошёл до None, значит цикла нет; указатели встретились на одном узле, значит список зациклен. Обычная печать на таком списке не остановится.
Можно ли развернуть список рекурсией?
Можно, но в Python глубина рекурсии по умолчанию ограничена 1000 вызовами. Рекурсивный разворот списка из 100 000 элементов падает с RecursionError: maximum recursion depth exceeded, а цикл из метода reverse в этот предел не упирается. Как работает цикл while, разобрано в статье про циклы с условием.
Зачем писать связный список самому, если есть deque?
Чтобы понять, как работают указатели: на своём классе видно, что происходит с head, tail и next при вставке, удалении и развороте. Те же приёмы нужны в задачах на алгоритмы и структуры данных, например в развороте связного списка и поиске цикла. Упражнения попроще есть среди задач по Python для начинающих.








