Linked list dart
dart:collection Show 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
ConstructorsLinkedList() Construct a new empty linked list.Propertiesfirst → E Returns the first element. [...] isEmpty → bool Returns true if there are no elements in this collection. [...] iterator → IteratorMethodsadd(E entry) → void Add entry to the end of the linked list. addAll(IterableOperatorsoperator ==(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. Maps are collections of key/value pairs, from which you retrieve a value using its associated key. 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 literalThe syntax of the list literal is: If not specified, the element type can be inferred from the list of elements. For example:
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 literalThe syntax of the set literal is: If not specified, the element type can be inferred from the set of elements. For example:
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 literalThe syntax of the map literal is: If not specified, the key type and the value type can be inferred from the map of elements. For example:
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. 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. LinkedListA 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. QueueA Queue is a collection that can be manipulated at both ends.
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. HashSetA 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. SplayTreeSetA 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. HashMapLike 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. SplayTreeMapA 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! 😀 |