Связные списки в Python: руководство с примерами

Связный список — это структура данных, играющая ключевую роль в организации и управлении данными. Он содержит последовательность узлов, размещённых в произвольных местах памяти, что помогает эффективно управлять памятью. Каждый узел связного списка состоит из двух основных компонентов: части с данными и ссылки на следующий узел в последовательности.

Если на первый взгляд это звучит сложно — не беспокойтесь!

Мы разберёмся в основах: что такое связные списки, зачем они нужны и какие уникальные преимущества дают.

Почему связные списки?

Связные списки были придуманы, чтобы устранить ряд недостатков при хранении данных в обычных списках и массивах, как описано ниже:

Простота вставки и удаления

В списках вставка или удаление элемента в любой позиции, кроме конца, требует сдвига всех последующих элементов. Это имеет трудоёмкость O(n) и может заметно ухудшать производительность, особенно по мере роста списка. Если вы ещё не знакомы с тем, как работают списки или как они устроены, прочитайте наш туториал по спискам в Python.

Связные списки работают иначе. Они хранят элементы в разных, несмежных участках памяти и соединяют их указателями на последующие узлы. Благодаря этому можно добавлять или удалять элементы в любой позиции, просто изменяя ссылки — чтобы включить новый элемент или обойти удалённый.

Когда у вас уже есть прямая ссылка на узел в точке вставки или удаления, сама операция выполняется за O(1). Однако поиск этой позиции всё равно требует прохода за O(n), так что преимущество O(1) применимо лишь тогда, когда у вас уже есть указатель на нужный узел (например, при работе с началом списка).

Динамический размер

Списки Python — это динамические массивы, то есть они позволяют изменять размер.

Однако это связано с рядом сложных операций, включая перераспределение массива в новый, больший участок памяти. Такая перераспределение неэффективно, поскольку элементы копируются в новый блок, при этом может выделяться больше места, чем требуется прямо сейчас.

В отличие от этого, связные списки могут динамически расти и уменьшаться без необходимости перераспределения или изменения размера. Поэтому они предпочтительны для задач, где нужна высокая гибкость.

Эффективность использования памяти

Списки выделяют память для всех своих элементов в одном непрерывном блоке. Если список должен вырасти сверх исходного размера, ему нужно выделить новый, больший непрерывный блок памяти и скопировать туда все существующие элементы. Этот процесс трудоёмок и неэффективен, особенно для больших списков. С другой стороны, если исходный размер списка был завышен, неиспользуемая память пропадает впустую.

Связные списки, напротив, выделяют память для каждого элемента отдельно. Это позволяет лучше использовать память, поскольку память для новых элементов выделяется по мере их добавления.

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

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

Выбор между связным списком и массивом зависит от конкретных требований приложения. Связные списки особенно полезны, когда:

• Необходимо часто вставлять и удалять множество элементов
• Размер данных непредсказуем или часто меняется
• Прямой доступ к элементам не требуется
• Набор данных содержит крупные элементы или сложные структуры

Типы связных списков

Существует три типа связных списков, и каждый по-своему удобен в разных сценариях. Это:

Односвязные списки

Односвязный список

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

Обычно каждый узел односвязного списка состоит из двух частей:

• Данные: фактическая информация, хранящаяся в узле.
• Next Pointer: ссылка на следующий узел. У последнего узла ссылка на следующий обычно равна null.

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

Вставка и удаление узла в начале односвязного списка очень эффективны — O(1). Однако вставка и удаление в середине или в конце требуют прохода до нужной точки, что даёт трудоёмкость O(n).

Устройство односвязных списков делает их полезными, когда операции происходят в начале списка.

Двусвязные списки

Двусвязный список

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

Двусвязные списки решают эту проблему, добавляя в каждый узел дополнительный указатель, благодаря чему по списку можно перемещаться в обе стороны. Каждый узел двусвязного списка содержит три элемента: данные, указатель на следующий узел и указатель на предыдущий.

Кольцевые связные списки

Кольцевой связный список

Кольцевые связные списки — это особый вид связных списков, в котором последний узел указывает обратно на первый, образуя кольцо. Это означает, что, в отличие от рассмотренных выше односвязных и двусвязных списков, кольцевой список не заканчивается — он зациклен.

Зацикленная природа кольцевых списков делает их идеальными для сценариев, где требуется непрерывный цикл, например, настольные игры, в которых ход после последнего игрока возвращается к первому, или вычислительные алгоритмы вроде циклического планирования (round-robin).

Сводка по временной сложности

Полезно наглядно сравнить связные списки со списками Python:

Главный вывод: связные списки выигрывают во вставках и удалениях в голове (O(1)), но проигрывают во всём остальном. Если вы не добавляете и не удаляете элементы в начале структуры данных достаточно часто, обычный список Python, скорее всего, будет лучшим выбором.

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

Теперь, когда мы разобрались, что такое связные списки, зачем они нужны и какие бывают, перейдём к их реализации в Python. Ноутбук к этому руководству доступен также в этой рабочей тетради DataLab; если вы создадите копию, сможете редактировать и запускать код. Это отличный вариант, если у вас возникнут сложности с запуском кода локально!

Инициализация узла

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

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

    def __repr__(self):
        return f"Node({self.data})"

Код выше инициализирует узел, выполняя два основных действия: атрибуту «data» присваивается значение, представляющее фактическую информацию, которую должен содержать узел. Атрибут «next» представляет адрес следующего узла. Сейчас он установлен в None, что означает отсутствие связи с другими узлами списка. По мере добавления новых узлов этот атрибут будет указывать на последующий узел.

