Collection #

dart:collection menyediakan implementasi koleksi tambahan yang tidak tersedia di dart:core — struktur data yang dioptimalkan untuk use case spesifik: antrian (queue), linked list, tree yang selalu terurut, dan view yang tidak bisa dimodifikasi. Memilih koleksi yang tepat bisa membuat perbedaan performa yang signifikan: Queue jauh lebih efisien dari List untuk operasi tambah/hapus di kedua ujung, dan SplayTreeMap memungkinkan iterasi yang selalu terurut tanpa biaya sorting ulang.

Gambaran `dart:collection` #

flowchart LR
    DC["dart:collection"] --> Q["Queue\nAntrian dua ujung"]
    DC --> LHM["LinkedHashMap\nMap dengan urutan penyisipan"]
    DC --> LHS["LinkedHashSet\nSet dengan urutan penyisipan"]
    DC --> STM["SplayTreeMap\nMap terurut berdasarkan kunci"]
    DC --> STS["SplayTreeSet\nSet terurut"]
    DC --> VIEW["Unmodifiable Views\nListView, MapView, SetView"]
    DC --> MISC["Misc\nHashMap, HashSet\nDoubleLinkedQueue"]

`Queue` — Antrian Dua Ujung (Deque) #

Queue adalah struktur data yang mendukung penambahan dan penghapusan efisien di kedua ujung (head dan tail). Berbeda dari List yang O(n) untuk operasi di awal, Queue adalah O(1) untuk semua operasi ujung:

import 'dart:collection';

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

// Tambah di akhir (tail)
queue.addLast(1);   // [1]
queue.addLast(2);   // [1, 2]
queue.addLast(3);   // [1, 2, 3]
queue.add(4);       // alias addLast — [1, 2, 3, 4]

// Tambah di awal (head)
queue.addFirst(0);  // [0, 1, 2, 3, 4]

// Tambah banyak
queue.addAll([5, 6]);       // di akhir
// Tidak ada addAllFirst bawaan

// Hapus dari awal (head) — O(1)
final pertama = queue.removeFirst(); // 0, queue = [1, 2, 3, 4, 5, 6]

// Hapus dari akhir (tail) — O(1)
final terakhir = queue.removeLast(); // 6, queue = [1, 2, 3, 4, 5]

// Akses tanpa hapus
print(queue.first);  // 1
print(queue.last);   // 5

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

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

// Hapus elemen tertentu
queue.remove(3); // hapus nilai 3 — O(n)

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

Perbandingan `Queue` vs `List` untuk Operasi Antrian #

import 'dart:collection';

// ANTI-PATTERN: List sebagai queue — removeAt(0) adalah O(n)
List<String> listQueue = [];
listQueue.add('A');         // O(1) — tambah di akhir
listQueue.add('B');
listQueue.removeAt(0);      // ✗ O(n) — hapus di awal, geser semua elemen

// BENAR: Queue untuk operasi antrian — O(1) di kedua ujung
Queue<String> queue = Queue<String>();
queue.addLast('A');         // O(1)
queue.addLast('B');
queue.removeFirst();        // ✓ O(1) — tidak ada pergeseran

// Benchmark sederhana untuk 100.000 operasi:
// List.removeAt(0): ~5000ms
// Queue.removeFirst(): ~5ms
// Perbedaan 1000x!

Use Case: Task Queue, BFS, Undo/Redo #

import 'dart:collection';

// Task queue sederhana
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) menggunakan 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 dengan dua stack (DoubleLinkedQueue sebagai stack)
class UndoRedo<T> {
  final _undo = Queue<T>();
  final _redo = Queue<T>();

