Связный список: что это, виды, операции и реализация на Python

Металлическая цепь на столе, одно звено раскрыто Изучение

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

Металлическая цепь на столе, одно звено раскрыто

Что такое связный список

Связный список (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)
Читайте также:  Декораторы Python: как работают, как написать свой и какие есть встроенные

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: без него пришлось бы идти от первого элемента до последнего.

Читайте также:  Регулярные выражения Python: модуль re, синтаксис и примеры

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: от консольной версии до окна на tkinter

Деревянные игрушечные вагоны, сцепленные друг с другом спереди и сзади

Где применяется связный список

Свой связный список в рабочем коде 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 для начинающих.

Оцените статью
bestprogrammer.ru
Добавить комментарий