Какие плюсы и минусы LinkedList?

Плюсы и минусы LinkedList в Dart/Flutter

LinkedList (связный список) — это фундаментальная структура данных в программировании. В Dart она находится в пакете `dart:collection`. Рассмотрю подробно её преимущества и недостатки.

Структура LinkedList

import 'dart:collection';

// LinkedList в Dart работает с LinkedListEntry
class Person extends LinkedListEntry<Person> {
  final String name;
  final int age;
  
  Person(this.name, this.age);
}

void main() {
  final list = LinkedList<Person>();
  
  final person1 = Person('Alice', 30);
  final person2 = Person('Bob', 25);
  
  list.add(person1);
  list.add(person2);
  
  for (final person in list) {
    print('${person.name}: ${person.age}');
  }
}

ПЛЮСЫ LinkedList

1. Быстрое удаление и вставка

final list = LinkedList<Person>();
final person = Person('John', 28);

list.add(person);

// Удаление за O(1) если есть ссылка на элемент
person.unlink();

// Вставка в начало списка за O(1)
final newPerson = Person('Jane', 26);
list.first.insertBefore(newPerson);

Объяснение: В отличие от List, где удаление/вставка требует сдвига элементов (O(n)), в LinkedList это делается за O(1) при наличии ссылки на элемент.

Применение: Очереди задач, history/undo стеки, кэши LRU.

2. Экономия памяти при частых изменениях

Когда часто добавляешь/удаляешь элементы, LinkedList не требует переаллокации памяти и копирования данных.

// Эффективная реализация очереди
class Queue<T extends LinkedListEntry<T>> {
  final _list = LinkedList<T>();
  
  void enqueue(T item) => _list.add(item);
  T dequeue() {
    final first = _list.first;
    first.unlink();
    return first;
  }
}

3. Двусторонние операции

LinkehList позволяет легко navigat в обе стороны (если нужно).

// Обход в обе стороны
void traverse(LinkedList<Person> list) {
  // Вперед
  for (final person in list) {
    print('Forward: ${person.name}');
  }
  
  // Назад через first/last
  var current = list.last;
  while (current != null) {
    print('Backward: ${current.name}');
    // Нужна дополнительная логика для движения назад
    break;
  }
}

МИНУСЫ LinkedList

1. Нет random access (индексированного доступа)

final list = LinkedList<Person>();
list.add(Person('Alice', 30));
list.add(Person('Bob', 25));

// ❌ Так НЕ работает
// final person = list[0];  // Ошибка!

// ✅ Нужно итерировать
final iterator = list.iterator;
iterator.moveNext();
final firstPerson = iterator.current;

Проблема: Чтобы найти n-й элемент, нужно пройти через все предыдущие (O(n)).

2. Больше памяти на элемент

Каждый элемент LinkedList требует дополнительных полей для ссылок (next/previous).

// Примерная структура в памяти
class LinkedListEntry<E> {
  E value;          // Сам элемент
  LinkedListEntry? next;     // Ссылка на следующий (+8 байт)
  LinkedListEntry? previous; // Ссылка на предыдущий (+8 байт)
}

// List требует меньше памяти
list<int> = [1, 2, 3, 4, 5];  // Компактнее

Итог: LinkedList может потреблять в 2-3 раза больше памяти чем List на больших объёмах данных.

3. Худшая cache locality

// List: элементы в памяти рядом
final list = [1, 2, 3, 4, 5];
// Они находятся в соседних ячейках памяти
// CPU кэш быстро их загружает

// LinkedList: элементы разбросаны в памяти
final linkedList = LinkedList<IntEntry>();
// Элементы могут быть в разных местах памяти
// Частые cache miss, медленнее для больших данных

4. Сложнее в использовании

// List простой и удобный
final list = [1, 2, 3];
list.add(4);
list.removeAt(0);
list.forEach((e) => print(e));

// LinkedList требует extends LinkedListEntry
class IntEntry extends LinkedListEntry<IntEntry> {
  final int value;
  IntEntry(this.value);
}

Проблема: Не все типы можно напрямую использовать в LinkedList.

Сравнение с List

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

✅ Используй LinkedList:

• Частые вставки/удаления в начало или середину
• Реализация очереди (Queue) или стека (Stack)
• LRU кэш с быстрым переупорядочиванием
• Двусвязные списки для навигации

❌ Избегай LinkedList:

• Нужны частые обращения по индексу
• Работа с большими данными (memory overhead)
• Performance-critical операции
• Нет специальных требований

Практический пример: LRU Cache

class LRUCache<K, V> {
  final int capacity;
  final _cache = <K, CacheEntry<V>>{}
  final _order = LinkedList<CacheEntry<V>>();
  
  void put(K key, V value) {
    if (_cache.containsKey(key)) {
      _cache[key]!.unlink();
    } else if (_cache.length >= capacity) {
      final oldest = _order.first;
      _cache.remove(_order.first);
      oldest.unlink();
    }
    
    final entry = CacheEntry(key, value);
    _order.add(entry);
    _cache[key] = entry;
  }
}

Резюме

LinkedList в Dart — это мощный инструмент для специфических сценариев, где нужны быстрые вставки/удаления. Однако в большинстве случаев обычный List эффективнее и удобнее. Выбирай LinkedList осознанно, когда профилирование показывает узкие места в операциях с коллекциями.