Что такое связный список и каковы его ключевые особенности

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

Ключевые характеристики:

• Узел (Node): Базовый элемент списка, который содержит две части: сами данные (data) и указатель (next) на следующий узел в последовательности.
• Указатель (Pointer/Next): Ссылка, которая связывает один узел с другим. У последнего узла указатель обычно равен null.
• Голова (Head): Указатель на самый первый узел списка. Это точка входа в структуру.

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

• Односвязный список (Singly Linked List): Каждый узел ссылается только на следующий.
• Двусвязный список (Doubly Linked List): Узлы содержат ссылки как на следующий, так и на предыдущий элементы, что упрощает обход в обе стороны.
• Кольцевой список (Circular Linked List): Последний узел ссылается на первый, замыкая список в кольцо.

Пример реализации узла и односвязного списка на 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_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

Преимущества и недостатки

Преимущества:

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

Недостатки:

• Медленный доступ к элементам: Для доступа к элементу по индексу требуется последовательный обход от начала списка, что занимает линейное время O(n).
• Дополнительные затраты памяти: Каждый узел хранит указатель, что увеличивает общий расход памяти по сравнению с массивом.
• Плохая локальность кэша: Элементы разбросаны по памяти, что делает итерацию по списку медленнее, чем по массиву, элементы которого лежат в памяти рядом.