Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 61 ยท Collections

The dart:collection Library

Learn the dart:collection library: Queue, ListQueue, DoubleLinkedQueue, LinkedList, HashSet, LinkedHashSet, HashMap, SplayTreeMap and unmodifiable views, and when to pick each.

List, Set and Map cover most programs, but they are only the default choices. The dart:collection library holds the specialised versions: queues with fast access at both ends, a linked list, sorted maps and sets, hash-only variants, and read-only views. Knowing which one fits saves you from slow code and from re-implementing well-tested data structures.

The Dart code is read-only; TypeScript stand-ins let you run the matching ideas. Everything here needs import 'dart:collection';. Basics of the core collections are in Lists, Sets, Maps and Iterables.

Queue, ListQueue and DoubleLinkedQueue

A queue lets you add and remove at both ends quickly. A plain List is fast at the end but slow at the front, because every element has to shift. Queue<E> is the interface, and it is also an Iterable<E>.

DART
import 'dart:collection';

void main() {
  var queue = Queue<String>();
  queue.addLast('b');
  queue.addLast('c');
  queue.addFirst('a');
  print(queue);                  // {a, b, c}
  print(queue.removeFirst());    // a
  print(queue.removeLast());     // c
  print(queue.length);           // 1
}

Calling removeFirst on an empty queue throws a StateError, so check isEmpty first. Two classes implement Queue:

  • ListQueue<E> stores items in a growing circular buffer. It is what Queue() gives you, and it is the best default: compact and fast.
  • DoubleLinkedQueue<E> stores each item in a node linked to its neighbours. Its special feature is an entry API (firstEntry(), lastEntry(), append, prepend, remove) that lets you insert and remove next to an element you already hold in constant time.

A queue is the natural tool for first-in, first-out jobs: breadth-first search, task lists, undo history and sliding windows.

TypeScript A double-ended queue (TypeScript stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

LinkedList

Dart's LinkedList<E> is an intrusive linked list: the elements themselves are the nodes. Each element must extend LinkedListEntry, which gives it next, previous, list, unlink(), insertAfter and insertBefore:

DART
import 'dart:collection';

base class Task extends LinkedListEntry<Task> {
  final String title;
  Task(this.title);

  @override
  String toString() => title;
}

void main() {
  var tasks = LinkedList<Task>();
  var write = Task('write');
  tasks.add(write);
  tasks.add(Task('test'));
  write.insertAfter(Task('review'));

  print(tasks);                  // (write, review, test)
  print(write.next);             // review
  write.next!.unlink();          // removes 'review' without searching
  print(tasks.length);           // 2
}

An element can belong to only one LinkedList at a time (adding it to a second list throws), and you cannot store plain ints or Strings. In exchange you get constant-time removal once you hold the element. Most programs never need it: reach for a Queue or a List first.

Hash-based and sorted sets and maps

The default {} map and set literals create a LinkedHashMap and LinkedHashSet, which remember insertion order. The library lets you choose differently:

Class Iteration order Lookup speed Notes
HashMap, HashSet not specified fastest lowest memory; do not rely on the order
LinkedHashMap, LinkedHashSet insertion order fast the default for literals
SplayTreeMap, SplayTreeSet sorted by key or element logarithmic needs keys that can be compared

The hash classes accept custom equals and hashCode functions, so you can make a case-insensitive set. They also have an identity() constructor that compares with identical instead of ==:

DART
import 'dart:collection';

void main() {
  var names = HashSet<String>(
    equals: (a, b) => a.toLowerCase() == b.toLowerCase(),
    hashCode: (s) => s.toLowerCase().hashCode,
  );
  names.addAll(['Ada', 'ada', 'ADA', 'Grace']);
  print(names.length);           // 2

  var scores = SplayTreeMap<int, String>()
    ..[50] = 'pass'
    ..[10] = 'low'
    ..[90] = 'top'
    ..[70] = 'good';
  print(scores.keys);            // (10, 50, 70, 90)
  print(scores.firstKey());      // 10
  print(scores.lastKey());       // 90
  print(scores.lastKeyBefore(70));  // 50
  print(scores.firstKeyAfter(70));  // 90
}

SplayTreeMap and SplayTreeSet keep their contents sorted at all times and answer "what comes just before or after this?" quickly (lastKeyBefore, firstKeyAfter, and for sets lastBefore and firstAfter). Pass a compare function to sort in a custom order, such as descending. The tree reshapes itself on reads, so do not modify it while iterating.

Unmodifiable views

UnmodifiableListView, UnmodifiableSetView and UnmodifiableMapView wrap an existing collection and reject changes. They are views, not copies: if the original changes, the view shows the change. That makes them ideal for returning internal state from a class without exposing the mutable collection:

DART
import 'dart:collection';

class Playlist {
  final List<String> _songs = [];
  void add(String song) => _songs.add(song);

  // Callers can read, but cannot add or remove.
  UnmodifiableListView<String> get songs => UnmodifiableListView(_songs);
}

List.unmodifiable(source) is different: it makes a snapshot copy that never changes. Use a view when you want live read-only access and a copy when you want a frozen value.

TypeScript Sorted keys and views versus copies (TypeScript stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

The separate package:collection adds more structures that dart:collection lacks, such as PriorityQueue (a heap), QueueList and CanonicalizedMap, plus helpers like groupBy and mergeSort. See Libraries and Packages for adding packages.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which collection should you pick for fast adds and removes at both ends?

    A Queue (ListQueue by default) handles both ends in constant time on average, whereas removing from the front of a List shifts every element.
  2. 2. What does the default {} map literal create?

    Map and Set literals produce LinkedHashMap and LinkedHashSet, so iteration follows insertion order.
  3. 3. What is true of an UnmodifiableListView?

    A view wraps the original, so it reflects later changes while refusing changes through the view. List.unmodifiable is the one that copies.
  4. 4. What must the elements of a LinkedList extend?

    LinkedList is intrusive: each element is its own node and must extend LinkedListEntry, which provides next, previous and unlink.

Summary

  • dart:collection supplies specialised collections; import it explicitly.
  • Queue (usually a ListQueue) is the right tool for fast work at both ends; removeFirst on an empty queue throws.
  • LinkedList needs elements that extend LinkedListEntry; use it only when you need constant-time unlinking.
  • HashMap/HashSet are unordered, LinkedHash* keeps insertion order (the literal default) and SplayTree* stays sorted and supports before/after lookups.
  • Unmodifiable*View wraps live data read-only; List.unmodifiable copies.

Next, write code that works for many types at once with Generics.