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

Динамический массив (list, ArrayList, vector) — это один большой блок памяти. Связный список — это много маленьких узлов, каждый знает только своего соседа. Узлы могут лежать в памяти где угодно: указатель связывает их в цепочку.

Базовая структура узла singly linked list:

class Node:
    __slots__ = ('value', 'next')

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

• value — данные узла (что угодно).
• next — указатель на следующий узел, или None если это конец.

Сам список держит только указатель на head — первый узел. Дальше — по next.

Реализация на Python class

Контейнер LinkedList:

class LinkedList:
    __slots__ = ('head',)

    def __init__(self):
        self.head = None

    def push_front(self, value):
        """Вставка в начало — O(1)."""
        self.head = Node(value, next_node=self.head)

    def pop_front(self):
        """Удаление с начала — O(1)."""
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        return node.value

    def find(self, value):
        """Поиск по значению — O(n)."""
        node = self.head
        while node is not None:
            if node.value == value:
                return node
            node = node.next
        return None

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

    def __len__(self):
        # O(n) если не кэшировать
        count = 0
        node = self.head
        while node is not None:
            count += 1
            node = node.next
        return count

Использование:

ll = LinkedList()
ll.push_front(30)
ll.push_front(20)
ll.push_front(10)

print(list(ll))   # [10, 20, 30]
print(ll.pop_front())  # 10
print(list(ll))   # [20, 30]

Сложности операций

Главное про singly linked list — в чём он быстрее и в чём медленнее массива:

Ключевая черта: linked list даёт O(1) на insert/delete, если у вас уже есть указатель на узел. Это полезно для LRU cache, ring buffer с замещением, парсеров. Платим за это потерей O(1) доступа по индексу и плохой cache locality (об этом — в уроке 03 этого модуля).

Зачем нужен указатель на tail

В нашей реализации push_back — это O(n), потому что без указателя на последний узел приходится пройти весь список. Можно добавить tail:

class LinkedListWithTail:
    __slots__ = ('head', 'tail', 'size')

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    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 push_front(self, value):
        node = Node(value, next_node=self.head)
        if self.head is None:
            self.tail = node
        self.head = node
        self.size += 1

Теперь push_back тоже O(1). Но: pop_back всё равно O(n) для singly linked, потому что после удаления tail нужно переставить указатель на предпоследний узел — а до него надо пройти весь список. Чтобы и pop_back был O(1), нужны указатели в обе стороны — doubly linked list (следующий урок).

Почему «singly» иногда хватает

В стандартной библиотеке Python нет встроенного linked list. Обычно его пишут сами для конкретной задачи. Singly linked хватает для:

• Стек (push_front/pop_front как push/pop) — но в Python проще list.append/pop, который тоже O(1) сзади.
• Persistent list в функциональном программировании (Haskell, Erlang). Каждое push_front даёт новый список, разделяющий хвост со старым. Это работает только для singly linked.
• Hash table chaining — внутри bucket’а хранится линейная цепочка коллизий. Это singly linked, разберём в модуле 8.
• Linked stack для парсера или DFS — когда удобно иметь immutable “prev state” указатель.

Для большинства практических задач, где нужен FIFO-доступ с обоих концов, лучше doubly linked или deque.

Память singly linked vs list

В Python каждый Node — отдельный PyObject. Размер:

import sys

class NodeSlots:
    __slots__ = ('value', 'next')
    def __init__(self, v, n):
        self.value = v
        self.next = n

n = NodeSlots(42, None)
print(f"Node (slots):     {sys.getsizeof(n)} bytes + 16 для __slots__ -> ~64 total")

Один узел в Python — 48-80 байт (с PyObject header, ob_refcnt, ob_type, ob_dict если не slots, и поля). Сравните с 8 байтами на указатель в Python list.

Linked list на 1M int = ~64 байт/узел * 1M = ~64 МБ. list на 1M int = ~36 МБ (буфер указателей + PyLongObject).

То есть singly linked в Python примерно вдвое дороже обычного list при том же содержимом. Плюс никакого spatial locality (об этом — урок 03).

Попробуй сам

Реализуйте reverse для singly linked — переверните список in-place за один проход:

class Node:
    __slots__ = ('value', 'next')
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

def reverse(head):
    """In-place reverse за один проход, O(n) время, O(1) дополнительной памяти."""
    prev = None
    curr = head
    while curr is not None:
        next_node = curr.next  # сохраняем хвост
        curr.next = prev        # переворачиваем стрелку
        prev = curr
        curr = next_node
    return prev

# Проверьте
head = build([1, 2, 3, 4, 5])
print(to_list(head))           # [1, 2, 3, 4, 5]
new_head = reverse(head)
print(to_list(new_head))       # [5, 4, 3, 2, 1]

Классическое упражнение. Понимание трёх указателей prev, curr, next_node — фундамент работы со связными списками.