Пропустить до содержимого
CodeMDD.io | Coding Tutorials

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

[

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

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

В этой статье вы узнаете:

  • Что такое связанные списки и когда их следует использовать
  • Как использовать collections.deque для всех ваших потребностей в связанных списках
  • Как реализовать свои собственные связанные списки
  • Какие еще типы связанных списков существуют и для чего они могут использоваться

Если вы хотите освежить свои навыки программирования для собеседования на работу, или если вы хотите узнать больше о структурах данных Python, помимо обычных словарей и списков, то вы попали по адресу!

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

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

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

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

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

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

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

Связанный список - это совокупность узлов. Первый узел называется головой (head) и используется как точка начала любой итерации по списку. У последнего узла должна быть ссылка на None для определения конца списка. Вот как это выглядит:

Теперь, когда вы знаете, как устроен связанный список, можно рассмотреть практические применения.

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

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

  • Стеков и очередей
  • Графов и деревьев
  • Циклических списков

Они также можно использовать для решения различных задач в программировании, таких как:

  • Управление памятью
  • Работа с большими объемами данных
  • Поддержка различных алгоритмов и структур данных

Теперь, когда вы понимаете, зачем нужны связанные списки, давайте рассмотрим, как их использовать в Python.

Введение в collections.deque

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

Как использовать collections.deque

Для использования collections.deque сначала необходимо импортировать его из модуля collections:

from collections import deque

Затем можно создать экземпляр deque:

my_linked_list = deque()

Теперь у вас есть пустой связанный список, и вы можете добавлять или удалять элементы с помощью методов append() и popleft():

my_linked_list.append(1)  # Добавить в конец списка
my_linked_list.append(2)
my_linked_list.appendleft(0)  # Добавить в начало списка
my_linked_list.popleft()  # Удалить первый элемент списка

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

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

Реализация вашего собственного связанного списка

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

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

Для начала создайте класс Node для представления узлов связанного списка:

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

Затем создайте класс LinkedList со свойством head и методами для создания, перебора, вставки и удаления узлов:

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


    def append(self, data):
        new_node = Node(data)


        if self.head is None:
            self.head = new_node
        else:
            curr_node = self.head
            while curr_node.next:
                curr_node = curr_node.next
            curr_node.next = new_node


    def traverse(self):
        curr_node = self.head
        while curr_node:
            print(curr_node.data)
            curr_node = curr_node.next


    def insert(self, data, position):
        new_node = Node(data)


        if position == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            curr_node = self.head
            prev_node = None
            curr_pos = 0


            while curr_node and curr_pos != position:
                prev_node = curr_node
                curr_node = curr_node.next
                curr_pos += 1


            prev_node.next = new_node
            new_node.next = curr_node


    def remove(self, data):
        curr_node = self.head
        prev_node = None


        while curr_node and curr_node.data != data:
            prev_node = curr_node
            curr_node = curr_node.next


        if curr_node is None:
            return


        if prev_node is None:
            self.head = curr_node.next
        else:
            prev_node.next = curr_node.next

Теперь вы можете создать экземпляр LinkedList и добавить, перебрать, вставить и удалить узлы:

my_linked_list = LinkedList()
my_linked_list.append(1)
my_linked_list.append(2)
my_linked_list.append(3)
my_linked_list.traverse()  # Выводит 1, 2, 3


my_linked_list.insert(0, 0)
my_linked_list.insert(4, 4)
my_linked_list.traverse()  # Выводит 0, 1, 2, 3, 4


my_linked_list.remove(2)
my_linked_list.traverse()  # Выводит 0, 1, 3, 4

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

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

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

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

Двусвязные списки - это связанные списки, у которых каждый узел содержит ссылки на предыдущий и следующий узлы. В Python вы можете использовать collections.deque с аргументом maxlen=2 для создания двусвязного списка:

my_doubly_linked_list = deque(maxlen=2)

Теперь вы можете выполнять обычные действия со связанными списками, но каждый узел будет содержать две ссылки: previous и next. Например:

my_doubly_linked_list.appendleft(1)
my_doubly_linked_list.append(2)
print(my_doubly_linked_list[0])  # Выводит 1
print(my_doubly_linked_list[1])  # Выводит 2

Как использовать циклические списки

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

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


first_node = Node(1)
second_node = Node(2)
third_node = Node(3)


first_node.next = second_node
second_node.next = third_node
third_node.next = first_node

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

Заключение

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

Теперь, когда вы освоили основы связанных списков, вы можете исследовать их дальше и применять эти знания в своих проектах на Python. Желаем вам успехов!