Что такое связный список (Linked List)?

Связный список — это линейная структура данных, состоящая из последовательности узлов (Node), где каждый узел хранит:

1. Данные (значение).
2. Ссылку (указатель) на следующий узел в списке.

В отличие от массива (List в Dart), элементы связного списка не хранятся в непрерывном блоке памяти, а распределены динамически.

Основные типы:

• Односвязный список: Узел ссылается только на следующий.
• Двусвязный список: Узел ссылается на следующий и предыдущий, что позволяет обход в обоих направлениях.
• Кольцевой связный список: "Хвост" списка ссылается на его "голову".

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

class Node<T> {
  T value;
  Node<T>? next; // Ссылка на следующий узел (null для последнего)

  Node(this.value, [this.next]);
}

class LinkedList<T> {
  Node<T>? head;
  Node<T>? tail;

  void addToTail(T value) {
    final newNode = Node(value);
    if (tail == null) { // Список пуст
      head = tail = newNode;
    } else {
      tail!.next = newNode;
      tail = newNode;
    }
  }

  void printList() {
    Node<T>? current = head;
    while (current != null) {
      print(current.value);
      current = current.next;
    }
  }
}

void main() {
  final list = LinkedList<int>();
  list.addToTail(1);
  list.addToTail(2);
  list.addToTail(3);
  list.printList(); // Вывод: 1 2 3
}

Применение в разработке: Прямое использование связных списков в Dart встречается редко, так как встроенный List (реализованный как расширяемый массив) эффективен для большинства задач. Однако понимание принципа работы важно для изучения более сложных структур (деревья, графы) и алгоритмов.