Collection #

dart:collection provides additional collection implementations not available in dart:core — data structures optimized for specific use cases: queues, linked lists, always-sorted trees, and unmodifiable views. Choosing the right collection can make a significant performance difference: Queue is far more efficient than List for add/remove operations at both ends, and SplayTreeMap enables always-sorted iteration without the cost of repeated sorting.

An Overview of dart:collection #

flowchart LR
    DC["dart:collection"] --> Q["Queue\nDouble-ended queue"]
    DC --> LHM["LinkedHashMap\nMap with insertion order"]
    DC --> LHS["LinkedHashSet\nSet with insertion order"]
    DC --> STM["SplayTreeMap\nMap sorted by keys"]
    DC --> STS["SplayTreeSet\nSorted set"]
    DC --> VIEW["Unmodifiable Views\nListView, MapView, SetView"]
    DC --> MISC["Misc\nHashMap, HashSet\nDoubleLinkedQueue"]

Queue — a Double-Ended Queue (Deque) #

Queue is a data structure supporting efficient addition and removal at both ends (head and tail). Unlike List, which is O(n) for operations at the front, Queue is O(1) for all end operations:

import 'dart:collection';

// Create a Queue
final queue = Queue<int>();
final dariIterable = Queue<int>.from([1, 2, 3, 4, 5]);

// Add at the end (tail)
queue.addLast(1);   // [1]
queue.addLast(2);   // [1, 2]
queue.addLast(3);   // [1, 2, 3]
queue.add(4);       // alias for addLast — [1, 2, 3, 4]

// Add at the start (head)
queue.addFirst(0);  // [0, 1, 2, 3, 4]

// Add many
queue.addAll([5, 6]);       // at the end
// No built-in addAllFirst

// Remove from the start (head) — O(1)
final pertama = queue.removeFirst(); // 0, queue = [1, 2, 3, 4, 5, 6]

// Remove from the end (tail) — O(1)
final terakhir = queue.removeLast(); // 6, queue = [1, 2, 3, 4, 5]

// Access without removing
print(queue.first);  // 1
print(queue.last);   // 5

// Properties
print(queue.length);    // 5
print(queue.isEmpty);   // false
print(queue.isNotEmpty); // true

// Iteration
for (final item in queue) {
  print(item);
}

// Remove a specific element
queue.remove(3); // remove the value 3 — O(n)

// Conversion
List<int> list = queue.toList();

Queue vs List for Queue Operations #

import 'dart:collection';

// ANTI-PATTERN: List as a queue — removeAt(0) is O(n)
List<String> listQueue = [];
listQueue.add('A');         // O(1) — add at the end
listQueue.add('B');
listQueue.removeAt(0);      // ✗ O(n) — remove at the start, shift all elements

// CORRECT: Queue for queue operations — O(1) at both ends
Queue<String> queue = Queue<String>();
queue.addLast('A');         // O(1)
queue.addLast('B');
queue.removeFirst();        // ✓ O(1) — no shifting

// A simple benchmark for 100.000 operations:
// List.removeAt(0): ~5000ms
// Queue.removeFirst(): ~5ms
// A 1000x difference!

Use Cases: Task Queues, BFS, Undo/Redo #

import 'dart:collection';

// A simple task queue
class TaskQueue<T> {
  final _queue = Queue<T>();

  void enqueue(T task) => _queue.addLast(task);
  T dequeue() => _queue.removeFirst();
  bool get isEmpty => _queue.isEmpty;
  int get panjang => _queue.length;
}

// Breadth-First Search (BFS) using a Queue
List<int> bfs(Map<int, List<int>> graph, int start) {
  final visited = <int>{};
  final queue = Queue<int>()..add(start);
  final hasil = <int>[];

  while (queue.isNotEmpty) {
    final node = queue.removeFirst();
    if (visited.contains(node)) continue;

    visited.add(node);
    hasil.add(node);

    for (final tetangga in graph[node] ?? []) {
      if (!visited.contains(tetangga)) {
        queue.addLast(tetangga);
      }
    }
  }
  return hasil;
}

