Как работает с памятью linked list?

Linked List в Dart: Как работает в памяти

Linked List — это фундаментальная структура данных, которая работает совсем по-другому, чем массивы. В контексте Flutter это важно понимать для оптимизации памяти и производительности.

1. Что такое Linked List?

Linked List — это структура, где каждый элемент (Node) содержит:

• Данные (value)
• Ссылка на следующий элемент (next)
• (Опционально) ссылка на предыдущий элемент (prev) для двусвязного списка

Обычный массив (Array):
┌─────┬─────┬─────┬─────┐
│  A  │  B  │  C  │  D  │ ← Память расположена подряд
└─────┴─────┴─────┴─────┘
  [0]   [1]   [2]   [3]

Односвязный список (Singly Linked List):
Node A ──→ Node B ──→ Node C ──→ Node D ──→ null
 ↓         ↓         ↓         ↓
(Data)   (Data)   (Data)   (Data)
(Next)   (Next)   (Next)   (Next)

Память может быть разбросана по разным местам!

2. Структура Node в Dart

// Собственная реализация
class LinkedListNode<T> {
  T value;
  LinkedListNode<T>? next;
  
  LinkedListNode(this.value, [this.next]);
}

class SimpleLinkList<T> {
  LinkedListNode<T>? head;
  
  void add(T value) {
    if (head == null) {
      head = LinkedListNode(value);
    } else {
      var current = head;
      while (current?.next != null) {
        current = current?.next;
      }
      current?.next = LinkedListNode(value);
    }
  }
  
  void print() {
    var current = head;
    while (current != null) {
      print(current.value);
      current = current.next;
    }
  }
}

// Использование
var list = SimpleLinkList<String>();
list.add('A');
list.add('B');
list.add('C');
list.print(); // A, B, C

3. LinkedList в dart:collection

Dart имеет встроенный LinkedList класс.

import 'dart:collection';

// LinkedList требует элементы типа LinkedListEntry
class Entry extends LinkedListEntry<String> {
  Entry(String value) : super(value);
}

void main() {
  final list = LinkedList<Entry>();
  
  // Добавление
  list.add(Entry('A'));
  list.add(Entry('B'));
  list.add(Entry('C'));
  
  // Итерация
  for (var entry in list) {
    print(entry); // A, B, C
  }
  
  // Удаление
  if (list.isNotEmpty) {
    list.first.unlink(); // Удалить первый элемент
  }
}

4. Сравнение: Array vs Linked List

*в двусвязном списке с ссылкой на tail

5. Как работает память

Array (ArrayList/List в Dart):

Мемория (RAM):
┌────────────────────────────────┐
│ 0x1000: 'A' (4 bytes)          │
│ 0x1004: 'B' (4 bytes)          │ ← Данные подряд
│ 0x1008: 'C' (4 bytes)          │
│ 0x100C: 'D' (4 bytes)          │
│ ...                            │
└────────────────────────────────┘

Указатель на Array: 0x1000

Доступ: array[2] → читаем память из (0x1000 + 2 * sizeof(item))
Это очень быстро (O(1))!

Linked List:

Мемория (RAM):
┌──────────────────┐
│Node A: 0x1000    │
│  value: 'A'      │
│  next: 0x2000    │ ← Указывает на другой адрес
└──────────────────┘

         ...(другая память может быть здесь)...

┌──────────────────┐
│Node B: 0x2000    │
│  value: 'B'      │
│  next: 0x3000    │ ← Указывает ещё куда-то
└──────────────────┘

         ...(и ещё)...

┌──────────────────┐
│Node C: 0x3000    │
│  value: 'C'      │
│  next: null      │ ← Конец списка
└──────────────────┘

Доступ: найти элемент 2
- Начинаем с head (0x1000)
- Следуем next → 0x2000
- Следуем next → 0x3000
Это медленно (O(n))!

6. Memory Overhead

Linked List требует дополнительной памяти для указателей.

class IntNode extends LinkedListEntry<int> {
  IntNode(int value) : super(value);
}

// В памяти:
// int value: 4-8 bytes
// LinkedListEntry overhead: ~24 bytes (в зависимости от платформы)
// + next pointer: 8 bytes
// + prev pointer: 8 bytes (если двусвязный)
// ────────────────────
// Итого: ~40-50 bytes на один элемент!

// Для сравнения: List<int> с 1000 элементов занимает ~4KB
// LinkedList<IntNode> с 1000 элементов занимает ~40-50KB!

7. Практическое применение в Flutter

Случай 1: Когда LinkedList может быть полезен