Создание класса связного списка

Далее создадим класс связного списка. В нём будут инкапсулированы все операции управления узлами, такие как вставка и удаление. Начнём с инициализации связного списка:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

Устанавливая self.head в None, мы указываем, что связный список изначально пуст и в нём нет узлов, на которые можно ссылаться. Теперь перейдём к наполнению списка вставкой новых узлов.

Вставка нового узла в начало связного списка

Внутри класса LinkedList добавим метод, создающий новый узел и помещающий его в начало списка:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Каждый вызов этого метода создаёт новый узел с указанными данными. Указатель next нового узла устанавливается на текущую голову списка, что помещает его перед существующими узлами. Наконец, новый узел становится головой списка.

Теперь заполним связный список последовательностью слов, чтобы лучше понять, как работает вставка. Для этого сначала создадим метод для обхода и печати содержимого списка:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Этот метод выведет содержимое нашего связного списка. Теперь используем определённые методы, чтобы заполнить список словами: «the quick brown fox».

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Код выше должен вывести следующее:

"the quick brown fox"

Вставка нового узла в конец связного списка

Теперь создадим метод insertAtEnd внутри класса LinkedList, чтобы добавлять новый узел в конец списка. Если список пуст, новый узел станет его головой. Иначе он будет добавлен после текущего последнего узла. Посмотрим, как это работает:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Метод начинает с создания нового узла. Затем проверяет, пуст ли список: если да — новый узел назначается головой. Иначе происходит проход до последнего узла, после чего его указатель next устанавливается на новый узел.

Теперь добавим этот метод в класс LinkedList и воспользуемся им, чтобы добавить слово в конец списка. Для этого измените основную функцию так:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Обратите внимание: мы просто вызвали метод insertAtEnd, чтобы добавить слово «jumps» в конец списка. Этот код должен вывести:

"the quick brown fox jumps"

Удаление узла из начала связного списка

Удалить первый узел связного списка просто: достаточно перенаправить голову списка на второй узел. Тогда первый узел больше не будет частью списка. Для этого добавьте в класс LinkedList следующий метод:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Удаление узла из конца связного списка

Чтобы удалить последний узел связного списка, нужно пройти по списку до предпоследнего узла и установить его указатель next в None. Так последний узел будет удалён из списка. Скопируйте и вставьте следующий метод в класс LinkedList:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Сначала метод проверяет, пуст ли список, и при необходимости возвращает сообщение пользователю. Если в списке один узел — он удаляется. В списках с несколькими узлами метод находит предпоследний узел и устанавливает ссылку на следующий узел в None.

Теперь обновим основную функцию, чтобы удалить элементы из начала и конца связного списка:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Этот код выведет список до и после удаления, показывая, как работают операции вставки и удаления в связных списках. После запуска вы увидите такой результат:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

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

Последняя операция в этой главе — получение конкретного значения из связного списка. Для этого метод должен начать с головы и итерироваться по каждому узлу, проверяя, совпадают ли данные узла с искомым значением. Вот практическая реализация:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Чтобы найти конкретные значения в созданном нами списке, обновите основную функцию, добавив метод поиска:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Этот код выведет следующий результат:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Слово «quick» успешно найдено в связном списке, так как оно находится на первой позиции. Слова «lazy» в списке нет, поэтому оно не найдено.

Итоги

Если вы дочитали до этого места — поздравляем! Теперь у вас есть прочное понимание базовых принципов связных списков: их структуры, типов, способов добавления и удаления элементов и обхода.

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

Создайте собственный проект

Погрузитесь в практическое применение связных списков, интегрируя их в проект по программированию или анализу данных. Связные списки используют для разработки файловых систем, построения хеш-таблиц, а также при создании систем GPS-навигации и настольных игр. Чтобы начать, посмотрите наши бесплатные пошаговые проекты по data science, которые научат решать реальные задачи на Python, R и SQL.

Изучайте структуры данных и алгоритмы

Освоение других структур данных — деревьев, стеков, очередей — логично продолжает понимание связных списков. Эти структуры развивают их принципы, помогая эффективно решать более широкий круг вычислительных задач. Например, деревья и двоичные деревья поиска расширяют идею связных списков до иерархической формы, позволяя каждому узлу соединяться с несколькими элементами.

Если эти понятия кажутся вам незнакомыми — не переживайте! У Datacamp есть целый курс по структурам данных и алгоритмам в Python, где эти темы разобраны подробнее. Сначала вы познакомитесь со структурами данных — стеком, деревьями, хеш-таблицами, очередями и графами. По мере прохождения курса вы разберётесь в алгоритмах поиска и сортировки, что поможет вам стать более эффективным программистом и решателем задач.

Изучение продвинутых концепций связных списков

В этом руководстве мы реализовали односвязные списки и рассмотрели операции вставки, удаления и обхода.

Вы можете пойти дальше и изучить реализацию двусвязных и кольцевых списков. Skip lists — ещё одно расширение связных списков, позволяющее ускорить поиск за счёт более быстрого доступа к элементам.

Освоение этих продвинутых структур данных поднимет ваши технические навыки на новый уровень и существенно улучшит программирование, подготовив к более сложным задачам в областях анализа данных, разработки ПО и машинного обучения.

Если вам нужна более дружелюбная для начинающих вводная в программирование перед переходом к продвинутым темам, изучите наш трек навыков Python Programming. Он предлагает серию курсов, которые научат вас основам языка.