// Undo/Redo with two stacks (DoubleLinkedQueue as a stack)
class UndoRedo<T> {
  final _undo = Queue<T>();
  final _redo = Queue<T>();

  void lakukan(T aksi) {
    _undo.addLast(aksi);
    _redo.clear(); // redo is cleared when a new action happens
  }

  T? batal() {
    if (_undo.isEmpty) return null;
    final aksi = _undo.removeLast();
    _redo.addLast(aksi);
    return aksi;
  }

  T? ulang() {
    if (_redo.isEmpty) return null;
    final aksi = _redo.removeLast();
    _undo.addLast(aksi);
    return aksi;
  }
}

LinkedHashMap — a Map with Insertion Order #

LinkedHashMap is Dart’s default {} implementation — preserving insertion order. It’s available explicitly when you want to emphasize ordering semantics or need special constructors:

import 'dart:collection';

// Map literals {} are LinkedHashMap by default
final map = {'c': 3, 'a': 1, 'b': 2};
print(map.keys.toList()); // ['c', 'a', 'b'] — insertion order preserved

// Explicit LinkedHashMap
final linked = LinkedHashMap<String, int>();
linked['c'] = 3;
linked['a'] = 1;
linked['b'] = 2;
print(linked.keys.toList()); // ['c', 'a', 'b']

// LinkedHashMap with custom equality and hashing
// Useful when keys aren't standard types
final caseInsensitive = LinkedHashMap<String, int>(
  equals: (a, b) => a.toLowerCase() == b.toLowerCase(),
  hashCode: (s) => s.toLowerCase().hashCode,
);

caseInsensitive['Dart'] = 1;
caseInsensitive['dart'] = 2;  // overwrites 'Dart' because case-insensitive
print(caseInsensitive.length); // 1
print(caseInsensitive['DART']); // 2

// An LRU Cache using LinkedHashMap
class LRUCache<K, V> {
  final int kapasitas;
  final _cache = LinkedHashMap<K, V>();

  LRUCache(this.kapasitas);

  V? get(K kunci) {
    if (!_cache.containsKey(kunci)) return null;
    // Move to the end (most recently used)
    final nilai = _cache.remove(kunci)!;
    _cache[kunci] = nilai;
    return nilai;
  }

  void put(K kunci, V nilai) {
    if (_cache.containsKey(kunci)) {
      _cache.remove(kunci);
    } else if (_cache.length >= kapasitas) {
      // Remove the least recently used (first element)
      _cache.remove(_cache.keys.first);
    }
    _cache[kunci] = nilai;
  }

  int get ukuran => _cache.length;
}

final lru = LRUCache<String, String>(kapasitas: 3);
lru.put('a', 'nilai_a');
lru.put('b', 'nilai_b');
lru.put('c', 'nilai_c');
lru.get('a');              // access 'a' → becomes most recently used
lru.put('d', 'nilai_d');   // evict 'b' (least recently used)
print(lru.ukuran);         // 3

SplayTreeMap — a Sorted Map #

SplayTreeMap is a BST (Binary Search Tree) that keeps keys always sorted. Operations are O(log n) for lookup, insert, and delete — but the advantage: iteration is always in key order:

import 'dart:collection';

// Default: natural order (ascending)
final tree = SplayTreeMap<String, int>();
tree['banana'] = 3;
tree['apple'] = 1;
tree['cherry'] = 2;
tree['date'] = 4;

print(tree.keys.toList()); // ['apple', 'banana', 'cherry', 'date'] — always sorted!

// Custom comparator — custom order
final descending = SplayTreeMap<int, String>(
  (a, b) => b.compareTo(a), // descending
);
descending[3] = 'tiga';
descending[1] = 'satu';
descending[2] = 'dua';
print(descending.keys.toList()); // [3, 2, 1] — descending

// Efficient range operations
final byInt = SplayTreeMap<int, String>();
for (int i = 1; i <= 10; i++) byInt[i] = 'nilai_$i';

