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

# Связанный список (Linked List) в Python

Связанный список — это линейная структура данных, в которой элементы (узлы) связаны друг с другом через указатели. Каждый узел содержит данные и ссылку на следующий узел.

Структура связанного списка

Отличие от массива:

Массив:
┌─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │  4  │  Данные в памяти рядом
└─────┴─────┴─────┴─────┘

Связанный список:
голова → [1 | ●]──→ [2 | ●]──→ [3 | ●]──→ [4 | None]
          данные   указатель на следующий

Реализация узла

class Node:
    def __init__(self, data):
        self.data = data        # значение узла
        self.next = None        # указатель на следующий узел

# Создание узлов
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

# Связывание узлов
node1.next = node2
node2.next = node3

# Теперь у нас есть список: 10 -> 20 -> 30 -> None

Простой связанный список

class LinkedList:
    def __init__(self):
        self.head = None  # ссылка на первый узел
    
    def append(self, data):
        """Добавить элемент в конец списка"""
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            return
        
        # найти последний узел
        current = self.head
        while current.next:
            current = current.next
        
        # присоединить новый узел
        current.next = new_node
    
    def prepend(self, data):
        """Добавить элемент в начало списка"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def display(self):
        """Вывести все элементы"""
        elements = []
        current = self.head
        
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(' -> '.join(elements) + ' -> None')
    
    def insert_after(self, prev_data, data):
        """Вставить элемент после элемента с prev_data"""
        current = self.head
        
        while current and current.data != prev_data:
            current = current.next
        
        if not current:
            print(f"Элемент {prev_data} не найден")
            return
        
        new_node = Node(data)
        new_node.next = current.next
        current.next = new_node
    
    def delete(self, data):
        """Удалить элемент из списка"""
        if not self.head:
            return
        
        # удаляем голову
        if self.head.data == data:
            self.head = self.head.next
            return
        
        # ищем элемент
        current = self.head
        while current.next and current.next.data != data:
            current = current.next
        
        if current.next:
            current.next = current.next.next
    
    def search(self, data):
        """Поиск элемента"""
        current = self.head
        
        while current:
            if current.data == data:
                return True
            current = current.next
        
        return False

# Использование
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 10 -> 20 -> 30 -> None

ll.prepend(5)
ll.display()  # 5 -> 10 -> 20 -> 30 -> None

ll.insert_after(20, 25)
ll.display()  # 5 -> 10 -> 20 -> 25 -> 30 -> None

ll.delete(25)
ll.display()  # 5 -> 10 -> 20 -> 30 -> None

print(ll.search(10))  # True
print(ll.search(99))  # False

Двусвязный список (Doubly Linked List)

Каждый узел имеет указатели на оба соседа:

class DNode:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = DNode(data)
        
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        
        current.next = new_node
        new_node.prev = current
    
    def display_forward(self):
        """Вывести в прямом порядке"""
        elements = []
        current = self.head
        
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(' <-> '.join(elements))
    
    def display_backward(self):
        """Вывести в обратном порядке"""
        if not self.head:
            return
        
        # найти последний узел
        current = self.head
        while current.next:
            current = current.next
        
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.prev
        
        print(' <-> '.join(elements))

# Использование
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display_forward()   # 10 <-> 20 <-> 30
dll.display_backward()  # 30 <-> 20 <-> 10

Циклический список (Circular Linked List)

Последний узел указывает на первый:

class CircularLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            new_node.next = new_node  # указывает на себя
            return
        
        current = self.head
        while current.next != self.head:  # остаёмся в цикле
            current = current.next
        
        current.next = new_node
        new_node.next = self.head

# Использование
cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
# 10 -> 20 -> 30 -> 10 -> 20 -> ...

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

Плюсы связанного списка

✅ Эффективная вставка/удаление в начало (O(1)) ✅ Динамический размер ✅ Не требует предварительного выделения памяти

Минусы связанного списка

❌ Медленный доступ к элементам по индексу (O(n)) ❌ Дополнительная память на указатели ❌ Медленнее в кэше (элементы разбросаны в памяти)

Когда использовать

• Связанный список: когда часто добавляешь/удаляешь в начало
• Массив: когда нужен быстрый доступ по индексу
• Дек (deque): оптимален для добавления с обоих концов

Связанный список — это фундаментальная структура данных, используемая в графах, кэшах и многих алгоритмах.