DATA STRUCTURE | COLLECTIONS

Dart on focus: Lists, Sets, and Queues

All Iterable Collections in Dart

In programming, when we want to store a collection of similar data, the language provides an array-like structure.

The same thing happens on Dart. The most popular way to aggregate related data is with a List class.

However, What is a List? What type of lists do we have? What other data structure do we have to iterate throw a list o elements?

It’s time to search for answers! Good people, follow my lead!

Collections and Iterables

Dart structures that group elements are called Collections. And they can be found in the dart:collection library.

Between the available collections, we have the iterable ones. Being iterable means the class implements the abstract class Iterable.

An Iterable is a collection of elements that can be accessed sequentially.

— dart.dev

So, a class that implements the Iterable must provide a way to move sequentially in a group of data, as the capacity to manage/access any individual value.

Is worth saying that there is more than one way to move, access, or manage data respecting the Iterable contract.

Lists

The most popular Iterable collection, but it’s not from the dart:collection lib. It is defined in the dart:core library.

A list of general purposes, and the interesting part is how it manages the length. There are two kinds of List: Fixed-Length and Growable (the default).

Fixed-length

The fixed-length list can’t change its size, meaning there is no way to remove or add a value.

To create one, we need to use one of the constructors of the List class setting the growable parameter as false;

List<int> fixedList = List.of([1, 2, 3], growable: false);
fixedList.add(4); // throws an error

Growable

The growable List is what we usually use since in every constructor the default value of the growable parameter is true.

As you can imagine this list can be expanded and diminished as we want.

List<int> growableList = <int>[1, 2, 3];
print(growableList.length); // 3
fixedList.add(4);
print(growableList.length); // 4

Sets

The word “Sets” probably reminds you of your high school days. I’m glad to say your studies about sets weren't in vain.

Sets, in Dart, are collections that don’t like duplicated values. they are also defined in the dart:core library.

A collection of objects in which each object can occur only once.

That is, for each object of the element type, the object is either considered to be in the set, or to not be in the set.

— dart.dev

We should try it. Notice how the initial value of set has a duplicated value.

Set<String> set = {"Cloud", "Vincent", "Cloud"};
print(set); // {"Cloud", "Vincent"}
set.add("Cloud");
print(set); // {"Cloud", "Vincent"}
set.add("Sephiroth");
print(set); // {"Cloud", "Vincent", "Sephiroth"}

As a Set looks for duplications, we must override the == operator and hashCode implementations.

As I said, you won’t regret the sets studies. Out Set class comes with some boolean operations that we learned and love.

The Set class implements methods like union, difference, intersection.

A curiosity is that Set is an abstract class, meaning it can’t be directly initiated. What you saw was a shortcut created by Dart.

The default Set implementation, LinkedHashSet.

Set<String> set = {"Cloud", "Vincent"};
print(set.runtimeType); // _CompactLinkedHashSet<String>

Which is a based hash-table Set implementation that keeps the track of insertion order.

Finally, You should consider using Sets when duplications are not allowed.

Note: Besides the List and Sets classes, any other structure presented here is found in the dart:collection library.

Queues and ListQueues

First, What is a Queue?

A Queue is a data structure that we can interact with just with the first or the last element.

In Dart, the Queue is an abstract class, meaning that you can’t instantiate it, but we have some classes that extend it like the ListQueue.

When you instantiate a Queue what happens is the creation of a QueueList class, which is the most basic Queue class.

final queue = Queue<int>();
print(queue.runtimeType); // ListQueue<int>

Yet, you can be more specific as well

final queue = ListQueue<int>();

The Queue class is an Iterable that provides us with functions like addFirst, addLast, removeFirst, removeLast. We also have the getters first and last from the Iterable class.

final ListQueue<String> queue = ListQueue.of(["Brazil", "Germany", "Italy"]);
queue.add("United State");
queue.addFirst("Australia");
queue.addLast("Vietnam");
queue.removeFirst(); // Remove Australia
print(queue); // {Brazil, Germany, Italy, United State, Vietnam}

