Matt Angelosanto for LogRocket

Posted on Dec 6, 2021 • Originally published at blog.logrocket.com

Dart and Flutter data structures: A comprehensive guide

#dart #flutter #webdev #computerscience

This is probably not the first time you’ve heard of data structures. As an experienced developer, you may have used them severally with other programming languages or even in the Dart programming language itself.

Data structures are at the core of software development and computer science by extension. They are one of the significant bases on which systems with varying degrees of complexity are built.

With Dart growing at a tremendous rate, mainly due to the popular Flutter framework, it is quickly becoming essential to have a clear understanding of the data structures available in this language and how you can carry out operations using them.

Let's proceed to explore and perform some CRUD operations on the various data structures you'll encounter when building a Dart or Flutter application.

Prerequisites

Fundamental knowledge of Dart
Dart SDK installed on your machine
Any text editor or IDE of your choice!

List

A list is an ordered collection of data that is stored and referenced as a single entity. Each element in the list is accessed by its index, which refers to its location. The index begins at 0 and continues to n - 1, with n being the length of the list.

Some real-life use cases of a list are:

Storing your browsing history
Storing songs in a music player or videos in a video player
Navigating webpages on a browser

List is best suited when the data grows dynamically. The arrangement of the items in the list is determined by the order in which they were added. This implies that the first added element has an index of 0, the second added element has an index of 1, etc.

In Dart, a list can either be growable or have a fixed length. You can specify this when you create the list by setting the growable property of the list to either true or false.

When a list is set to growable, the size of the list is flexible. In such a case, you can add items to the list, increasing its capacity to accommodate the items.

On the other hand, a fixed-length list retains the exact length that you specify at the point of its creation. An attempt to change its size either directly or through a list operation such as add or remove will result in an error.

Creating an empty, growable list

// Creating an empty list in a non-null-safe program.
var list = List();
 print(list); // []
 list.add(1);
 print(list); // [1]
 list.add(2);
 print(list); // [1, 2]

// Creating an empty list in a null-safe program.
 var nullSafeList = List.empty(growable: true);
  print(nullSafeList); // []
  nullSafeList.add(1);
  print(nullSafeList); // [1]
  nullSafeList.add(2);
  print(nullSafeList); // [1, 2]

In the code block above, we demonstrated two techniques of creating an empty, growable list. The Dart team deprecated the List() method of creating an empty list, which you cannot apply in a null-safe program. They replaced this technique with the blank square bracket, [].

Hence, if you want to create an empty growable list, it is recommended that you use the blank square brackets style shown in the above example.

Creating a list with fixed length

Sometimes, you want to ensure that the length of your list does not change throughout its lifecycle in your program. The example below shows how you can achieve this by creating a list with a fixed-length:

// Creating a list with a fixed length.
var list = List.filled(3, 0);
print(list); // [0, 0, 0]
list[1] = 3;
print(list); // [0, 3, 0]
list.add(1); // error

In the above example, we initialized the variable list with its filled constructor that fills the list with the same value. The first argument in the constructor is the length of the list and the second argument represents the initial value of the elements in the list.

This constructor also accepts an optional third argument of data type bool that you can use to set the growable property of the list. By default, this property is false, implying that the length is fixed. Passing true will make the size of the list flexible, and you can invoke operations that mutate the length of the list.

Otherwise, that is, if growable is left on its default (which is false), the length cannot be mutated. This means I can't add a new element or remove an element from the list as this will change the size or length of the list. I can only modify the values of the existing elements in the list or perform any other operations that do not change the size.

Invoking any operation that mutates the length of this list above will throw an error.

Creating a list with initialized values

You can also create a list and assign values to it at the same time.

var list = [1,2,3,4,5,6];
print(list); // [1,2,3,4,5,6]

Creating a list for items of the same datatype

The examples we illustrated above are lists that can contain data of varying types. This implies that you can have data of types int, String, bool, etc., in the same list.

List is a generic datatype and can contain elements that are strictly the same datatype.

// creating a list of Strings with a fixed length of 5 and all // elements have initial values - "foo";
  var stringList = List<String>.filled(5, "foo");
  print(stringList); // [foo, foo, foo, foo, foo]
  stringList[4] = "bar";
  print(stringList); // [foo, foo, foo, foo, bar]
//   stringList[2] = 3; // error

 // creating a growable list of integers.
var intList = List<int>.empty(growable: true);
  print(intList); // []
  intList.add(3);
  print(intList); // [3]
