The List class implements the Iterable interface and intensively uses the indexed order to iterate over elements in the collection. The List class can be of a fixed or variable length. A fixed-length list can only be created by a constructor with a specific number of elements: new List(5). The fixed-length type has restrictions on all operations changing the length of the list and finishing with UnsupportedError. The features of the fixed-length type are as follows:

The variable list returns as a result of the new List() or [] operations. It has an internal buffer and dynamically changes its size when needed. Any attempt to change the length of the List class during iteration will result in ConcurrentModificationError. The following diagram shows the hierarchy of the list-based classes:

Dart always creates an instance of the List class as a result of instantiation. If the standard implementation of the List class is not enough, you can create your own implementation; just extend the ListBase class to align with your needs, as shown in the following code:

import "dart:collection";

class NewList<E> extends ListBase {
  final List<E> _elements;
  
  NewList() :_elements = new List<E>();
  
  @override
  operator [](int index) {
    return _elements[index];
  }

  @override
  void operator []=(int index, value) {
    _elements[index] = value;
  }

  @override
  int get length => _elements.length;

  @override
  void set length(int newLength) {
    _elements.length = newLength;
  }
}

You might be surprised to know that you need to implement only four methods to have a fully functional list-based class. This is because the other methods of the ListBase class use those four main methods to manage the internal buffer and iterate over elements. If you do not desire to extend the ListBase class, you can use ListMixin as follows:

class OtherList<E> extends MainList with ListMixin<E> {
  // ...
}

The List class interface supports ordering via a sort method.

Sometimes, we need to randomly rearrange the elements in the List class. The shuffle method of the List class can come in handy while doing that:

import 'dart:math';

main() {
  var list = new List.from([1, 2, 3, 4, 5]);
  print(list);
  // => [1, 2, 3, 4, 5]
  // Crete seed to initialize internal state of 
  // random-number generator
  var seed = new DateTime.now().millisecondsSinceEpoch;
  // Create instance of generator 
  var random = new Random(seed);
  // Re-arrange elements in list
  list.shuffle(random);
  print(list);
   // => [4, 5, 1, 3, 2]
}

Run the preceding code snippet a couple of times and see the different results of the shuffle operation.

The LinkedList class is a double-linked list. A LinkList class is a collection of elements of the same data type, and it is efficient when it comes to the insertion and deletion of elements of a complex structure. Despite the name, it has nothing in common with the List class.

Let's take a look at the class hierarchy of the LinkedList class:

All the elements in LinkedList are based on LinkedListEntry and connected through pointers. Each LinkedListEntry class has a pointer field pointing to the next and previous elements in the list. It contains the link of the LinkedList instance it belongs to. Before adding the element to another LinkedList class, it must be removed from the current one. If it is not, StateError is thrown. Each element of the LinkedList class knows its own position, so we can use methods such as addBefore, addAfter, or unlink of LinkedListEntry to manipulate them:

import "dart:collection";

We must create a wrapper class Element based on LinkedListEntry to keep our elements, as shown in the following code:

class Element<E> extends LinkedListEntry {
  final E value;
  Element(this.value);
  @override
  String toString() => value != null ? value.toString() : null;
}

Here, we create the LinkedList instance and use the Element wrapper:

main() {
  LinkedList<Element> list = new LinkedList<Element>();
  Element b = new Element("B");
  list.add(b);
  //
  b.insertAfter(new Element("A"));
  b.insertBefore(new Element("C"));
  print(list);
  // => (C, B, A)
  b.unlink();
  print(list);
  // => (C, A)
}

Finally, we use insertAfter, insertBefore, and unlink of the Element methods to manipulate these elements. The advantages of LinkedList are as follows:

The disadvantages of LinkedList are as follows:

The Set class is a collection that cannot contain identical elements. It does not allow indexed access to an element in the collection, so only the iterator and for-each loop methods can traverse elements of a Set class:

void main() {
  var aset = new Set.from([3, 2, 3, 1]);
  print(aset);
  // => {3, 2, 1}
}

