Зачем нужен связанный список?

Связанный список (Linked List) — структура данных

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

Основная идея

Массив:          [1] [2] [3] [4] [5]  (смежные ячейки памяти)

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

Как устроен узел

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

# Создание связанного списка
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Связывание
node1.next = node2
node2.next = node3
# node3.next = None (по умолчанию)

# Обход
current = node1
while current:
    print(current.data)  # 1, 2, 3
    current = current.next

Класс для работы со связанным списком

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 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:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def display(self):
        """Вывести все элементы"""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" → ".join(map(str, elements)))

# Использование
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.display()  # 0 → 1 → 2 → 3

ll.delete(2)
ll.display()  # 0 → 1 → 3

Преимущества связанного списка

1. Динамическое распределение памяти

# Массив: нужно заранее знать размер
arr = [0] * 1000000  # Выделяется память для миллиона элементов

# Связанный список: память выделяется по мере надобности
ll = LinkedList()
for i in range(100):
    ll.append(i)  # Каждый раз выделяется ровно столько, сколько нужно

2. Быстрое вставление в начало O(1)

# Массив: нужно сдвинуть все элементы O(n)
arr.insert(0, 999)  # 999, [1, 2, 3, 4, 5] → [999, 1, 2, 3, 4, 5]

# Связанный список: просто создаем новый узел и обновляем head O(1)
ll.prepend(999)  # Мгновенно

3. Гибкий размер

# Массив: динамическое расширение медленно (реаллокация памяти)
# Связанный список: просто добавляем новый узел

Недостатки связанного списка

1. Медленный доступ по индексу O(n)

# Массив: доступ за O(1)
arr[5]  # Мгновенно

# Связанный список: нужно пройти 5 элементов O(n)
def get_at_index(ll, index):
    current = ll.head
    for _ in range(index):
        if not current:
            return None
        current = current.next
    return current.data if current else None

get_at_index(ll, 5)  # Медленно

2. Больше памяти (каждый узел хранит ссылку)

# Массив: 100 элементов = ~400 байт (int = 4 байта)
arr = [0] * 100

# Связанный список: 100 элементов = ~800 байт
# Каждый узел: int (4 байта) + указатель (8 байт на 64-bit) = 12 байт

3. Кэш-неэффективность

# Массив: элементы рядом в памяти (CPU кэш)
# Связанный список: элементы разбросаны по памяти (кэш-промахи)

Когда использовать связанный список

1. Очередь (Queue) — FIFO

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def enqueue(self, data):
        """Добавить в конец"""
        new_node = Node(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
    
    def dequeue(self):
        """Удалить из начала"""
        if not self.head:
            return None
        data = self.head.data
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return data

# Использование
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.dequeue())  # 2

2. Стек (Stack) — LIFO

class Stack:
    def __init__(self):
        self.head = None
    
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def pop(self):
        if not self.head:
            return None
        data = self.head.data
        self.head = self.head.next
        return data

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

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

# Позволяет ходить в обе стороны
# Используется в LRU кэшах, истории браузера

4. Практический пример: LRU Cache

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> value
        self.order = LinkedList()  # порядок использования
    
    def get(self, key):
        if key not in self.cache:
            return -1
        
        # Переместить в конец (самый свежий)
        # ... реализация
        return self.cache[key]
    
    def put(self, key, value):
        if len(self.cache) >= self.capacity:
            # Удалить самый старый (в начале списка) O(1)
            pass
        
        self.cache[key] = value
        # Добавить в конец

Сравнение со списком Python (list)

import time

# Список Python — это динамический массив
lst = list(range(100000))

# Добавить в конец: O(1) аммортизированное
start = time.time()
lst.append(999999)
print(f"Append: {time.time() - start:.6f}s")

# Вставить в начало: O(n)
start = time.time()
lst.insert(0, -1)
print(f"Insert at start: {time.time() - start:.6f}s")  # Медленнее

# Доступ по индексу: O(1)
start = time.time()
val = lst[50000]
print(f"Access by index: {time.time() - start:.6f}s")  # Быстро

Когда НЕ использовать связанный список в Python

# ❌ Нужен доступ по индексу → используй list
arr[5]

# ❌ Нужна сортировка → используй list
sorted(lst)

# ❌ Нужна быстрая вставка в конец → используй list или deque
lst.append()  # Аммортизированно O(1)

# ✅ Используй связанный список только если:
# - Часто вставляешь/удаляешь в начало O(1)
# - Нужны две стороны (двусвязный список)
# - Учишь структуры данных

Практический пример из LeetCode

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    """Развернуть связанный список"""
    prev = None
    current = head
    
    while current:
        # Сохраняем следующий
        next_temp = current.next
        
        # Разворачиваем текущий узел
        current.next = prev
        
        # Движемся дальше
        prev = current
        current = next_temp
    
    return prev

# Используется в собеседованиях!

Итог

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

В production Python коде я почти никогда не использую связанные списки. Вместо этого:

• Для очередей: collections.deque (оптимизирован)
• Для стеков: обычный list
• Для кэшей: OrderedDict или специализированные библиотеки

Но знание связанных списков — обязательно для любого разработчика. Это базовые знания структур данных, которые проверяют на собеседованиях.