Привет, Хабр!
Эта статья написана для новичков, которые только начинают осваивать структуры данных на 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 добавляет новый узел в конец двусвязного списка. Создаем новый узел и проверяем, пуст ли список. Если да, то новый элемент станет и головой, и хвостом. Если же список уже содержит элементы, то:
Текущий хвост
tailсписка должен указать на новый узел.Новый узел должен узнать о текущем хвосте как о своём предыдущем узле.
Хвост списка должен обновиться на новый узел.
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, но здесь обновляем указатели для головы:
Новый узел смотрит на текущую голову как на следующий элемент.
Текущая голова должна знать, что у неё появился новый предшественник.
Обновляем указатель на голову, чтобы он указывал на новый узел.
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 нет сложных манипуляций с элементами. Мы просто меняем ссылки у нескольких узлов. Это и есть одна из фич двусвязного списка: не нужно беспокоиться о сдвиге всего массива.
Удаление элементов
Теперь рассмотрим, как реализуется удаление узлов из двусвязного списка.
Как работает удаление?
Мы начинаем с поиска элемента, который нужно удалить.
Как только нашли его, нужно обновить указатели у соседних узлов:
Если это голова, то нужно обновить ссылку на следующий элемент и убедиться, что у нового первого элемента больше нет ссылки на удаленный узел.
Если это хвост, аналогично обновляем ссылку на предыдущий элемент.
Если элемент в середине, то его соседи должны перепрыгнуть через него, связавшись друг с другом.
Пример кода для удаления элемента:
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()Пограничные случаи
При работе с двусвязными списками всегда нужно учитывать пограничные случаи:
Пустой список: Когда вы пытаетесь удалить элемент из пустого списка, никакие операции не должны выполняться.
Удаление последнего элемента: Если удаляется последний элемент, то как указатель на голову
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()) # Текст версии 2add_change() добавляет новые состояния текста.
undo() и redo() позволяют перемещаться между этими состояниями назад и вперед.
Всем новичкам в Pyrhon рекомендую обратить внимание на открытый урок по управлению зависимостями, на котором будут рассмотрены инструменты Pipenv и Poetry. Если актуально — записывайтесь по ссылке.