  void lakukan(T aksi) {
    _undo.addLast(aksi);
    _redo.clear(); // redo dihapus saat ada aksi baru
  }

  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` — Map dengan Urutan Penyisipan #

LinkedHashMap adalah implementasi default {} di Dart — menjaga urutan penyisipan. Tersedia secara eksplisit jika ingin menekankan semantik urutan atau membutuhkan constructor khusus:

import 'dart:collection';

// Map literal {} adalah LinkedHashMap secara default
final map = {'c': 3, 'a': 1, 'b': 2};
print(map.keys.toList()); // ['c', 'a', 'b'] — urutan penyisipan terjaga

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

// LinkedHashMap dengan equality dan hash kustom
// Berguna ketika kunci bukan tipe standar
final caseInsensitive = LinkedHashMap<String, int>(
  equals: (a, b) => a.toLowerCase() == b.toLowerCase(),
  hashCode: (s) => s.toLowerCase().hashCode,
);

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

// LRU Cache menggunakan 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;
    // Pindahkan ke akhir (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) {
      // Hapus yang paling lama tidak digunakan (elemen pertama)
      _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');              // akses 'a' → jadi most recently used
lru.put('d', 'nilai_d');   // evict 'b' (least recently used)
print(lru.ukuran);         // 3

`SplayTreeMap` — Map Terurut #

SplayTreeMap adalah BST (Binary Search Tree) yang menjaga kunci selalu terurut. Operasi O(log n) untuk lookup, insert, delete — tapi keuntungannya: iterasi selalu dalam urutan kunci:

import 'dart:collection';

// Default: urutan natural (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'] — selalu terurut!

// Custom comparator — urutan custom
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

// Operasi range yang efisien
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

// Kunci sebelum/sesudah nilai tertentu — O(log n)
print(byInt.lastKeyBefore(5));  // 4 — kunci terbesar yang < 5
print(byInt.firstKeyAfter(5));  // 6 — kunci terkecil yang > 5

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

Kapan SplayTreeMap vs LinkedHashMap vs HashMap #

LinkedHashMap (default Map {})
  → Butuh urutan penyisipan terjaga
  → Lookup O(1) rata-rata
  → GUNAKAN untuk hampir semua kasus

HashMap
  → Tidak butuh urutan apapun
  → Sedikit lebih cepat dari LinkedHashMap untuk dataset sangat besar
  → GUNAKAN jika urutan benar-benar tidak penting

SplayTreeMap
  → Butuh iterasi terurut berdasarkan kunci
  → Butuh range query (kunci sebelum/sesudah nilai tertentu)
  → Lookup O(log n) — lebih lambat dari HashMap/LinkedHashMap
  → GUNAKAN untuk time-series, leaderboard terurut, scheduler

`LinkedHashSet` — Set dengan Urutan Penyisipan #

import 'dart:collection';

// Set biasa tidak menjaga urutan
final set1 = {3, 1, 4, 1, 5, 9, 2, 6};
print(set1.toList()); // urutan tidak dijamin

// LinkedHashSet — urutan penyisipan terjaga
final linked = LinkedHashSet<int>()
  ..addAll([3, 1, 4, 1, 5, 9, 2, 6]); // duplikat otomatis diabaikan

print(linked.toList()); // [3, 1, 4, 5, 9, 2, 6] — urutan penyisipan, tanpa duplikat

// Deduplication yang mempertahankan urutan asli
List<String> dedupUrutan(List<String> list) {
  return LinkedHashSet<String>.from(list).toList();
}

print(dedupUrutan(['b', 'a', 'c', 'a', 'b', 'd']));
// ['b', 'a', 'c', 'd'] — urutan penyisipan pertama terjaga

`SplayTreeSet` — Set Terurut #

import 'dart:collection';

// Set yang selalu terurut
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] — selalu terurut!

// 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 adalah wrapper yang mencegah modifikasi tanpa membuat salinan data — lebih hemat memori dari membuat copy:

import 'dart:collection';

// UnmodifiableListView — List yang tidak bisa dimodifikasi
final internal = [1, 2, 3, 4, 5];
final view = UnmodifiableListView(internal);

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

try {
  view.add(6);      // ✗ UnsupportedError
} catch (e) {
  print('Tidak bisa dimodifikasi: $e');
}

// View merefleksikan perubahan pada list asli
internal.add(6);
print(view.last); // 6 — view otomatis update!

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

// UnmodifiableSetView (dari package collection atau manual)
// Tersedia di package collection: UnmodifiableSetView

// Pola umum: ekspos koleksi internal sebagai view
class Repository {
  final List<Produk> _data = [];

  // Kembalikan view — bukan copy (hemat memori) dan bukan reference asli
  UnmodifiableListView<Produk> get semua => UnmodifiableListView(_data);

  // Kembalikan copy jika ingin snapshot yang tidak berubah
  List<Produk> get snapshot => List.unmodifiable(_data);
}

`HashMap` — Map Tanpa Jaminan Urutan #

import 'dart:collection';

// HashMap murni — tidak ada jaminan urutan iterasi
// Sedikit lebih efisien dari LinkedHashMap untuk dataset sangat besar
final hash = HashMap<String, int>();
hash['c'] = 3;
hash['a'] = 1;
hash['b'] = 2;

// Urutan tidak dijamin — bisa 'a', 'b', 'c' atau urutan apapun
print(hash.keys.toList()); // urutan tidak tentu

// Sama seperti LinkedHashMap, tapi tanpa overhead linked list
// Gunakan ketika:
// - Urutan benar-benar tidak penting
// - Dataset sangat besar dan performa kritis

`DoubleLinkedQueue` — Queue dengan Akses Node #

import 'dart:collection';

// DoubleLinkedQueue memungkinkan akses dan operasi di level node
final dll = DoubleLinkedQueue<int>();
dll.addAll([1, 2, 3, 4, 5]);

// Iterasi dengan akses ke entry (node)
dll.forEachEntry((entry) {
  print('${entry.element}');

  // Operasi pada node
  if (entry.element == 3) {
    entry.insertBefore(99);  // sisipkan sebelum node ini
    entry.insertAfter(100);  // sisipkan setelah node ini
  }
});

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

// Hapus entry spesifik dari dalam forEachEntry
dll.forEachEntry((entry) {
  if (entry.element % 2 == 0) {
    entry.remove(); // hapus node genap
  }
});

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

Memilih Koleksi yang Tepat #

flowchart TD
    A{Tipe koleksi?} --> B{List / urutan berindeks}
    A --> C{Set / unik}
    A --> D{Map / key-value}
    A --> E{Antrian / queue}

    B --> B1["List<T>\nDart core\nUmum"]
    B --> B2["UnmodifiableListView\ndart:collection\nEkspos tanpa modifikasi"]

    C --> C1["Set<T>\nDart core\nUrutan tidak penting"]
    C --> C2["LinkedHashSet\nurutan penyisipan"]
    C --> C3["SplayTreeSet\nurutan natural/custom"]

    D --> D1["Map / {}\nLinkedHashMap\nUrutan penyisipan"]
    D --> D2["HashMap\nTanpa urutan\nSedikit lebih cepat"]
    D --> D3["SplayTreeMap\nSelalu terurut\nRange query"]

    E --> E1["Queue / ListQueue\nTambah/hapus O(1)\ndi kedua ujung"]
    E --> E2["DoubleLinkedQueue\nAkses level node\nSisip di tengah"]

Ringkasan #

Queue untuk antrian (FIFO) atau tumpukan (LIFO) — operasi addFirst/addLast/removeFirst/removeLast semua O(1), berbeda dari List yang O(n) untuk operasi di awal.
BFS wajib menggunakan Queue — Queue.removeFirst() adalah O(1) vs List.removeAt(0) yang O(n) — perbedaan bisa mencapai 1000x untuk dataset besar.
LinkedHashMap adalah default {} di Dart — sudah menjaga urutan penyisipan. Gunakan HashMap hanya jika urutan benar-benar tidak penting dan butuh sedikit lebih cepat.
SplayTreeMap untuk data terurut — iterasi selalu dalam urutan kunci, dan firstKeyAfter/lastKeyBefore memungkinkan range query yang efisien tanpa sorting ulang.
UnmodifiableListView lebih hemat dari List.unmodifiable — view tidak membuat salinan data, hanya wrapper. Perubahan pada list asli tetap terlihat melalui view.
LRU Cache dengan LinkedHashMap — pola yang sangat berguna: hapus dari awal (LRU), tambah ke akhir (MRU), akses pindahkan ke akhir.
LinkedHashSet untuk deduplication dengan urutan — LinkedHashSet.from(list).toList() menghapus duplikat sambil mempertahankan urutan kemunculan pertama.
SplayTreeSet untuk sorted set — berguna untuk leaderboard, event scheduler, dan kasus di mana elemen selalu perlu diiterasi secara terurut.
DoubleLinkedQueue ketika butuh sisipan di tengah-tengah antrian — entry.insertBefore() dan entry.insertAfter() adalah O(1), tidak seperti List.insert() yang O(n).
Semua kelas dart:collection tersedia langsung dari dart:core saat digunakan sebagai tipe — Queue, LinkedHashMap, dll. perlu diimport dari dart:collection hanya saat membuat instance secara eksplisit.

← Sebelumnya: dart:convert Berikutnya: dart:typed_data →

Collection #

Gambaran dart:collection #

Queue — Antrian Dua Ujung (Deque) #

Perbandingan Queue vs List untuk Operasi Antrian #