В чем разница между ArrayList и LinkedList?

Разница между ArrayList и LinkedList

Хотя в Dart нет прямых аналогов ArrayList и LinkedList (как в Java), их концепции остаются актуальны при работе со списками. Понимание этих различий критично для выбора правильной структуры данных.

ArrayList (List в Dart)

List в Dart реализует динамический массив (аналог ArrayList):

final list = <int>[1, 2, 3, 4, 5];
print(list[2]); // O(1) доступ по индексу
list.add(6);    // O(1) в среднем, O(n) при расширении

Характеристики:

• Память: Непрерывный блок памяти
• Доступ по индексу: O(1) — мгновенно
• Вставка в конец: O(1) в среднем
• Вставка в середину: O(n) — нужно сдвигать элементы
• Удаление: O(n) для удаления с середины
• Поиск: O(n) без индекса

LinkedList (в контексте других языков)

LinkedList использует узлы, связанные указателями:

Данные в памяти разреженные:
[Node1] -> [Node2] -> [Node3] -> [Node4] -> null
  data      data       data       data

Характеристики:

• Память: Разреженная (узлы в разных местах памяти)
• Доступ по индексу: O(n) — нужно пройти от начала
• Вставка в начало: O(1) — просто переставить указатели
• Вставка в конец: O(1) с tail pointer, иначе O(n)
• Удаление: O(1) если есть ссылка на узел
• Поиск: O(n)

Сравнительная таблица

Операция         | ArrayList | LinkedList
─────────────────┼───────────┼──────────
Доступ [i]       | O(1)      | O(n)
Вставка в конец  | O(1)*     | O(1)**
Вставка в начало | O(n)      | O(1)
Вставка в конец  | O(n)      | O(1)
Удаление с конца | O(1)      | O(1)
Удаление с начала| O(n)      | O(1)
Поиск элемента   | O(n)      | O(n)
Память           | Эффект    | Большая

*O(1) в среднем, O(n) при перераспределении **С сохраненным указателем на tail

Примеры в Dart

List (ArrayList поведение):

// Быстрый доступ по индексу
final numbers = [10, 20, 30, 40, 50];
print(numbers[2]);      // 30 - O(1)

// Медленная вставка в середину
var items = ['a', 'b', 'd', 'e'];
items.insert(2, 'c');   // O(n) - сдвигаются 'd' и 'e'
print(items);           // [a, b, c, d, e]

// Эффективная работа с концом
var stack = <int>[];
stack.add(1);           // O(1)
stack.add(2);           // O(1)
stack.removeLast();     // O(1)

Использование List для каждого случая:

// ❌ Плохо - много вставок в начало
final list = <int>[];
for (int i = 0; i < 1000; i++) {
  list.insert(0, i);  // O(n) каждый раз!
}

// ✅ Хорошо - работа с концом
final list = <int>[];
for (int i = 0; i < 1000; i++) {
  list.add(i);        // O(1)
}

Практические примеры в Flutter

Кэшированные данные (ArrayList):

class ProductCache {
  final List<Product> products = [];
  
  Product getByIndex(int index) => products[index]; // O(1) - быстро!
  
  void addProduct(Product p) => products.add(p);
}

История действий (LinkedList поведение):

class UndoManager {
  final List<Action> history = [];
  int currentIndex = -1;
  
  void execute(Action action) {
    currentIndex++;
    if (currentIndex < history.length) {
      history.removeRange(currentIndex, history.length);
    }
    history.add(action);  // Добавляем в конец - O(1)
  }
  
  void undo() {
    if (currentIndex > 0) {
      currentIndex--;
      history[currentIndex].undo();
    }
  }
}

Когда выбрать List

✅ Используй List (ArrayList):

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

❌ Избегай List при:

• Частые вставки/удаления в начало
• Частые вставки/удаления в середину
• Очередь (Queue) — используй Queue из dart:collection

Альтернативы в Dart

// Для очереди
final queue = Queue<int>();
queue.add(1);           // O(1)
queue.removeFirst();    // O(1)

// Для стека
final stack = <int>[];
stack.add(1);           // O(1)
stack.removeLast();     // O(1)

// Для отсортированного доступа
final set = <int>{};    // HashSet
set.add(1);             // O(1)
set.contains(1);        // O(1)

Вывод

List в Dart — это оптимальный выбор для большинства случаев благодаря быстрому доступу по индексу и простоте использования. Однако при часто вставках в начало или у очередях лучше использовать Queue из dart:collection. Выбор структуры данных критичен для производительности приложения.