3. Basic Data Structures in Dart

Written by Kelvin Lau & Jonathan Sande

The dart:core library contains the core components of the Dart language. Inside, you’ll find a variety of tools and types to help create your Dart apps. Before you start building your own custom data structures, it’s important to understand the primary data structures that come with Dart.

This chapter will focus on the three main data structures that the dart:core library provides right out of the box: List, Map, and Set.

List

A list is a general-purpose, generic container for storing an ordered collection of elements, and it’s used commonly in all sorts of Dart programs. In many other programming languages, this data type is called an array.

You can create a list by using a list literal, which is a comma-separated list of values surrounded with square brackets. For example:

final people = ['Pablo', 'Manda', 'Megan'];

Dart defines List as an abstract class with methods for accessing and modifying the elements of the collection by index. Since Dart is platform-independent, how List is implemented under the hood depends on the underlying platform, whether that’s the Dart VM, or Dart compiled to JavaScript for the web, or native code running directly on your computer.

List, like most other Dart collections, is an Iterable. This means that you can step through the elements sequentially. All iterables have a length getter that returns the number of elements in the collection. While this could take O(n) time for iterables that need to count every element, List will efficiently return length in O(1) time.

Dart lists can also be growable or fixed-length. When you specify a fixed length for the list, Dart can be more efficient about the space it allocates. However, you won’t be able to add or remove elements anymore as you could in a growable list.

As with any data structure, there are certain notable traits that you should be aware of. The first of these is the notion of order.

Order

Elements in a list are explicitly ordered. Using the above people list as an example, 'Pablo' comes before 'Manda'.

All elements in a list have a corresponding zero-based integer index. For example, people has three indices, one corresponding to each element. You can retrieve the value of an element in the list by writing the following:

people[0] // 'Pablo'
people[1] // 'Manda'
people[2] // 'Megan'

Order is defined by the List data structure and should not be taken for granted. Some data structures, such as Map, have a weaker concept of order.

Random-Access

Random-access is a trait that data structures can claim if they can handle element retrieval in a constant amount of time. For example, getting 'Megan' from the people list takes constant time. Again, this performance should not be taken for granted. Other data structures such as linked lists and trees do not have constant time access.

List Performance

Aside from being a random-access collection, other areas of performance will be of interest to you as a developer. Particularly, how well or poorly does the data structure fare when the amount of data it contains needs to grow? For lists, this varies in two aspects.

Insertion Location

The first aspect is where you choose to insert the new element inside the list. The most efficient scenario for adding an element to a list is to add it at the end of the list:

people.add('Edith');
print(people); // [Pablo, Manda, Megan, Edith]

Inserting 'Edith' using the add method will place the string at the end of the list. This is an amortized constant-time operation, meaning the time it takes to perform this operation on average stays the same no matter how large the list becomes. Since Dart lists are backed by a buffer, if you keep adding elements, the buffer will fill up every so often. Then Dart will have to spend some extra time allocating more space for the buffer. That doesn’t happen very often, though, so the “amortized” part of amortized constant-time means that the occasional complexity bump gets averaged out over time and so the operation is still considered constant-time.

To help illustrate why the insertion location matters, consider the following analogy. You’re standing in line for the theater. Someone new comes along to join the lineup. What’s the easiest place to add people to the lineup? At the end, of course!

If the newcomer tried to insert themselves into the middle of the line, they would have to convince half the lineup to shuffle back to make room.

And if they were terribly rude, they would try to insert themselves at the head of the line. This is the worst-case scenario because every single person in the lineup would need to shuffle back to make room for this new person in front!

This is exactly how the list works. Inserting new elements anywhere aside from the end of the list will force elements to shuffle backwards to make room for the new element:

people.insert(0, 'Ray');
// [Ray, Pablo, Manda, Megan, Edith]

If the number of elements in the list doubles, the time required for this insert operation will also double.

If inserting elements in front of a collection is a common operation for your program, you may want to consider a different data structure to hold your data.

Capacity

