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

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

[

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

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

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

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

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

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

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

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

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

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

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

Вот пример реализации простого связанного списка в 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
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node


    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        print(elements)

В этом примере мы создаем два класса: Node для представления узла и LinkedList, который содержит методы для добавления элементов в конец списка (append) и отображения списка (display).

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

Использование collections.deque для связанных списков

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

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

Для начала, вам необходимо импортировать модуль deque из библиотеки collections. Затем вы можете создать новый объект deque и добавлять или удалять элементы с использованием методов append и pop. Вот пример:

from collections import deque


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


# Добавление элементов в связанный список
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)


# Удаление элементов из связанного списка
linked_list.popleft() # удаление первого элемента
linked_list.pop() # удаление последнего элемента

В этом примере мы создаем новый связанный список с помощью deque(), а затем добавляем несколько элементов с помощью метода append(). Затем мы удаляем элементы из начала списка с помощью метода popleft() и из конца списка с помощью метода pop().

Как реализовать очереди и стеки с использованием collections.deque

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

Чтобы реализовать очередь, вы можете использовать методы append() для добавления элемента в конец очереди и popleft() для удаления элемента из начала очереди.

from collections import deque


queue = deque()


# Добавление элементов в очередь
queue.append(1)
queue.append(2)
queue.append(3)


# Удаление элемента из начала очереди
queue.popleft()

Чтобы реализовать стек, вы можете использовать методы append() для добавления элемента в конец стека и pop() для удаления элемента из конца стека.

from collections import deque


stack = deque()


# Добавление элементов в стек
stack.append(1)
stack.append(2)
stack.append(3)


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

Теперь вы знаете, как использовать collections.deque для реализации связанных списков, очередей и стеков в Python.

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

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

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
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node


    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        print(elements)

В этом примере мы создаем два класса: Node для представления узла и LinkedList, который содержит методы для добавления элементов в связанный список (append) и отображения списка (display).

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

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

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

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

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

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


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


    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node
            new_node.prev = current_node


    def display_forward(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        print(elements)


    def display_backward(self):
        elements = []
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.prev
        print(elements)

В этом примере мы добавляем новое поле prev в класс Node, чтобы хранить ссылку на предыдущий узел. Также мы добавляем новый метод display_backward(), который позволяет отображать список в обратном порядке, начиная с последнего элемента.

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

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

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


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


    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current_node = self.head
            while current_node.next != self.head:
                current_node = current_node.next
            current_node.next = new_node
            new_node.next = self.head


    def display(self):
        elements = []
        current_node = self.head
        while True:
            elements.append(current_node.data)
            current_node = current_node.next
            if current_node == self.head:
                break
        print(elements)

В этом примере последний узел списка ссылается на первый узел, создавая замкнутый цикл. Мы используем условие current_node == self.head в цикле, чтобы определить конец списка.

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

Заключение

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