// firstKey / lastKey — O(log n)
print(byInt.firstKey()); // 1
print(byInt.lastKey());  // 10

// Keys before/after a given value — O(log n)
print(byInt.lastKeyBefore(5));  // 4 — the largest key < 5
print(byInt.firstKeyAfter(5));  // 6 — the smallest key > 5

// Range query — all keys between 3 and 7
final range = byInt.keys
    .skipWhile((k) => k < 3)
    .takeWhile((k) => k <= 7)
    .toList();
print(range); // [3, 4, 5, 6, 7]

When to Use SplayTreeMap vs LinkedHashMap vs HashMap #

LinkedHashMap (default Map {})
  → Need insertion order preserved
  → O(1) average lookup
  → USE for almost all cases

HashMap
  → No ordering needed at all
  → Slightly faster than LinkedHashMap for very large datasets
  → USE when order truly doesn't matter

SplayTreeMap
  → Need sorted iteration by key
  → Need range queries (keys before/after a given value)
  → O(log n) lookup — slower than HashMap/LinkedHashMap
  → USE for time-series, sorted leaderboards, schedulers

LinkedHashSet — a Set with Insertion Order #

import 'dart:collection';

// Regular sets don't preserve order
final set1 = {3, 1, 4, 1, 5, 9, 2, 6};
print(set1.toList()); // order not guaranteed

// LinkedHashSet — insertion order preserved
final linked = LinkedHashSet<int>()
  ..addAll([3, 1, 4, 1, 5, 9, 2, 6]); // duplicates automatically ignored

print(linked.toList()); // [3, 1, 4, 5, 9, 2, 6] — insertion order, no duplicates

// Deduplication that preserves the original order
List<String> dedupUrutan(List<String> list) {
  return LinkedHashSet<String>.from(list).toList();
}

print(dedupUrutan(['b', 'a', 'c', 'a', 'b', 'd']));
// ['b', 'a', 'c', 'd'] — first insertion order preserved

SplayTreeSet — a Sorted Set #

import 'dart:collection';

// A set that's always sorted
final treeSet = SplayTreeSet<int>();
treeSet.addAll([5, 3, 8, 1, 4, 7, 2, 6]);
print(treeSet.toList()); // [1, 2, 3, 4, 5, 6, 7, 8] — always sorted!

// firstKey / lastKey
print(treeSet.first); // 1
print(treeSet.last);  // 8

// lastBefore / firstAfter
print(treeSet.lastBefore(5));  // 4
print(treeSet.firstAfter(5));  // 6

// Custom comparator
final descSet = SplayTreeSet<String>((a, b) => b.compareTo(a));
descSet.addAll(['banana', 'apple', 'cherry']);
print(descSet.toList()); // ['cherry', 'banana', 'apple']

Unmodifiable Views #

Views are wrappers that prevent modification without copying the data — more memory-efficient than making copies:

import 'dart:collection';

// UnmodifiableListView — a List that can't be modified
final internal = [1, 2, 3, 4, 5];
final view = UnmodifiableListView(internal);

print(view[0]);     // 1 — read ✓
print(view.length); // 5

try {
  view.add(6);      // ✗ UnsupportedError
} catch (e) {
  print('Cannot be modified: $e');
}

// The view reflects changes to the original list
internal.add(6);
print(view.last); // 6 — the view updates automatically!

// UnmodifiableMapView
final internalMap = {'a': 1, 'b': 2};
final mapView = UnmodifiableMapView(internalMap);
print(mapView['a']); // 1
// mapView['c'] = 3; // ✗ UnsupportedError

// UnmodifiableSetView (from the collection package or manual)
// Available in the collection package: UnmodifiableSetView

// Common pattern: expose internal collections as views
class Repository {
  final List<Produk> _data = [];

  // Return a view — not a copy (memory-efficient) and not the raw reference
  UnmodifiableListView<Produk> get semua => UnmodifiableListView(_data);

  // Return a copy if you want an immutable snapshot
  List<Produk> get snapshot => List.unmodifiable(_data);
}

HashMap — a Map Without Order Guarantees #