The second factor that determines the speed of insertion is the list’s capacity. Underneath the hood, Dart lists are allocated with a predetermined amount of space for its elements. If you try to add new elements to a list that is already at maximum capacity, the list must restructure itself to make room for more elements. This is done by copying all the current elements of the list to a new and bigger container in memory. However, this comes at a cost. Each element of the list has to be visited and copied.

This means that any insertion, even at the end, could take n steps to complete if a copy is made. However, Dart employs a strategy that minimizes the times this copying needs to occur. Each time it runs out of storage and needs to copy, it doubles the capacity.

Note: The actual implementation details are determined by where your Dart code is running. For example, in the Dart VM, saying the capacity “doubles” is generally true, but the specific implementation in the internal VM file growable_array.dart is (old_capacity * 2) | 3.

Map

A map is collection that holds key-value pairs. For example, here’s a map containing users’ names and scores:

final scores = {'Eric': 9, 'Mark': 12, 'Wayne': 1};

The abstract Map class itself in Dart doesn’t have any guarantees of order, nor can you insert at a specific index. The keys of a map can be of any type, but if you are using your own custom type then that type needs to implement operator== and hashCode.

Although Map itself doesn’t guarantee an order, the default Dart implementation of Map is LinkedHashMap, which, unlike HashMap, promises to maintain the insertion order.

You can add a new entry to the map with the following syntax:

scores['Andrew'] = 0;

Since this is a LinkedHashMap under the hood, the new key-value pair will appear at the end of the map:

print(scores);
// {Eric: 9, Mark: 12, Wayne: 1, Andrew: 0}

That is not the case with HashMap, which you can observe if you import dart:collection:

import 'dart:collection';

And then add the following code below what you wrote earlier:

final hashMap = HashMap.of(scores);
print(hashMap);
// {Andrew: 0, Eric: 9, Wayne: 1, Mark: 12}

Now the order has changed since HashMap makes no guarantees about order.

It’s possible to traverse through the key-value pairs of a map multiple times. This order, even when undefined as it is with HashMap, will be the same every time it’s traversed until the collection is mutated.

Note: The dart:collection library contains many additional data structures beyond the basic ones found in dart:core. By the time you’re finished with this book, you’ll understand how many of them work and what their performance characteristics and advantages are.

The lack of explicit ordering comes with some redeeming traits, though. Unlike lists, maps don’t need to worry about elements shifting around. Inserting into a map always takes a constant amount of time.

Lookup operations are also constant-time. This is significantly faster than searching for a particular element in a list, which requires a walk from the beginning of the list to the insertion point.

Set

A set is a container that holds unique values. Imagine it being a bag that allows you to add items to it but rejects items that have already been added:

var bag = {'Candy', 'Juice', 'Gummy'};
bag.add('Candy');
print(bag); // {Candy, Juice, Gummy}

Since sets enforce uniqueness, they lend themselves to a variety of interesting applications, such as finding duplicate elements in a collection of values:

final myList = [1, 2, 2, 3, 4];
final mySet = <int>{};
for (final item in myList) {
  if (mySet.contains(item)) {
    // mySet already has it, so it's a duplicate
  }
  mySet.add(item);
}

Similar to maps, order is generally not an important aspect of sets. That said, Dart’s default implementation of Set uses LinkedHashSet, which, unlike HashSet, promises to maintain insertion order.

You won’t use sets nearly as often as lists and maps, but they’re still common enough to be an important data structure to keep in your tool belt.

That wraps up this summary of the basic data collection structures that Dart provides for you. In the following chapters, you’ll use lists, maps and sets to build your own data structures.

Key Points

• Every data structure has advantages and disadvantages. Knowing them is key to writing performant software.
• Functions such as List.insert have characteristics that can cripple performance when used haphazardly. If you find yourself needing to use insert frequently with indices near the beginning of the list, you may want to consider a different data structure, such as a linked list.
• Map sacrifices the ability to access elements by ordered index but has fast insertion and retrieval.
• Set guarantees uniqueness in a collection of values. It’s optimized for speed, and like Map, abandons the ability to access elements by ordered index.

Where to Go From Here?

Need a more detailed explanation of lists, maps and sets? Check out the “Collections” chapter in Dart Apprentice from raywenderlich.com.