So, any element in the middle of a Queue is inaccessible?

In Theory, the idea is to avoid having access to them, but Dart is like a mother searching for her children's approval… always flexible!

With that said, there is no direct option to add value in the middle of a Queue. However, remotion is possible just through remove function.

final queue = ListQueue.of(["Brazil", "Germany", "Italy"]);
queue.remove("Germany");
print(queue); // {Brazil, Italy}

You also can make a workaround by creating a copy of the queue without some elements through filter functions like where.

ListQueue should be used every time you want to avoid a programmer making an insertion in the middle of a list. Another advantage over the List is efficiency.

This guarantees constant time peek and remove operations, and amortized constant time add operations.

This concludes our talk about the main iterable collections of Dart. Let’s dive more deeply into more specific classes.

HashSet

A HashSet is the same as a Set but unordered.

An unordered hash-table based Set implementation — dart.dev

This means through iteration there is no guarantee will the elements will be in the input order or can be sorted.

final hashSet = HashSet.from({'Hello', 'World', '!'});
print(hashSet); // {World, Hello, !}

If we can work with an ordered Set, why would we choose the HashSet?

Good question, quick answer. With fewer guarantees, we can expect more performance!

LinkedList

Despite its name a LinkedList does not implement the List class but is an Iterable, so is worth talking about here.

It is a data structure that implements a Double Linked List. In other words, each element knows its own next and previous element.

Single Linked List only knows the next element. Double Liked List also know the previous one | Source: Cristopher Webb

The LinkedList class only accepts LinkedListEntry (abstract class) as elements. And the LinkedListEntry possesses a next and aprevious getter.

class EntryItem extends LinkedListEntry<EntryItem> {
  final String text;
  EntryItem(this.text);

  @override
  String toString() {
    return text;
  }
}

final linkedList = LinkedList<EntryItem>();
linkedList.addAll([EntryItem('Hello'),EntryItem('World'), EntryItem('!')]);
print(linkedList.first.previous); // null
print(linkedList.first.next); // World
print(linkedList.last.previous); // World
print(linkedList.last.next); // null

This Double Linked List data structure is useful when we want to represent a graph or a tree in our code.

DoubleLinkedQueue

If the List can do it, the Queue also can!

The DoubleLinkedQueue is a Double Linked List based on the Queue class.

As the LinkedList, only Objects extended of DoubleLinkedQueueEntry are allowed in this List, or… they should be.

DoubleLinkedQueue extension and interface

The fact is, DoubleLinkedQueueEntry is not a must! Since its generics says that any element E can be stored in the DoubleLinkedQueue.

Author’s note: To be honest, I don’t have a clue of why the Flutter team did this, because without the nextEntry() and previousEntry() from the DoubleLinkedQueueEntry, use a DoubleLinkedQueue has no sense.

Let's stick with the logic of using the DoubleLinkedQueueEntry. The use of the DoubleLinkedQueueEntry is a bit different from LinkedList.

class QEntryItem extends DoubleLinkedQueueEntry<String> {
  final String text;
  QEntryItem(this.text) : super(text);

  @override
  String toString() {
    return text;
  }
}

final linkedQueue = DoubleLinkedQueue<QEntryItem>();
linkedQueue.addAll([QEntryItem('Hello'),QEntryItem('World'), QEntryItem('!')]);
print(linkedQueue.first); // Hello
print(linkedQueue.first.previousEntry()); // null
print(linkedQueue.first.nextEntry()); // null
print(linkedQueue.last); // !
print(linkedQueue.last.previousEntry()); // null
print(linkedQueue.last.nextEntry()); // null

When you use the add function in a DoubleLinkedQueue, the nextEntry and previousEntry are not settled automatically.