//   intList.add("doe"); // error

Retrieving items from a list

Remember that the items in a list are identified using their indices. To fetch an item from a list, you locate this item using its index.

var values = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

// using the index to retrieve its respective element.
print(values[3]); // 40
print(values[7]); // 80
print(values[0]); // 10

// using a for loop to access an array
for(int i = 0; i < values.length; i++ ){
  print("The element in index $i is ${values[i]}");
}
Output
/**  
The element in index 0 is 10
The element in index 1 is 20
The element in index 2 is 30
The element in index 3 is 40
The element in index 4 is 50
The element in index 5 is 60
The element in index 6 is 70
The element in index 7 is 80
The element in index 8 is 90
The element in index 9 is 100  
**/

Modifying an item in a list

You can also change the values in a list by reassigning a new value to the desired item through its index.

var values = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

// using the index to retrieve its respective element.
print(values[3]); // 40
print(values[7]); // 80
print(values[0]); // 10

// modifying an item in the list by reassigning a new value to each //index 
values[3] = 12; 
values[7] = 19;
values[0] = 38;

print(values[3]); // 12
print(values[7]); // 19
print(values[0]); // 38

Modifying a range of items in a list

You can also modify a sequence of items in a list using the setAll() method. This method takes two arguments: the first is the starting index of things you want to modify, and the second is the list containing the new values.

Note that the length of the new list must not be greater than what is obtainable from the starting index. Otherwise, the application will throw an error.

var values = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
print(values); // [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

// modifying the items in the list by reassigning a new values 
  values.setAll(4, [1,3,4,5,6]);
  print(values); // [10, 20, 30, 40, 1, 3, 4, 5, 6, 100]

Removing an item from a list

You can delete an element from a list by using the remove() method. This method deletes the first instance of the item in the list.

var values = [15, 16, 17, 18, 19, 20, 21, 22, 23, 24];
print(values); // [15, 16, 17, 18, 19, 20, 21, 22, 23, 24]

// remove an instance of 18\. This removes the first occurence of the instance in the list.  
values.remove(18);
print(values); // [15, 16, 17, 19, 20, 21, 22, 23, 24]

// remove the value at index 8  
values.removeAt(8);
print(values); // [15, 16, 17, 19, 20, 21, 22, 23]

// remove items that meet a condition, in this case even numbers.  
values.removeWhere((int num) => num % 2 == 0);   
 print(values); [15, 17, 19, 21, 23]

  // remove items between index 1 and 3
  values.removeRange(1,4);
  print(values); // [15, 23]

  // remove the last item in the list.
  values.removeLast();
  print(values); // [15]

Iterating a list

You can iterate through the items in a list by using either a for loop or the forEach() method of the list.

var values = [15, 16, 17, 18, 19, 20, 21, 22, 23, 24];

  // iterating with for loop
 for(int i = 0; i < values.length; i++){
   print(values[i]);
 }

  // Iterating with for each method
  values.forEach((int num) => print(num));

You can also iterate through a list using the Iterator instance, which allows you to perform an operation on each of the items in the list.

 var iterator = values.iterator;
 while(iterator.moveNext()){
  print(iterator.current);
 }

Shuffling a list

A list in Dart has an implicit shuffle method which you can invoke to shuffle the items in your list.

var values = [15, 16, 17, 18, 19, 20, 21, 22, 23, 24];
print(values);

values.shuffle();
 print(values);

Flutter data structures: Map

A map is a dynamic, generic collection of items stored as a key-value pair. The keys are unique entities that serve to reference and retrieve their respective values.

These keys and values are also referred to as entries and can be of any data type you may choose to declare when creating the map or making it dynamic. Any interaction you’ll need to do on the values requires passing through their respective keys to access them.

Some real-life use cases for the Map data structure are:

A dictionary — the word is the key and the meaning is the value
Your contact list — the name of the contact can be regarded as the key and the full contact information, the value
You can also use it when creating a banking system, whereby the account number is the key and the account entity or details is the value

Creating an empty map

You can create an empty map in either of two ways:

Via constructor:
```
var map = Map();
print(map); // {}
```
Via its literals:
```
var map = {};
print(map); // {}
```

Initializing the values in a map

You can also initialize the values of a map when using the literals technique of creation.

var map = {"name": "dami", "age": "10"};
print(map);

Adding an entry to a map

