Двусвязный список в Python: простой инструмент для сложных задач

Привет, Хабр!

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

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

Начнем с основ: разберемся, как они работают, где их реально стоит применять и как реализовать двусвязный список с нуля (да, на время забудем про библиотеку collections и её deque).

Начнем с основ: создание узлов

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

class Node:     def __init__(self, data):         self.data = data         self.prev = None  # Ссылка на предыдущий элемент         self.next = None  # Ссылка на следующий элемент 

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

Переходим к самой структуре двусвязного списка

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

Для начала создадим самую простую заготовку двусвязного списка:

class DoublyLinkedList:     def __init__(self):         self.head = None  # Начальный (первый) узел         self.tail = None  # Конечный (последний) узел 

Это базовая структура, и на данный момент наш двусвязный список пуст — он не содержит никаких элементов, а указатели head и tail указывают на None.

Добавляем элементы в конец и начало списка

Добавление в конец списка

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

1. Текущий хвост tail списка должен указать на новый узел.

2. Новый узел должен узнать о текущем хвосте как о своём предыдущем узле.

3. Хвост списка должен обновиться на новый узел.

def append(self, data):     new_node = Node(data)     if self.head is None:  # Если список пуст         self.head = self.tail = new_node  # Первый элемент — и голова, и хвост     else:         self.tail.next = new_node  # Связываем текущий хвост с новым узлом         new_node.prev = self.tail  # Связываем новый узел с текущим хвостом         self.tail = new_node  # Обновляем хвост 

Добавление в начало списка

Метод prepend добавляет новый элемент в начало списка. Это практически зеркальная операция по сравнению с append, но здесь обновляем указатели для головы:

1. Новый узел смотрит на текущую голову как на следующий элемент.

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

3. Обновляем указатель на голову, чтобы он указывал на новый узел.

def prepend(self, data):     new_node = Node(data)     if self.head is None:  # Если список пуст         self.head = self.tail = new_node  # Первый элемент — и голова, и хвост     else:         new_node.next = self.head  # Новый узел указывает на текущую голову         self.head.prev = new_node  # Текущая голова знает, что перед ней новый узел         self.head = new_node  # Обновляем голову 

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

Удаление элементов

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

Как работает удаление?

1. Мы начинаем с поиска элемента, который нужно удалить.

2. Как только нашли его, нужно обновить указатели у соседних узлов:

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

   • Если это хвост, аналогично обновляем ссылку на предыдущий элемент.

   • Если элемент в середине, то его соседи должны перепрыгнуть через него, связавшись друг с другом.

Пример кода для удаления элемента:

def delete(self, data):     if self.head is None:         return  # Список пуст      current = self.head     while current:         if current.data == data:             # Если удаляемый элемент - это голова             if current == self.head:                 self.head = current.next                 if self.head:                     self.head.prev = None  # Обнуляем указатель на предыдущий узел у новой головы             # Если удаляемый элемент - это хвост             elif current == self.tail:                 self.tail = current.prev                 if self.tail:                     self.tail.next = None  # Обнуляем указатель на следующий узел у нового хвоста             # Если удаляемый элемент находится в середине             else:                 current.prev.next = current.next                 current.next.prev = current.prev             return         current = current.next 

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

Обход списка

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

Прямой обход списка (от головы до хвоста):

def traverse(self):     current = self.head     while current:         print(current.data, end=" ")         current = current.next     print()

Обратный обход списка (от хвоста к голове):

def reverse_traverse(self):     current = self.tail     while current:         print(current.data, end=" ")         current = current.prev     print()

Пограничные случаи

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

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

2. Удаление последнего элемента: Если удаляется последний элемент, то как указатель на голову head, так и на хвост tail должны быть сброшены на None.

Эти ситуации можно легко обработать в методах добавления и удаления.

Метод поиска элементов

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

def find(self, data):     current = self.head     while current:         if current.data == data:             return current         current = current.next     return None  # Элемент не найден

Этот метод проходит по всему списку и возвращает узел с нужным значением, если такой существует.

Пример использования

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

class Node:     def __init__(self, data):         self.data = data         self.prev = None         self.next = None  class UndoRedo:     def __init__(self):         self.current = None  # Текущая версия текста      def add_change(self, data):         new_node = Node(data)         if self.current is None:             self.current = new_node  # Если это первое изменение         else:             self.current.next = new_node             new_node.prev = self.current             self.current = new_node  # Обновляем текущее состояние      def undo(self):         if self.current and self.current.prev:             self.current = self.current.prev         return self.current.data if self.current else None      def redo(self):         if self.current and self.current.next:             self.current = self.current.next         return self.current.data if self.current else None  # Пример использования: editor = UndoRedo() editor.add_change("Текст версии 1") editor.add_change("Текст версии 2") editor.add_change("Текст версии 3")  print(editor.undo())  # Текст версии 2 print(editor.undo())  # Текст версии 1 print(editor.redo())  # Текст версии 2

add_change() добавляет новые состояния текста.

undo() и redo() позволяют перемещаться между этими состояниями назад и вперед.

---

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