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

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

• Динамическое изменение размера — не требует заранее выделенной памяти, как массив.
• Эффективная вставка/удаление — O(1) для операций в начале/конце (если есть ссылка на хвост).
• Гибкость — можно легко реорганизовывать элементы без копирования.

Пример реализации на Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = 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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Недостатки:

• Доступ к элементу по индексу — O(n).
• Дополнительная память на хранение ссылок.

Используется в задачах, где важна частота вставок/удалений (например, очередь, стек, LRU-кэш).