Remember that each entry comprises a key and its respective value. When adding an entry to a map, you specify the key in square brackets and assign the value to it. You can also add a collection of entries from a different map object into your desired map using the addAll() method.

Likewise, you can use the putIfAbsent() method to add an entry if the provided key does not already exist in the map.

var map = {};
print(map);

// adding an entry whose key is "name" and value is "dami"
map["name"] = "dami";
print(map);
// adding an entry whose key is "age" and value is 10
map['age'] = 10;
print(map);

//adding a collection of entries  
map.addAll({"school": "semicolon", "degree": "Bsc"});
print(map);

//adding an entry if the key does not already exist
map.putIfAbsent("school", () => "semicolon");
print(map);

Retrieving the value of an entry

The value of an entry is retrieved using its key as a reference to it.

var map = {'name': 'dami', 'age': 10};
print(map['name']);

var nameValue = map['name'];
print(nameValue);

Updating an entry in a map

You can update the value of an entry by simply reassigning a new value to it via its key.

 var map = {'name': 'dami', 'age': 10};
  print(map['name']);

// assigning a new value to the key
  map['name'] = 'john';
  print(map['name']);

Deleting an entry from a map

You can remove keys from a map object by invoking the remove() method. This method takes the key as an argument and deletes the entry with the matching key and its corresponding value.

 var map = {
    'ten': 10,
    'eleven': 11,
    'twelve': 12,
    'thirteen': 13,
    'fourteen': 14,
    'fifteen': 15,
    'sixteen': 16
    };

  map.remove('twelve');
  print(map);

You can also remove entries that meet a certain condition using the removeWhere(). This method takes a two-argument function to perform its task. The first argument in the function represents the key, and the second argument, the value.

Below is an example where we remove all even-number values and keys starting with character t.

 // remove all entries with even number values
  map.removeWhere((key, value) => value % 2 == 0);
  print(map);

  //remove all entries with key starting with 't'
  map.removeWhere((key, value) => key.startsWith('t'));
  print(map);

Creating a map to contain specific data types

You can create a map that contains the keys and values of defined datatypes. For instance, you may want your map to contain keys of the String datatype and int values. Below is an example of how you can go about this:

Map<String, int> map = {'first': 10, 'second': 20, 'third': 30, 'fourth': 40};

map['fifth'] = 50;

print(map);  

map['sixth'] = "value" // error  

// defining the data types via the constructor
var secondMap =  Map<String, int>();
secondMap['name'] = 5;
print(secondMap); // {name: 5}

secondMap['age'] = 'six'; //error

In the example above, adding a value of data type String will throw an error because we have specified that only int values are accepted in the map.

Iterating through a map

You can iterate through a map using the forEach() or for...in techniques.

// iterating through the keys of the map using the for...in loop to print all the values  
for(String k in map.keys){
  print(map[k]);
}

In the for...in loop example above, we iterated through the keys in the map. For each iteration, we fetched each key, stored it in the variable k, and used it to print the values in the map.

The forEach() method takes a two-argument function, just as we described with the removeWhere() method. Using the forEach() method allows you to perform operations on both the keys and the values simultaneously.

map.forEach((key, value) {print("key = $key, value = $value");});

// key = ten, value = 10
// key = eleven, value = 11
// key = twelve, value = 12
// key = thirteen, value = 13
// key = fourteen, value = 14
// key = fifteen, value = 15
// key = sixteen, value = 16

Flutter data structures: Set

A set is a collection of unique items. Unlike lists, sets are particularly unique data structures that ensure duplicate values do not exist in the collection.

A very common real-life use case for a set is checking the intersection of two collections. That is, you can efficiently obtain the elements that are common to two sets. Here is a snippet that illustrates this:

 Set set = {1,2,3,4,5, 6};
  Set other = {5,6,7,8};
  print(set.intersection(other)); // {5,6}

Sets are best suited for storing unique values whose order is not essential as a variable. Below are three types of sets we’ll look at in detail:

HashSet

This type of set does not have a specified order of iteration. The hashcode and equalTo() method determines the order of the items in the set. HashSet is best suited when the insertion order is unimportant, and you want to store unique values.

LinkedHashSet

This set stores the data based on the order in which the items are inserted — so, if you insert item A first, then item B, you are sure to get A before B when iterating the set. It is the default implementation applied when an instance of a set is created using its literals. It also accepts null values.

SplayTreeSet

