3.
Core Data Structures in Dart
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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 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 commonly used 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 collection elements 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'.
people[0] // 'Pablo'
people[1] // 'Manda'
people[2] // 'Megan'
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]
people.insert(0, 'Ray');
// [Ray, Pablo, Manda, Megan, Edith]
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.
Map
A map is a 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};
scores['Andrew'] = 0;
print(scores);
// {Eric: 9, Mark: 12, Wayne: 1, Andrew: 0}
import 'dart:collection';
final hashMap = HashMap.of(scores);
print(hashMap);
// {Andrew: 0, Eric: 9, Wayne: 1, Mark: 12}
Set
A set is a container that holds unique values. Imagine it as 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}
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);
}
Key Points
- Every data structure has advantages and disadvantages. Knowing them is key to writing performant software.
- Functions such as
List.inserthave characteristics that can cripple performance when used haphazardly. If you need to useinsertfrequently with indices near the beginning of the list, you may want to consider a different data structure, such as a linked list. -
Mapsacrifices the ability to access elements by ordered index but has fast insertion and retrieval. -
Setguarantees uniqueness in a collection of values. It’s optimized for speed, and likeMap, 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 “Lists”, “Sets” and “Maps” chapters in Dart Apprentice: Fundamentals from Kodeco.