A Set class can contain at most one null element.

The Set class can return a new set as a result of the execution of the intersection method between its internal collection and the other one:

main() {
  var aset = new Set.from([3, 2, 3, 1]);
  print(aset);
  // => {3, 2, 1}
  var other = new Set.from([2, 1, 5, 6]);
  print(other);
  // => {2, 1, 5, 6}
  var intersect = aset.intersection(other);
  print(intersect);
  // => {2, 1}
}

The union method returns a new Set class that contains all the elements in its internal collection and the other one:

main() {
  var aset = new Set.from([3, 2, 3, 1]);
  print(aset);
  // => {3, 2, 1}
  var other = new Set.from([2, 1, 5, 6]);
  print(other);
  // => {2, 1, 5, 6}
  var union = aset.union(other);
  print(union);
  // => {3, 2, 1, 5, 6}
}

If you need to find the difference between the elements of a certain collection and other collections, use the difference method of the Set class as follows:

main() {
  var aset = new Set.from([3, 2, 3, 1]);
  print(aset);
  // => {3, 2, 1}
  var other = new Set.from([2, 1, 5, 6]);
  print(other);
  // => {2, 1, 5, 6}
  var difference = aset.difference(other);
  print(difference);
  // => {3}
}

Here is the class hierarchy of the set-based classes:

import 'dart:collection';

void main() {
  var hset = new HashSet.from([3, 2, 3, 1]);
  print(hset);
  // => {1, 2, 3}
}

import 'dart:collection';

void main() {
  var hset = new HashSet(equals:(e1, e2) {
    return e1 == e2;
  }, hashCode:(e) {
    return e.hashCode;
  });
  hset.addAll([3, 2, 3, 1]);
  print(hset);
  // => {1, 2, 3}
  hset.add(1);
  print(hset);
  //  => {1, 2, 3}
}

import 'dart:collection';

void main() {
  var hset = new LinkedHashSet();
  hset.addAll([3, 2, 3, 1]);
  print(hset);
  // => {3, 2, 1}
  hset.add(1);
  print(hset);
  //  => {3, 2, 1}
}

SplayTreeSet

Last but not least, SplayTreeSet is a class that maintains the collection in a sorted order, but is slow when it comes to lookups and updates. It extends a _SplayTree class. Class_SplayTree is a self-balancing binary search tree (BST). The time taken by most operations in BST is proportional to the height of the tree, and it is better to keep it small. Self-balancing BST reduces the height by performing tree transformation at logarithmic time, O(log(n)), where n is the height of the tree. The following diagram shows the hierarchy of classes:

By default, a SplayTreeSet class assumes that all elements are comparable and uses an object-compare method to order them. In my example, I have added an array of strings to SplayTreeSet:

import 'dart:collection';

main() {
  var sset = new SplayTreeSet();
  sset.addAll(['33', '2', '33', '10']);
  print(sset);
  // => (10, 2, 33)
}

The order of the result is correct from the perspective of comparing the strings, but we have to order them with respect to the integer values to represent them as strings. To fix this problem, we can pass the compare function as an argument of the constructor:

import 'dart:collection';

main() {
  var sset = new SplayTreeSet((e1, e2) {
    return int.parse(e1).compareTo(int.parse(e2));
  });
  sset.addAll(['33', '2', '33', '10']);
  print(sset);
  // => (2, 10, 33)
}

Now the result looks exactly the way we want it to be.

A Queue class is a collection of elements that are added and removed in a specific order at both ends. It generally accepts null elements. A ListQueue class is the implementation of the general purpose Queue class. It uses a List instance to keep the collection elements and uses head and tail pointers to manipulate them. The ListQueue class implementation is a very efficient solution for any queue or stack usage with a small memory footprint, as shown in the following code:

import 'dart:collection';

void main() {
  var queue = new Queue();
  queue.add(2);
  queue.add(3);
  queue.addFirst(1);
  print(queue);
  // => {1, 2, 3}
  queue.removeLast();
  print(queue);
  // => {1, 2}
}