The default operation of the SplayTreeSet is to store data that is comparable. For instance, if you insert numeric values, the SplayTreeSet orders them by default; inserting a string and a numeric value will throw an error because it cannot compare them to each other.

Likewise, inserting a null value will throw an error. You can also use SplayTreeSet when you want to store data in a form you determine. You can also specify how the items should compare by passing a compare function in the constructor.

Let’s compare all three set types:

HashSet	LinkedHashSet	SplayTreeSet
It has a complexity of O(1) when inserting, retrieving and removing data.	It has a complexity of O(1) when inserting, retrieving and removing data.	It has a complexity of O(log(n)) when inserting, retrieving and removing data.
Permits null value.	Permits null value.	Does not permit `null` value.
It uses the hashcode and `equalTo()` methods to compare items.	It uses the hashcode and `equalTo()` methods to compare items.	It uses the `Comparable.compareTo()` method to compare items.

Now, let’s take a look at performing CRUD operations with sets.

Creating a set

You can create a set through any of the constructors of its implementers or a literal.

 // Creating an empty hashSet.
 Set hashSet = HashSet();

 // creating an empty splayTreeSet
 var splayTreeSet = SplayTreeSet();

 // creating an empty linked hash set
 Set linkedHashSet = LinkedHashSet();

 // creating an empty linked hash set by literal.
 Set literalSet = {};

 // creating a linked hash set of integer values.
 var intSet = <int> {2,3,4,5};

Adding an element to a set

Set has an add() method that you can use to insert data. When you attempt to add a value that already exists in the set, this new value is ignored. The set compares this new value with what already exists in it and checks that none of its data is equal to this new value before adding it.

This method returns a bool value — true if the data was added and false if the new data is a duplicate.

var set = <int> {2,3,4,5};
 print(set); // {2, 3, 4, 5}

 // adding a unique item
 print(set.add(1)); // true
 print(set); // {2, 3, 4, 5, 1}

// adding a duplicate item
 print(set.add(2)); // false
 print(set); // {2, 3, 4, 5, 1}

Updating an element in a set

The set data structure does not have a default approach for updating its data. This is because modifying a value in the set could alter the iteration order of the collection. For instance, if you are using a LinkedHashSet, the new value could be added at the end of the set. This alters the already defined order of the data based on how you inserted them.

However, you can update the value in a set by using its map method. This update creates a new Set instance that you have to store in a variable for further reference.

 var set = <int> {1,2,3,4,5,6,7,8,9};
 print(set); // {1, 2, 3, 4, 5, 6, 7, 8, 9}

 // updating the value 4 to 11
 var newSet = set.map((e) => e == 4 ? 11 : e).toSet();
 print(newSet); // {1, 2, 3, 11, 5, 6, 7, 8, 9}

Note that you would not have to apply this peculiar sorting functionality to the SplayTreeSet if you replace a lower value with a value that is higher than the rest of the data in the collection using the above technique.

Removing an element from a set

You can remove an item from a set by using the remove() method. To remove an item from a set, pass a value equal to the data you want to remove from the set. This method also returns a bool datatype — once more, it returns true if the value you want to remove is present in the set, and otherwise returns false.

var set = <int> {1, 2, 3, 4, 5};
 print(set); // {1, 2, 3, 4, 5}

// removing an item that exists in the set
 var isRemoved =  set.remove(4);
 print(isRemoved); // true
 print(set); // {1, 2, 3, 5}

 // removing an item that does not exist in the set
 isRemoved = set.remove(20);
 print(isRemoved); // false
 print(set); // {1, 2, 3, 5}

Just as we did with map and list, you can also remove the item or items that meet a specified condition from a set. This can be done using the removeWhere() method, and the operation is similar to how I described it in the list and map sections illustrated above.

Iterating on a set

You can iterate on a set using either the for...in loop or the forEach() method.

var set = <int> {1,2,3,4,5};

 // iterating a set using the for...in loop
 for(int value in set){
  print(value);
 }

 //iterating a set using the forEach
 set.forEach((element) {print(element);});

 // Using the iterator object
 var iterator = set.iterator;
 while(iterator.moveNext()){
  print(iterator.current);
 }

Dart data structures: Stack

A stack is an abstract collection that stores data in an ordered sequence. There is only one point of entry and exit in a stack. A stack uses the model of last in, first out (LIFO) — the last item that goes into the stack is also the first item that goes out of the stack.

