dart:collection
A specialized double-linked list of elements that extends LinkedListEntry.
This is not a generic data structure. It only accepts elements that extend the LinkedListEntry class. See the Queue implementations for generic collections that allow constant time adding and removing at the ends.
This is not a List implementation. Despite its name, this class does not implement the List interface. It does not allow constant time lookup by index.
Because the elements themselves contain the links of this linked list, each element can be in only one list at a time. To add an element to another list, it must first be removed from its current list [if any].
In return, each element knows its own place in the linked list, as well as which list it is in. This allows constant time LinkedListEntry.insertAfter, LinkedListEntry.insertBefore and LinkedListEntry.unlink operations when all you have is the element.
A LinkedList also allows constant time adding and removing at either end, and a constant time length getter.
Inheritance- Object
- Iterable
- LinkedList
Constructors
LinkedList[] Construct a new empty linked list.Properties
first → E Returns the first element. [...] isEmpty → bool Returns true if there are no elements in this collection. [...] iterator → Iterator Returns a new Iterator that allows iterating the elements of this Iterable. [...] last → E Returns the last element. [...] length → int Returns the number of elements in this. [...] single → E Checks that this iterable has only one element, and returns that element. [...] hashCode → int The hash code for this object. [...] isNotEmpty → bool Returns true if there is at least one element in this collection. [...] runtimeType → Type A representation of the runtime type of the object.Methods
add[E entry] → void Add entry to the end of the linked list. addAll[Iterable entries] → void Add entries to the end of the linked list. addFirst[E entry] → void Add entry to the beginning of the linked list. clear[] → void Remove all elements from this linked list. forEach[void action[E entry]] → void Call action with each entry in this linked list. [...] Remove entry from the linked list. [...] any[bool test[E element]] → bool Checks whether any element of this iterable satisfies test. [...] cast[] → Iterable Provides a view of this iterable as an iterable of R instances. [...] contains[Object element] → bool Returns true if the collection contains an element equal to element. [...] elementAt[int index] → E Returns the indexth element. [...] every[bool test[E element]] → bool Checks whether every element of this iterable satisfies test. [...] expand[Iterable f[E element]] → Iterable Expands each element of this Iterable into zero or more elements. [...] firstWhere[bool test[E element], { E orElse[] }] → E Returns the first element that satisfies the given predicate test. [...] fold[T initialValue, T combine[T previousValue, E element]] → T Reduces a collection to a single value by iteratively combining each element of the collection with an existing value [...] followedBy[Iterable other] → Iterable Returns the lazy concatentation of this iterable and other. [...] join[[String separator = "" ]] → String Converts each element to a String and concatenates the strings. [...] lastWhere[bool test[E element], { E orElse[] }] → E Returns the last element that satisfies the given predicate test. [...] map[T f[E e]] → Iterable Returns a new lazy Iterable with elements that are created by calling f on each element of this Iterable in iteration order. [...] noSuchMethod[Invocation invocation] → dynamic Invoked when a non-existent method or property is accessed. [...] reduce[E combine[E value, E element]] → E Reduces a collection to a single value by iteratively combining elements of the collection using the provided function. [...] singleWhere[bool test[E element], { E orElse[] }] → E Returns the single element that satisfies test. [...] skip[int count] → Iterable Returns an Iterable that provides all but the first count elements. [...] skipWhile[bool test[E value]] → Iterable Returns an Iterable that skips leading elements while test is satisfied. [...] take[int count] → Iterable Returns a lazy iterable of the count first elements of this iterable. [...] takeWhile[bool test[E value]] → Iterable Returns a lazy iterable of the leading elements satisfying test. [...] toList[{bool growable: true }] → List Creates a List containing the elements of this Iterable. [...] toSet[] → Set Creates a Set containing the same elements as this iterable. [...] toString[] → String Returns a string representation of [some of] the elements of this. [...] where[bool test[E element]] → Iterable Returns a new lazy Iterable with all elements that satisfy the predicate test. [...] whereType[] → Iterable Returns a new lazy Iterable with all elements that have type T. [...]Operators
operator ==[dynamic other] → bool The equality operator. [...]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. The main collection types in Dart are: Lists are 0-indexed collections of objects with a length. Sets are collections of objects in which every object can only occur once.Common Collection Types
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.
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 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: [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:
- [] 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: {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:
- {} 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: {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:
- {} 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 hashCode implementation.
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 hashCode implementation.
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.
Now that you have seen all the collections available in Dart, it is time to put that knowledge into practice.
Open up a project of yours and search for any collection usage. Analyse the problem you are trying to solve and pick up the most suitable collection that can solve your problem.
Having the details of every collection in mind, you can use this simple cheat sheet to check the running time complexity of the operations you are interested in.
If you found the information useful, don’t forget to 👏!
Until next time! 😀