The correct usage is to use DoubleLinkedQueueEntry as a root element and invoke the append and prepend from it to add new elements with the type E of the DoubleLinkedQueueEntry.

Confusing… here is an example.

final linkedQueue = DoubleLinkedQueue<QEntryItem>();
linkedQueue.add(QEntryItem('Hello'));
linkedQueue.first.append('World');
linkedQueue.first.nextEntry()?.append('!');
print(linkedQueue.first); // Hello
print(linkedQueue.first.nextEntry()?.element); // World
print(linkedQueue.first.nextEntry()?.nextEntry()?.element); // !

linkedQueue.first.nextEntry()?.nextEntry()?.prepend("I'm Goku");
print(linkedQueue.first); // Hello
print(linkedQueue.first.nextEntry()?.element); // World
print(linkedQueue.first.nextEntry()?.nextEntry()?.element); // I'm Goku
print(linkedQueue.first.nextEntry()?.nextEntry()?.nextEntry()?.element); // !

The good thing about DoubleLinkedQueue is to keep the performance of a Queue with constant time for peek and removal operations, and low cost for adding something.

SplayTreeSet

One more Set object. This Set behavior is like a priority queue, where each value is inserted in a specific position relative to other elements.

The set is based on a self-balancing binary tree. It allows most operations in amortized logarithmic time

— api.flutter.dev

In other words, a Set that efficiently calls sort every time you insert something in it. =)

On the constructor, you need to provide a comparable function to the SplayTreeSet to know the order of the element.

final splayTreeSet = SplayTreeSet<String>((a, b) => a.compareTo(b));
splayTreeSet.add('Orange');
splayTreeSet.addAll({'Apple', 'Grapes', 'Strawberry', 'Banana'});
print(splayTreeSet); // {Apple, Banana, Grapes, Orange, Strawberry}

The function compare is used for ordering and equality. As Sets do not accept duplications, if values a and b are equal to 0, then b is ignored.

If we call contains function on a value in which the comparable function reaches 0 for some internal value, then it returns true;

final splayTreeSet = SplayTreeSet<TreeItem>((a, b) => a.id.compareTo(b.id));
splayTreeSet.add(TreeItem(1, 'Monkey'));
splayTreeSet.addAll({TreeItem(1, 'Cat'), {TreeItem(2, 'Horse'), TreeItem(3, 'Turtle')});
print(splayTreeSet); // {1: Monkey, 2: Horse, 3: Turtle}
print(splayTreeSet.contains(TreeItem(1, 'Dog'))); // true

SplayTreeSet is a handful class for when you want to keep your data sorted and without duplications.

UnmodifiableListView

This class creates a copy of an existing List class and follows its changes, but this copy cannot be modified.

final numbers = <int>[10, 20, 30];
final unmodifiableListView = UnmodifiableListView(numbers);

// Insert new elements into the original list.
numbers.addAll([40, 50]);
print(unmodifiableListView); // [10, 20, 30, 40, 50]

unmodifiableListView.remove(20); // throws an error

Use it when you want to watch a List without being able to modify it.

UnmodifiableSetView

Same thing as UnmodifiableListView, but now with Sets.

inal numbers = <int>{10, 20, 30};
final unmodifiableSetView = UnmodifiableSetView(numbers);

// Insert new elements into the original list.
numbers.addAll([40, 50]);
print(unmodifiableSetView); // [10, 20, 30, 40, 50]

unmodifiableSetView.remove(20); // throws an error

Use it when you want to watch a Set without being able to modify it.

Conclusion

Phew! Who would guess we have so many data structures ready to use in Dart? The popular List class is the most permissive and can be used in any situation.

Although, more flexibility means more possibilities for mistakes. We should choose the least permissive data structure that works for us.

Finally, I still missing data structures like a circular queue and a stack, but we can’t complain about having few options.

Thanks for reading! If you want to read more of my thoughts and programming tips, then check out my articles and follow or subscribe for upcoming content.