It might be helpful to think of Dart stacks like a stack of books. You can only pick a book from the top of the stack and add a book to the top of the stack. Picking a book at the bottom of the stack or in-between books would require you to first take out the books on top before you reach the desired book.

It is important to note that the stack data structure discussed here is different from the Flutter Stack widget. Although they have the same underlying structure, they differ in terms of applications and operations.

The Flutter Stack widget gives you the ability to place widgets right on top of each other. The composing widgets appear as layers such that the widget at the top of the stack is at the forefront of the screen. Then, the widgets beneath the topmost stack appear behind one another. You can read up on the Flutter Stack widget if you’d like more information.

Dart stack operations

Push: the process of adding an item to the stack
Pop: the process of removing an item from the stack
Top: the process of viewing the item at the top of the stack without removing it

You’d typically apply a stack when you want to:

Perform an operation that requires you to undo/redo a task or set of tasks like you would in a word processor.
Evaluate mathematical expressions when building a calculator.

Creating a Dart stack

Dart uses an external package to implement the stack data structure. Run the command below on your terminal to install the stack package:

dart pub add stack

  // create a dynamic stack to hold data of any type
Stack dynamicStack = Stack();

// create a stack of int to hold int values
  Stack<int> intStack = Stack();

Let’s explore how we can perform operations on stacks.

Pushing an item to a Dart stack

kStack<int> intStack = Stack();

// pushing items into the stack.
intStack.push(3);
intStack.push(4);
intStack.push(5);

// printing the values of the items in the stack
intStack.print();

  // 5
  // 4
  // 3

Popping an item from a Dart stack

Stack<int> intStack = Stack();

// pushing items into the stack.
intStack.push(3);
intStack.push(4);
intStack.push(5);

// printing the length of the stack
print(intStack.length); // 3

// popping the element at the top of the stack
print(intStack.pop()); // 5

print(intStack.length); // 2

Check that the stack contains a value

You can check that a value is present in a stack by using the contains() method. This method returns true if the value is present, and false otherwise.

Stack<int> intStack = Stack();

// pushing items into the stack.
intStack.push(3);
intStack.push(4);
intStack.push(5);

// checking that an existent value exists in the stack
print(intStack.contains(4)); // true

// checking that a non-existent value exists in the stack
print(intStack.contains(8)); // false

The contains() method is also present in the list and queue data structures. A queue is quite similar to a stack, except that it uses the first in, first out model (FIFO).

If you’ve ever used a queue, you’ll have noticed some of the operations we illustrated in the list and stack sections such as add(), remove(), removeWhere(), Iterator, forEach(), elementAt() work pretty much the same way.

Choosing the right data structure

When writing an algorithm to solve a complex task, one of the decisions you may struggle with is picking the right data structure to solve your problem. Sometimes there may be several data structures that can get the job done, yet you have to consider the complexity and computing power it will take each choice of data structure to solve the task.

One of the biggest factors to consider when picking a data structure involves the complexity of the algorithms used in your program. You should first determine the most-used operation in your algorithm: will you be doing a lot of insertions, removing, or retrieving? If you perform many insertions and retrieve data from the collection, you may want to consider a map or a set if you are particular about unique values.

Here is a summary of the complexities of the operations performed in the data structures to guide you when selecting for your next application:

Data Structure	Insertion	Removal	Contains
List	O(1)	O(n)	O(n)
LinkedHashSet	O(1)	O(1)	O(1)
SplayTreeSet	O(log n)	O(log n)	O(log n)
Map	O(1)	O(1)	O(1)

Conclusion

A solid understanding of data structures is a fundamental requisite of every software developer. In this article, we’ve explored the CRUD operations of some of the most commonly used data structures in Dart and Flutter, and what to consider when choosing the proper data structure for your algorithms. For more information, you can check out the official documentation.

LogRocket: Full visibility into your web apps

LogRocket is a frontend application monitoring solution that lets you replay problems as if they happened in your own browser. Instead of guessing why errors happen, or asking users for screenshots and log dumps, LogRocket lets you replay the session to quickly understand what went wrong. It works perfectly with any app, regardless of framework, and has plugins to log additional context from Redux, Vuex, and @ngrx/store.

In addition to logging Redux actions and state, LogRocket records console logs, JavaScript errors, stacktraces, network requests/responses with headers + bodies, browser metadata, and custom logs. It also instruments the DOM to record the HTML and CSS on the page, recreating pixel-perfect videos of even the most complex single-page apps.

Try it for free.