Here is the class hierarchy of Queue:

The initial capacity of ListQueue is eight elements, and can be changed by passing another number as an argument of the constructor. Actually, this value will be rounded up to the nearest power of two. It always checks the number of elements in queue and grows an internal collection automatically via the creation of a new List instance and copying elements from the old one to the new one. The removal of elements is performed by moving elements one by one to fill the hole. The Queue class does not reduce the size of an internal collection when it removes elements. Elements in a Queue class can be traversed via a for-each loop or within an Iterator.

The Map class is a collection of key-value pairs. Each key has a reference to only one value. It does not allow duplicate keys, but allows duplicate values. The Map class is not a subtype of the Iterator, IteratorBase, or even IteratorMixin. The Map class provides separate iterators for keys and values:

void main() {
  var map = new Map.fromIterables([3, 2, 1], ['3', '2', '1']);
  print(map);
  // => {3: 3, 2: 2, 1: 1}
}

The Map class allows you to use the null value as a key. Each of the Map class implementations behave a little differently with respect to the order of elements when iterating the map. A key of the Map class must implement the equals operator and the hashCode method.

The Map class doesn't support duplicate keys. It has a putIfAbsent method to look up the value of the key or add a new value if it is not present, as shown in the following code:

void main() {
  var map = new Map.fromIterables([3, 2, 1], ['3', '2', '1']);
  print(map);
  // => {3: 3, 2: 2, 1: 1}
  map.putIfAbsent(3, () => '33'),
  map.putIfAbsent(4, () => '4'),
  print(map);
  // => {3: 3, 2: 2, 1: 1, 4: 4}
}

This method adds key-value pairs only if the key is absent. The containsKey and containsValue methods return the search result:

void main() {
  var map = new Map.fromIterables([3, 2, 1], ['3', '2', '1']);
  print(map);
  // => {3: 3, 2: 2, 1: 1}
  print(map.containsKey(1));
  // => true
  print(map.containsKey(5));
  // => false
  print(map.containsValue('2'));
  // => true
  print(map.containsValue('55'));
  // => false
}

Here is the hierarchy of the Map class:

import 'dart:collection';

void main() {
  var map = new HashMap.fromIterables([2, 3, 1], ['2', '3', '1']);
  print(map);
  // => {2: 2, 1: 1, 3: 3}
}

import 'dart:collection';

void main() {
  var map = new LinkedHashMap.
      fromIterables([3, 2, 1], ['3', '2', '1']);
  print(map);
  // => {3: 3, 2: 2, 1: 1}
  map.remove(3);
  map[3] = '3';
  print(map);
  // => {2: 2, 1: 1, 3: 3}
}

import 'dart:collection';

void main() {
  var map = new LinkedHashMap(equals: (e1, e2) {
    return e1 == e2;
  }, hashCode: (e) {
    return e.hashCode;
  });
  map.addAll({3: '3', 2: '2', 1: '1'});
  print(map);
  // => {3: 3, 2: 2, 1: 1}
  map.remove(3);
  map[3] = '3';
  print(map);
  // => {2: 2, 1: 1, 3: 3}
}

SplayTreeMap

The SplayTreeMap class is an ordered map that maintains a collection in a sorted order, but is slower when it comes to lookups and updates. This class is based on the _SplayTree class and also on SplayTreeSet. The SplayTreeMap class is a self-balancing binary search tree, as shown in the following diagram:

In the following code, the keys of the map are compared with the compare function passed in the constructor:

import 'dart:collection';

void main() {
  var map = new SplayTreeMap((e1, e2) {
    return e1 > e2 ? 1 : e1 < e2 ? -1 : 0;
  });
  map.addAll({3: '3', 2: '2', 1: '1'});
  print(map);
  // => {1: 1, 2: 2, 3: 3}
  map.remove(3);
  map[3] = '3';
  print(map);
  // => {1: 1, 2: 2, 3: 3}
}

By default, a SplayTreeMap function assumes that all the keys are comparable and uses an object-compare method to compare the keys of elements.