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

Эта статья написана для новичков, которые только начинают осваивать структуры данных на 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. Если актуально — записывайтесь по ссылке.