Collections are a set of interfaces and classes that implement highly optimised data structures. They reduce the programming effort and improve the performance of the code if chosen carefully.

In this article, you will see the strengths and weaknesses of all the collections to enable you to choose the perfect fit for your use case.

Choosing the right collection solves 90% of the problem — managing it is the remaining part and it comes naturally after selecting the right one.

Before jumping into the more complex collections available, let’s have a look at the most common collection types in Dart.

Common Collection Types

The main collection types in Dart are:

• List
• Set
• Map

Lists are 0-indexed collections of objects with a length.
In other programming languages, they are called arrays.
Lists are Iterable and the iteration occurs in the index order. If the length of the list is changed during an iteration, a ConcurrentModificationError is thrown.

Sets are collections of objects in which every object can only occur once.
Two objects are considered indistinguishable, hence can occur only once, if they are equal with regard to the Object.== operator.
Sets are Iterable and the order of iteration depends on the specific Set implementations.

Maps are collections of key/value pairs, from which you retrieve a value using its associated key.
Every key in the map is unique.
Maps and the keys and values are Iterable and the order of iteration depends on the specific Map implementations.

Collection Literals

Collection literals are a syntactic expression that evaluates to an aggregate collection type.

In Dart, collection literals are preferred over unnamed constructor instantiation of collections. (see relevant Effective Dart tip)

List literal

The syntax of the list literal is: <elementType>[elements].
It creates an object of type _GrowableList.

If not specified, the element type can be inferred from the list of elements.
If the element type is neither specified nor inferred, then it is considered dynamic.

For example:

• <int>[] creates an empty List of int elements
• ["Hello", "World"] creates a 2-elements List of Strings.
• [] creates an empty List of dynamic elements

A _GrowableList is an internal type that represents a growable List. It keeps an internal buffer that grows when necessary. This guarantees that a sequence of add operations will each execute in amortized constant time.

Set literal

The syntax of the set literal is: <elementType>{elements}.
It creates an object of type _CompactLinkedHashSet.

If not specified, the element type can be inferred from the set of elements.
If the element type is neither specified nor inferred, then a Map is created instead.

For example:

• <int>{} creates an empty Set of int elements
• {"Hello", "World"} creates a 2-elements Set of String.

A _CompactLinkedHashSet is an internal type that represents an optimized LinkedHashSet. It keeps track of the order that the elements were inserted.

Iteration is done in the order that the elements were inserted. Adding an element that is already in the set does not change its iteration position in the iteration order. However, removing an element and adding it again, will make it the last element in the iteration order.

Map literal

The syntax of the map literal is: <keyType, valueType>{elements}.
It creates an object of type _InternalLinkedHashMap.

If not specified, the key type and the value type can be inferred from the map of elements.
If types are neither specified nor inferred, then they are considered dynamic.

For example:

• <String, int>{} creates an empty Map of String/int key/value elements.
• {“Hello”: 123} creates a single-element Map of String/int key/value elements.
• {} creates an empty Map of dynamic/dynamic key/value elements.

An _InternalLinkedHashMap is an internal type that represents an optimised LinkedHashMap. The insertion order of the keys is remembered.

Values are iterated in the associated key’s order.
Changing a key’s value, when already present in the map, does not change the iteration order.
However, removing a key, and adding it again, will make it the last element of the map.

Until now, you have seen the most common collections used in Dart. However, this is just the tip of the iceberg.

Depending on the problem you are trying to solve, you can choose a better performing collection.

LinkedList

A LinkedList is a specialised double-linked list of elements that extend LinkedListEntry.

Despite its name, LinkedList is not an implementation of List, hence it does not provide constant-time index lookup.

Since every LinkedListEntry element knows its position in the list, this enables constant time insertAfter, insertBefore and unlink operations on the LinkedListEntry elements.

The LinkedList allows constant-time adding and removing at either end, as well as constant-time length getter.

Queue

A Queue is a collection that can be manipulated at both ends.
As Queue is an abstract class in Dart, there are two main implementations available:

• ListQueue
• DoubleLinkedQueue

ListQueue keeps a cyclic buffer of elements. When the buffer fills up, it doubles its size to accommodate the new items.

It guarantees constant time peek and remove operations and amortized constant-time for add operations (due to buffer size adjustments).

DoubleLinkedQueue is a Queue implementation based on a double-linked list.

It allows constant-time add, remove-at-ends and peek operations.

HashSet

A HashSet is an unordered hash-table implementation of Set.

All the elements of a HashSet must have consistent equality and hashCodeimplementation.

Depending on the distribution of hash codes of the elements, the add, remove, contains and length operations run in potentially amortized constant time.

Since the elements of a HashSet are not ordered, iteration order is unspecified, but it is consistent between changes to the set.

SplayTreeSet

A SplayTreeSet is a self-balancing binary tree implementation of Set. It allows most operations in amortized logarithmic time.

The elements of the set can be ordered relative to each other using a compare function that is passed in the constructor.

If the compare function is omitted, the objects have to be Comparable and compared using their Comparable.compareTo method.

HashMap

Like the HashSet, a HashMap is an unordered hash-table implementation of Set.

The keys of a HashMap must have consistent equality and hashCodeimplementation.

Simple operations are done in (potentially amortized) constant time: add, contains, remove, and length, given that the hash codes of objects are well distributed.

Iteration order of keys, values and entries is unspecified and might happen in any order but is consistent between changes. Values are iterated in the same order as their associated keys — iterating keys and values in parallel will give matching key/value pairs.

SplayTreeMap

A SplayTreeMap is a Map implementation based on a self-balancing binary tree. It allows most single-entry operations is amortized logarithmic time.

Keys of the map are compared using the compare function passed in the constructor.

If the compare function is omitted, then the keys are considered to be Comparable and their associated Comparable.compareTo functions are used for setting their order in the map.

Conclusion

If you found the information useful, don’t forget to ?!

Until next time! ?