// Очередь (Queue) - часто вставляешь в начало, удаляешь с конца
class TaskQueue {
  final tasks = LinkedList<TaskNode>();
  
  void addTask(String task) {
    tasks.add(TaskNode(task)); // O(1)
  }
  
  String? removeTask() {
    if (tasks.isEmpty) return null;
    final first = tasks.first;
    final value = first.value;
    first.unlink(); // O(1)
    return value;
  }
}

class TaskNode extends LinkedListEntry<String> {
  TaskNode(String value) : super(value);
}

Случай 2: Когда List лучше

// ❌ НЕ ДЕЛАЙ ТАК: LinkedList для частого доступа
var list = LinkedList<NumberNode>();
list.add(NumberNode(1));
list.add(NumberNode(2));
list.add(NumberNode(3));

var sum = 0;
for (var item in list) { // O(n) итерация
  sum += item.value;
}

// ✅ ЛУЧШЕ: используй List
var list = [1, 2, 3];
var sum = list.reduce((a, b) => a + b);

// ✅ ЛУЧШЕ: для последовательного доступа
for (var value in list) { // O(1) доступ к каждому
  sum += value;
}

8. Двусвязный список

class BilinkedListNode<T> {
  T value;
  BilinkedListNode<T>? next;
  BilinkedListNode<T>? previous;
  
  BilinkedListNode(this.value);
  
  void insertAfter(BilinkedListNode<T> node) {
    node.next = this.next;
    node.previous = this;
    if (this.next != null) {
      this.next!.previous = node;
    }
    this.next = node;
  }
}

// Пример: кольцевой буфер для анимаций
class CircularBuffer<T> {
  late BilinkedListNode<T>? head;
  late BilinkedListNode<T>? current;
  
  void add(T value) {
    final node = BilinkedListNode(value);
    if (head == null) {
      head = node;
      current = node;
      node.next = node;
      node.previous = node; // Кольцо
    } else {
      head!.insertAfter(node);
    }
  }
  
  T? next() {
    if (current == null) return null;
    current = current!.next;
    return current!.value;
  }
}

9. Когда использовать LinkedList в практике

✅ ДА:

• Очереди (Queue)
• Стеки (Stack) с частыми вставками в начало
• LRU кэш (Least Recently Used)
• Разреженные структуры с редкими доступами

❌ НЕТ:

• Обычные списки данных
• Частый доступ по индексу
• Небольшие коллекции (< 100 элементов)
• Мобильные приложения (память критична)

10. Производительность в контексте Flutter

// ❌ Проблема в Flutter: memory pressure
var largeLinkedList = LinkedList<ExpensiveNodeType>();
// Каждый Node = ~50 bytes overhead
// 10000 элементов = 500KB только на указатели!
// На мобильном устройстве это заметно

// ✅ Лучше: List<T>
var list = List<ExpensiveType>();
// Даже с большим количеством элементов
// Memory компактнее
// Доступ быстрее
// GC работает эффективнее

11. Реальный пример: LRU Cache

import 'dart:collection';

class LRUCache<K, V> {
  final int maxSize;
  final map = <K, LinkedListEntry<_CacheItem<K, V>>>{}
  final list = LinkedList<_CacheItem<K, V>>();
  
  LRUCache(this.maxSize);
  
  V? get(K key) {
    final node = map[key];
    if (node == null) return null;
    
    // Переместить в конец (most recently used)
    node.unlink();
    list.add(node);
    
    return node.value.value;
  }
  
  void put(K key, V value) {
    if (map.containsKey(key)) {
      map[key]!.unlink();
    }
    
    final node = _CacheItem<K, V>(key, value);
    list.add(node);
    map[key] = node;
    
    // Если превышен размер, удалить самый старый (first)
    if (list.length > maxSize) {
      final oldest = list.first;
      oldest.unlink();
      map.remove(oldest.value.key);
    }
  }
}

class _CacheItem<K, V> extends LinkedListEntry<_CacheItem<K, V>> {
  final K key;
  final V value;
  
  _CacheItem(this.key, this.value) : super(_CacheItem);
}

Вывод

Linked List в памяти:

• Данные разбросаны — следуем указателям
• Дорогой по памяти — overhead на каждый элемент
• Быстр для вставок/удалений — O(1)
• Медленнее для доступа — O(n)

В практике Flutter:

• Используй List<T> в 99% случаев
• LinkedList только для специфических случаев (Queue, LRU)
• Помни о memory overhead на мобильных устройствах
• Профилируй — не додумывай!

Linked List — это важная техника, но в контексте мобильной разработки List часто оказывается лучшим выбором.