Структура узла

Структура узла


Двусвязные списки в Python: структура, реализация и применение

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


Структура узла

Каждый узел двусвязного списка содержит:

  • data — значение узла;
  • prev — ссылка на предыдущий узел;
  • next — ссылка на следующий узел.

Реализация класса узла в Python:

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

Реализация двусвязного списка

Класс двусвязного списка управляет узлами через ссылки на голову (head) и хвост (tail):

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

    def is_empty(self):
        return self.head is None

Основные операции

1. Добавление элемента в начало

def prepend(self, data):
    new_node = Node(data)
    if self.is_empty():
        self.head = self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

2. Добавление элемента в конец

def append(self, data):
    new_node = Node(data)
    if self.is_empty():
        self.head = self.tail = new_node
    else:
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

3. Удаление элемента по значению

def delete(self, data):
    current = self.head
    while current:
        if current.data == data:
            if current.prev:
                current.prev.next = current.next
            else:
                self.head = current.next

            if current.next:
                current.next.prev = current.prev
            else:
                self.tail = current.prev
            return  # Удален первый найденный элемент
        current = current.next

4. Поиск элемента

def search(self, data):
    current = self.head
    while current:
        if current.data == data:
            return True
        current = current.next
    return False

5. Обход списка (с начала в конец)

def traverse_forward(self):
    current = self.head
    while current:
        print(current.data, end=" <-> ")
        current = current.next
    print("None")

6. Обход списка (с конца в начало)

def traverse_backward(self):
    current = self.tail
    while current:
        print(current.data, end=" <-> ")
        current = current.prev
    print("None")

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

dll = DoublyLinkedList()
dll.append(10)     # Список: 10
dll.prepend(5)     # Список: 5 <-> 10
dll.append(20)     # Список: 5 <-> 10 <-> 20
dll.delete(10)     # Список: 5 <-> 20
dll.traverse_forward()   # Вывод: 5 <-> 20 <-> None
dll.traverse_backward()  # Вывод: 20 <-> 5 <-> None

Преимущества и недостатки

Плюсы:

  • Быстрая вставка и удаление элементов в любом месте (O(1) для начала/конца, O(n) для произвольной позиции).
  • Возможность обхода в обоих направлениях.
  • Динамическое изменение размера.

Минусы:

  • Больший расход памяти (каждый узел хранит две ссылки).
  • Сложнее в реализации, чем односвязный список.
  • Доступ к элементу по индексу требует обхода (O(n)).

Сравнение с другими структурами данных

ПараметрДвусвязный списокОдносвязный списокМассив
Доступ по индексуO(n)O(n)O(1)
Вставка в началоO(1)O(1)O(n)
Удаление из концаO(1)O(n)O(1)
ПамятьВыше (две ссылки на узел)Ниже (одна ссылка на узел)Фиксированный размер

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

  1. История браузера (кнопки “Назад” и “Вперед”).
  2. Редакторы текста (undo/redo).
  3. Плейлисты с навигацией в обе стороны.
  4. Системы кэширования (например, LRU-кэш).

Рекомендации

  • Используйте двусвязные списки, когда нужна частая вставка/удаление элементов в обеих частях списка.
  • Для задач с частым доступом по индексу выбирайте массивы (или списки Python).
  • В библиотеке collections есть готовая реализация двусвязного списка — deque, оптимизированная для быстрых операций в начале и конце.

Заключение

Двусвязные списки — это гибкая структура данных, которая сочетает динамичность с эффективными операциями вставки и удаления. Их стоит использовать там, где важна двунаправленная навигация и частые модификации данных. Однако для работы с ними требуется аккуратная реализация, чтобы избежать ошибок в управлении ссылками. В Python для большинства задач удобнее применять встроенные структуры (например, deque), но понимание принципов работы двусвязных списков помогает глубже изучить алгоритмы и структуры данных.