Что такое двусвязный список?

Двусвязный список (Doubly Linked List)

Двусвязный список — это структура данных, в которой каждый узел (node) содержит:

• Данные (value)
• Ссылку на следующий узел (next)
• Ссылку на предыдущий узел (previous)

Это позволяет навигировать по списку в обе стороны: вперёд и назад.

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

class Node<T> {
  T value;
  Node<T>? next;
  Node<T>? previous;
  
  Node(this.value);
}

Визуализация

Односвязный список:
Null <- [A] -> [B] -> [C] -> Null

Двусвязный список:
Null <-> [A] <-> [B] <-> [C] <-> Null

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

class DoublyLinkedList<T> {
  Node<T>? head;
  Node<T>? tail;
  int _length = 0;
  
  // Добавление в начало
  void addFirst(T value) {
    final newNode = Node(value);
    
    if (head == null) {
      head = tail = newNode;
    } else {
      newNode.next = head;
      head?.previous = newNode;
      head = newNode;
    }
    _length++;
  }
  
  // Добавление в конец
  void addLast(T value) {
    final newNode = Node(value);
    
    if (tail == null) {
      head = tail = newNode;
    } else {
      tail?.next = newNode;
      newNode.previous = tail;
      tail = newNode;
    }
    _length++;
  }
  
  // Удаление с начала
  T? removeFirst() {
    if (head == null) return null;
    
    final value = head!.value;
    
    if (head == tail) {
      head = tail = null;
    } else {
      head = head!.next;
      head?.previous = null;
    }
    _length--;
    return value;
  }
  
  // Удаление с конца
  T? removeLast() {
    if (tail == null) return null;
    
    final value = tail!.value;
    
    if (head == tail) {
      head = tail = null;
    } else {
      tail = tail!.previous;
      tail?.next = null;
    }
    _length--;
    return value;
  }
  
  // Получение длины
  int get length => _length;
  
  // Вывод списка вперёд
  void printForward() {
    final values = <T>[];
    var current = head;
    while (current != null) {
      values.add(current.value);
      current = current.next;
    }
    print('Вперёд: $values');
  }
  
  // Вывод списка назад
  void printBackward() {
    final values = <T>[];
    var current = tail;
    while (current != null) {
      values.add(current.value);
      current = current.previous;
    }
    print('Назад: $values');
  }
}

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

void main() {
  final list = DoublyLinkedList<int>();
  
  // Добавление элементов
  list.addLast(10);
  list.addLast(20);
  list.addLast(30);
  list.addFirst(5);
  
  print('Длина: ${list.length}'); // 4
  
  // Вывод в обе стороны
  list.printForward();  // Вперёд: [5, 10, 20, 30]
  list.printBackward(); // Назад: [30, 20, 10, 5]
  
  // Удаление
  print('Удалили первый: ${list.removeFirst()}'); // 5
  print('Удалили последний: ${list.removeLast()}'); // 30
  
  list.printForward();  // Вперёд: [10, 20]
  list.printBackward(); // Назад: [20, 10]
}

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

1. Навигация в обе стороны — можно двигаться вперёд и назад
2. Быстрое удаление — если есть ссылка на узел, удаление O(1)
3. Вставка в конец — быстрая благодаря tail ссылке

Недостатки

1. Больше памяти — два указателя на узел вместо одного
2. Сложнее — больше логики при операциях
3. Медленнее поиск — всё ещё O(n) для поиска элемента

Сравнение со список types

// Массив (List) в Dart
final list = [1, 2, 3, 4, 5];
list.add(6);           // O(1) в конце
list.insert(0, 0);     // O(n) в начале
list.removeAt(2);      // O(n)

// Двусвязный список
final dlist = DoublyLinkedList<int>();
dlist.addLast(1);      // O(1)
dlist.addFirst(0);     // O(1)
// Удаление требует поиска: O(n)

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

1. Реализация Deque (Double-Ended Queue)

class Deque<T> {
  final DoublyLinkedList<T> _list = DoublyLinkedList();
  
  void pushFront(T value) => _list.addFirst(value);
  void pushBack(T value) => _list.addLast(value);
  
  T? popFront() => _list.removeFirst();
  T? popBack() => _list.removeLast();
  
  int get length => _list.length;
}

final deque = Deque<int>();
deque.pushBack(1);
deque.pushBack(2);
deque.pushFront(0);
print(deque.popFront()); // 0
print(deque.popBack());  // 2

2. Реализация LRU Cache

class LRUCache<K, V> {
  final int capacity;
  final Map<K, Node<MapEntry<K, V>>> _map = {};
  final DoublyLinkedList<MapEntry<K, V>> _list = DoublyLinkedList();
  
  LRUCache({required this.capacity});
  
  void put(K key, V value) {
    if (_map.containsKey(key)) {
      // Обновить существующий ключ
      _map[key]?.value = MapEntry(key, value);
    } else {
      // Добавить новый ключ
      if (_map.length >= capacity) {
        // Удалить самый старый элемент
        _list.removeFirst();
      }
      final entry = MapEntry(key, value);
      _list.addLast(entry);
    }
  }
}

Когда использовать

• Реализация Deque (очередь с двумя концами)
• LRU кэши
• Браузерный history (вперёд/назад)
• Плейлисты с навигацией туда-сюда
• Текстовые редакторы (undo/redo)

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