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

Введение в связанные списки в Python

Автор: Pedro Pregueiro

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

Понимание связанных списков

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

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

Каждый элемент связанного списка называется узлом, и каждый узел имеет два поля:

Data (данные) содержит значение, которое должно быть записано в узел.
Next (следующий) содержит ссылку на следующий узел в списке.

Вот как выглядит типичный узел:

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

Связанный список - это совокупность узлов. Первый узел называется головой списка и используется в качестве стартовой точки для итерации по списку. Последний узел должен иметь ссылку next, указывающую на None, чтобы определить конец списка.

Практические применения

Связанные списки имеют различные применения в реальном мире. Они могут использоваться для реализации стеков, очередей, кольцевых списков и других структур данных. Вот некоторые практические примеры использования связанных списков:

Управление памятью: Связанные списки могут быть использованы для управления динамической памятью, разделения ее на блоки и отслеживания их доступности.
Имплементация стеков и очередей: Связанные списки могут быть использованы для реализации структур данных стека и очереди.
Работа с большими данными: Связанные списки позволяют эффективно работать с большими объемами данных, так как они не требуют непрерывного блока памяти.

Сравнение производительности со списками

Одним из факторов, который следует учитывать при выборе между связанными списками и обычными списками, является производительность. Начиная с Python 3.2, в стандартной библиотеке Python появился модуль collections с классом deque, который реализует двустороннюю очередь, основанную на связанных списках. Вот сравнение производительности связанных списков и обычных списков:

Операция	Связанные списки (через `collections.deque`)	Обычные списки
Добавление элемента в начало	O(1)	O(n)
Добавление элемента в конец	O(1)	O(1)
Удаление элемента с начала	O(1)	O(n)
Удаление элемента с конца	O(1)	O(1)
Получение элемента по индексу	O(n)	O(1)

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

Использование `collections.deque`

Python предоставляет модуль collections с классом deque, который реализует двустороннюю очередь на базе связанных списков. deque предоставляет быстрое добавление и удаление элементов на обоих концах. Вот пример использования collections.deque для создания связанного списка:

from collections import deque

# Создание пустого связанного списка
linked_list = deque()

# Добавление элементов в конец списка
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)

# Добавление элемента в начало списка
linked_list.appendleft(5)

# Удаление элемента из конца списка
linked_list.pop()

# Удаление элемента из начала списка
linked_list.popleft()

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

Теперь, когда вы знакомы с основами связанных списков и использованием collections.deque, вы можете реализовать свой собственный связанный список. Вот пример, демонстрирующий, как создать связанный список, обойти его, вставить новый узел и удалить узел из списка:

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

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

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node

    def remove(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next is not None:
                if current.next.data == data:
                    current.next = current.next.next
                    return
                current = current.next

Использование продвинутых связанных списков

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

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

Двусвязные списки имеют не только ссылку на следующий узел, но и ссылку на предыдущий узел. Это позволяет эффективно выполнять операции вставки и удаления элементов как в начале, так и в конце списка. Вот пример, показывающий, как использовать двусвязные списки в Python:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # Определение методов добавления, удаления и обхода списка

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(10)
doubly_linked_list.append(20)
doubly_linked_list.append(30)
doubly_linked_list.traverse()

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

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

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    # Определение методов добавления, удаления и обхода списка

circular_linked_list = CircularLinkedList()
circular_linked_list.append(10)
circular_linked_list.append(20)
circular_linked_list.append(30)
circular_linked_list.traverse()

Заключение

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

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

Использование связанных списков может быть сложным, но с практикой и пониманием основных концепций они станут мощным инструментом в вашем арсенале программирования на Python.

Дальнейшее чтение:

Официальная документация по модулю collections