import 'dart:collection';

// Pure HashMap — no iteration order guarantees
// Slightly more efficient than LinkedHashMap for very large datasets
final hash = HashMap<String, int>();
hash['c'] = 3;
hash['a'] = 1;
hash['b'] = 2;

// Order not guaranteed — could be 'a', 'b', 'c' or any order
print(hash.keys.toList()); // undefined order

// Same as LinkedHashMap, but without the linked list overhead
// Use when:
// - Order truly doesn't matter
// - The dataset is very large and performance-critical

DoubleLinkedQueue — a Queue with Node Access #

import 'dart:collection';

// DoubleLinkedQueue allows node-level access and operations
final dll = DoubleLinkedQueue<int>();
dll.addAll([1, 2, 3, 4, 5]);

// Iterate with access to entries (nodes)
dll.forEachEntry((entry) {
  print('${entry.element}');

  // Node operations
  if (entry.element == 3) {
    entry.insertBefore(99);  // insert before this node
    entry.insertAfter(100);  // insert after this node
  }
});

print(dll.toList()); // [1, 2, 99, 3, 100, 4, 5]

// Remove specific entries from within forEachEntry
dll.forEachEntry((entry) {
  if (entry.element % 2 == 0) {
    entry.remove(); // remove even nodes
  }
});

print(dll.toList()); // [1, 99, 3, 5]

Choosing the Right Collection #

flowchart TD
    A{Collection type?} --> B{List / indexed sequence}
    A --> C{Set / unique}
    A --> D{Map / key-value}
    A --> E{Queue / queue}

    B --> B1["List<T>\nDart core\nGeneral purpose"]
    B --> B2["UnmodifiableListView\ndart:collection\nExpose without modification"]

    C --> C1["Set<T>\nDart core\nOrder doesn't matter"]
    C --> C2["LinkedHashSet\ninsertion order"]
    C --> C3["SplayTreeSet\nnatural/custom order"]

    D --> D1["Map / {}\nLinkedHashMap\nInsertion order"]
    D --> D2["HashMap\nNo order\nSlightly faster"]
    D --> D3["SplayTreeMap\nAlways sorted\nRange queries"]

    E --> E1["Queue / ListQueue\nO(1) add/remove\nat both ends"]
    E --> E2["DoubleLinkedQueue\nNode-level access\nInsert in the middle"]

Summary #

  • Queue for queues (FIFO) or stacks (LIFO) — addFirst/addLast/removeFirst/removeLast are all O(1), unlike List, which is O(n) for operations at the front.
  • BFS requires a Queue — Queue.removeFirst() is O(1) vs List.removeAt(0) which is O(n) — the difference can reach 1000x for large datasets.
  • LinkedHashMap is Dart’s default {} — it already preserves insertion order. Use HashMap only when order truly doesn’t matter and you need slightly better speed.
  • SplayTreeMap for sorted data — iteration is always in key order, and firstKeyAfter/lastKeyBefore enable efficient range queries without re-sorting.
  • UnmodifiableListView is more efficient than List.unmodifiable — a view doesn’t copy the data, it’s just a wrapper. Changes to the original list remain visible through the view.
  • LRU Caches with LinkedHashMap — a very useful pattern: remove from the front (LRU), add to the end (MRU), move accessed items to the end.
  • LinkedHashSet for order-preserving deduplication — LinkedHashSet.from(list).toList() removes duplicates while keeping the first-occurrence order.
  • SplayTreeSet for sorted sets — useful for leaderboards, event schedulers, and cases where elements always need to be iterated in sorted order.
  • DoubleLinkedQueue when you need insertions in the middle of a queue — entry.insertBefore() and entry.insertAfter() are O(1), unlike List.insert() which is O(n).
  • All dart:collection classes are available directly from dart:core when used as types — Queue, LinkedHashMap, etc. only need to be imported from dart:collection when explicitly creating instances.

← Previous: Convert   Next: Typed Data →

About | Author | Content Scope | Editorial Policy | Privacy Policy | Disclaimer | Contact