Список как структура данных: связный список, отличие от массива и list в Python
Структура данных список простыми словами: односвязный и двусвязный связный список, чем список отличается от массива, сложность операций и как устроен list в Python.
Коротко
- Список — это упорядоченная последовательность элементов, в которую можно добавлять и из которой можно удалять. Это описание поведения, а не устройства.
- Реализуют список двумя способами: на массиве (элементы лежат в памяти подряд) и на связном списке (элементы разбросаны по памяти и связаны ссылками).
- Связный список бывает односвязным (ссылка только на следующий узел) и двусвязным (ссылки на следующий и на предыдущий).
- Массив выигрывает в доступе по индексу — O(1) против O(n). Связный список выигрывает во вставке и удалении, когда нужное место уже найдено, — O(1) против O(n).
listв Python — это динамический массив, а не связный список. Ближайший родственник связного списка в стандартной библиотеке —collections.deque.
| Операция | Массив (list в Python) | Односвязный список | Двусвязный список |
|---|---|---|---|
| Доступ по индексу | O(1) | O(n) | O(n) |
| Поиск по значению | O(n) | O(n) | O(n) |
| Вставка в начало | O(n) | O(1) | O(1) |
| Вставка в конец | O(1) амортизированно | O(1) с tail | O(1) |
| Вставка после известного узла | O(n) | O(1) | O(1) |
| Удаление узла по ссылке на него | O(n) | O(n) | O(1) |
Если запись O(n) пока ни о чём не говорит, начните со статьи про Big O, а потом возвращайтесь.
Что такое список
Слово «список» в программировании используют в двух смыслах, и из-за этого начинается путаница.
Список как абстракция. Это договорённость о поведении: элементы стоят в определённом порядке, у каждого есть позиция, можно вставить элемент, удалить, пройти по всем по очереди. Как именно это хранится в памяти, абстракция не говорит.
Список как конкретная структура. Обычно имеют в виду связный список — цепочку узлов, соединённых ссылками. Когда на собеседовании говорят «дан список, разверните его», речь именно о нём.
Отсюда и вечный вопрос «чем список отличается от массива». Честный ответ: массив — один из способов сделать список. А сравнивать имеет смысл две реализации — массив и связный список. Этим дальше и займёмся.
Список вместе с массивом, стеком и очередью относят к линейным структурам данных: у каждого элемента не больше одного соседа слева и одного справа. Как эти структуры соотносятся с деревьями, графами и хеш-таблицами, показано в обзоре структур данных.
Как устроен связный список
Массив — это сплошной кусок памяти: элементы стоят вплотную друг к другу, как дома на одной улице. Зная адрес первого и номер нужного, адрес любого вычисляется одним умножением.
Связный список устроен иначе. Каждый элемент живёт в отдельном узле, а узлы лежат в памяти где придётся. Чтобы цепочка не рассыпалась, каждый узел хранит две вещи: значение и ссылку на следующий узел.
head
↓
[10 | •] → [20 | •] → [30 | •] → None
Похоже на квест с записками: в каждой записке написано, где лежит следующая. Попасть сразу на пятую нельзя — придётся пройти первые четыре.
У списка есть голова (head) — ссылка на первый узел. Через неё доступно всё остальное. Последний узел ссылается на None: это признак конца.
На Python узел — это класс из двух полей:
class Node: def __init__(self, value, next=None): self.value = value self.next = next # собираем список 10 -> 20 -> 30 вручную head = Node(10, Node(20, Node(30))) current = head while current is not None: print(current.value) # 10, 20, 30 current = current.next
Цикл while current is not None с шагом current = current.next — основа всего. Почти любая операция со связным списком — это такой обход с небольшими добавками.
Односвязный список: реализация на Python
Соберём полноценный класс. Кроме головы будем хранить хвост (tail) — ссылку на последний узел. Без неё вставка в конец требовала бы обхода всего списка.
class LinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def __len__(self): return self.size def __iter__(self): current = self.head while current is not None: yield current.value current = current.next def push_front(self, value): """Вставка в начало: O(1).""" self.head = Node(value, self.head) if self.tail is None: # список был пуст self.tail = self.head self.size += 1 def push_back(self, value): """Вставка в конец: O(1), потому что храним tail.""" node = Node(value) if self.tail is None: self.head = self.tail = node else: self.tail.next = node self.tail = node self.size += 1 def find(self, value): """Поиск по значению: O(n).""" current = self.head while current is not None: if current.value == value: return current current = current.next return None def get(self, index): """Доступ по индексу: O(n), идём от головы.""" if not 0 <= index < self.size: raise IndexError('индекс вне списка') current = self.head for _ in range(index): current = current.next return current.value def insert_after(self, node, value): """Вставка после известного узла: O(1).""" node.next = Node(value, node.next) if node is self.tail: self.tail = node.next self.size += 1 def pop_front(self): """Удаление из начала: O(1).""" if self.head is None: raise IndexError('список пуст') node = self.head self.head = node.next if self.head is None: # удалили последний узел self.tail = None self.size -= 1 return node.value def remove(self, value): """Удаление по значению: O(n) на поиск + O(1) на перестановку ссылки.""" prev, current = None, self.head while current is not None 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 self.size -= 1 return True
Проверяем:
lst = LinkedList() lst.push_back(20) lst.push_back(30) lst.push_front(10) print(list(lst)) # [10, 20, 30] lst.insert_after(lst.find(20), 25) print(list(lst)) # [10, 20, 25, 30] lst.remove(20) print(list(lst), len(lst)) # [10, 25, 30] 3 print(lst.get(1)) # 25 print(lst.pop_front()) # 10 print(list(lst)) # [25, 30]
Операции и их сложность
Разберём, откуда берётся каждая цифра из таблицы.
Вставка: O(1), если место известно
Вставить узел после данного — значит поменять две ссылки. Никакие другие элементы не двигаются.
Было: [20 | •] ───────────→ [30 | •]
Стало: [20 | •] → [25 | •] → [30 | •]
В коде это одна строка: node.next = Node(value, node.next). Новый узел сначала запоминает старого соседа, и только потом на него переключается ссылка предыдущего. Порядок важен: если сначала перезаписать node.next, хвост списка потеряется.
Сравните с массивом: чтобы вставить элемент в середину, нужно сдвинуть вправо всё, что стоит после, — это O(n).
Доступ по индексу: O(n)
У узлов нет номеров, и адрес пятого элемента не вычислить. Метод get честно делает index шагов от головы. Поэтому цикл вида for i in range(len(lst)): lst.get(i) работает за O(n²) — классическая ловушка для тех, кто привык к массивам. По связному списку ходят итератором, а не по индексам.
Поиск: O(n)
Тут паритет с массивом: и там, и там в худшем случае придётся просмотреть всё. Но в отсортированном массиве можно искать бинарным поиском за O(log n), а в связном списке нельзя — нет быстрого прыжка в середину. Эту проблему решает список с пропусками, надстройка из нескольких уровней ссылок.
Удаление: всё упирается в предыдущий узел
Чтобы убрать узел, нужно перенаправить ссылку предыдущего узла в обход удаляемого. В односвязном списке назад пути нет, поэтому remove тащит за собой переменную prev.
Отсюда важная оговорка. Фразу «удаление из связного списка — O(1)» часто понимают неправильно. O(1) стоит только перестановка ссылок. Найти узел по значению — O(n). И даже если ссылка на узел уже есть, в односвязном списке ещё нужен его предшественник, а это снова обход.
Исключение — голова: у первого узла предшественника нет, так что pop_front всегда O(1). А вот удаление из конца односвязного списка — O(n) даже при наличии tail: чтобы передвинуть хвост на один узел назад, до этого узла надо дойти от головы.
Двусвязный список
Проблему с предыдущим узлом решают в лоб: каждому узлу добавляют вторую ссылку — назад.
None ← [10] ⇄ [20] ⇄ [30] → None
head tail
Теперь любой узел знает обоих соседей, и вырезать его из цепочки можно, не обходя список:
class DNode: def __init__(self, value): self.value = value self.prev = None self.next = None def unlink(node): """Вырезать узел из середины двусвязного списка за O(1).""" node.prev.next = node.next node.next.prev = node.prev a, b, c = DNode(1), DNode(2), DNode(3) a.next, b.prev = b, a b.next, c.prev = c, b unlink(b) print(a.next.value, c.prev.value) # 3 1
Что даёт вторая ссылка:
- удаление узла по ссылке на него — O(1);
- удаление из конца — O(1);
- обход в обе стороны.
Цена — лишний указатель в каждом узле и вдвое больше ссылок, которые надо не забыть обновить. Функция unlink выше сломается на первом и последнем узле, где prev или next равны None. Как закрыть эти случаи фиктивными узлами и собрать на двусвязном списке LRU-кэш, разобрано в отдельной статье про двусвязный список.
Бывают ещё кольцевые списки: последний узел ссылается на первый. Они удобны для задач «по кругу» — например, чтобы по очереди раздавать процессорное время задачам.
Список и массив: в чём отличие
Асимптотика — только половина картины. Вторая половина — как структура лежит в памяти.
| Массив | Связный список | |
|---|---|---|
| Расположение в памяти | один сплошной блок | узлы разбросаны |
| Доступ по индексу | O(1) | O(n) |
| Вставка и удаление | O(n) из-за сдвига | O(1) при известном месте |
| Рост | иногда копирует всё в новый блок | добавляет по одному узлу |
| Накладные расходы памяти | небольшой запас ёмкости | ссылка (или две) на каждый узел |
| Дружба с кешем процессора | хорошая | плохая |
Память. В связном списке за каждый элемент приходится платить: кроме значения узел хранит ссылку, а в Python ещё и служебные поля объекта. На моей машине (CPython 3.9, 64 бита) один элемент в list занимает 8 байт под ссылку, а узел Node из примера выше — около 150 байт вместе со своим словарём атрибутов. Точные числа зависят от версии интерпретатора, порядок разницы — нет.
Кеш процессора. Процессор читает память блоками и заранее подгружает соседние ячейки. Элементы массива лежат рядом, и обход идёт по уже подгруженным данным. Узлы списка разбросаны, каждый переход по ссылке — прыжок в новое место. Поэтому даже простой обход связного списка заметно медленнее обхода массива, хотя у обоих O(n). У меня сумма миллиона чисел по самодельному списку считалась примерно в 2,5 раза дольше, чем по list.
Рост. У массива фиксированный размер. Когда место кончается, динамический массив выделяет блок побольше и копирует туда всё содержимое. Это редкая, но дорогая операция. Связный список растёт ровно, без таких пауз.
Практический вывод простой: по умолчанию берите массив. Связный список оправдан, когда вы постоянно вставляете и удаляете элементы в начале или в середине, имея под рукой ссылку на нужное место.
Список в Python
Тип называется list, но внутри это не связный список, а динамический массив ссылок на объекты. Отсюда всё его поведение:
nums[i]— O(1);nums.append(x)— O(1) амортизированно;nums.insert(0, x)иnums.pop(0)— O(n), потому что сдвигаются все элементы;x in nums— O(n).
То, что это массив с запасом ёмкости, видно невооружённым глазом:
import sys nums = [1, 2, 3] print(nums[1]) # 2 — доступ по индексу за O(1) sizes = [] for _ in range(20): nums.append(0) size = sys.getsizeof(nums) if not sizes or sizes[-1] != size: sizes.append(size) print(sizes) # размер растёт ступеньками, а не на каждом append
У меня вывелось [120, 184, 248]: за двадцать добавлений память выделялась всего три раза. Конкретные числа в вашей версии Python могут отличаться, но ступеньки останутся.
deque — когда нужны оба конца
Отдельного класса «связный список» в стандартной библиотеке Python нет. Самое близкое — collections.deque: в CPython это двусвязный список из блоков фиксированного размера. Он добавляет и удаляет элементы с обоих концов за O(1).
from collections import deque queue = deque([1, 2, 3]) queue.append(4) # в конец queue.appendleft(0) # в начало print(queue.popleft()) # 0 print(queue.pop()) # 4 print(queue) # deque([1, 2, 3])
Разницу легко измерить. Вставим сто тысяч элементов в начало:
from collections import deque from timeit import timeit N = 100_000 def fill_list(): data = [] for i in range(N): data.insert(0, i) # каждый раз сдвигаем все элементы def fill_deque(): data = deque() for i in range(N): data.appendleft(i) # просто дописываем слева print(f'list.insert(0, x): {timeit(fill_list, number=1):.3f} с') print(f'deque.appendleft: {timeit(fill_deque, number=1):.3f} с')
На моём ноутбуке получилось 1,372 с против 0,004 с — разница в сотни раз, и с ростом N она только увеличивается.
У deque есть и обратная сторона: доступ к элементу в середине по индексу у него O(n), а не O(1). Так что это замена списку для очереди, а не для всего подряд. Для стека хватает и обычного list: append и pop работают с концом массива.
Когда что выбирать
Массив (list) — почти всегда. Нужен доступ по индексу, сортировка, бинарный поиск, срезы, добавление в конец.
deque — если добавляете и забираете элементы с обоих концов: очереди, обход графа в ширину, скользящее окно.
Самодельный связный список — редко, но метко:
- LRU-кэш: хеш-таблица хранит ссылки на узлы двусвязного списка, и перемещение элемента в начало стоит O(1);
- структуры, где элемент должен уметь удалить себя сам, не зная своей позиции;
- цепочки в хеш-таблицах, списки смежности в графах;
- низкоуровневый код, где нельзя позволить себе паузу на копирование всего массива.
И, конечно, собеседования — там связный список встречается гораздо чаще, чем в рабочем коде.
Частые ошибки
Потерянный хвост. При вставке сначала перезаписали node.next, а потом спохватились, что старое значение было нужно. Всё, что шло дальше, недостижимо. Сначала настраивайте ссылки нового узла, потом — соседей.
Обращение к None. current.next.value падает, когда current — последний узел. Перед каждым шагом через две ссылки проверяйте обе.
Забытые краевые случаи. Пустой список, список из одного узла, операция над головой или хвостом. Если код работает на 10 → 20 → 30, это ещё ничего не значит — проверьте его на списке из нуля и одного элемента.
Необновлённый tail или size. Удалили последний узел, а хвост всё ещё на него указывает. Следующий push_back допишет элемент в никуда.
Обход по индексам. for i in range(len(lst)): lst.get(i) превращает линейный проход в квадратичный.
Вера в то, что list — это связный список. Из-за неё пишут nums.insert(0, x) в цикле и удивляются, почему программа на большом входе работает минутами.
На собеседованиях
Связный список любят за то, что на нём сразу видно, умеет ли кандидат аккуратно работать со ссылками и краевыми случаями. Теоретические вопросы обычно такие: чем список отличается от массива, какая сложность у вставки и почему, как устроен list в Python. Ответы на все три — выше.
Задачи начинаются с трёх классических:
- разворот списка — проверка, что вы не теряете ссылки при перестановке;
- поиск цикла — быстрый и медленный указатели;
- слияние двух отсортированных списков — фиктивный узел перед головой.
Приёмы, на которых держатся почти все такие задачи, собраны в статье «Задачи на связные списки». Попробовать руками можно прямо на сайте: разворот, слияние, цикл.
Что запомнить
- Список — это поведение: упорядоченная последовательность со вставкой и удалением. Массив и связный список — два способа его реализовать.
- Связный список состоит из узлов; каждый хранит значение и ссылку на следующий, а в двусвязном — ещё и на предыдущий.
- Доступ по индексу в связном списке — O(n), вставка и удаление при известном месте — O(1).
- В односвязном списке для удаления нужен предыдущий узел; двусвязный снимает это ограничение ценой лишней ссылки.
- Массив компактнее и быстрее на обходе из-за кеша процессора, поэтому он — выбор по умолчанию.
listв Python — динамический массив. Для быстрых операций с обоих концов естьcollections.deque.