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

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

Основные типы:

• Односвязный список — каждый узел ссылается только на следующий.
• Двусвязный список — узлы содержат ссылки на следующий и предыдущий элементы.
• Кольцевой список — последний узел ссылается на первый.

Пример на 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)), нет кэширования.