5. Linked Lists

Written by Kelvin Lau & Jonathan Sande

A linked list is a collection of values arranged in a linear, unidirectional sequence. It has several theoretical advantages over contiguous storage options such as the Dart List:

• Constant time insertion and removal from the front of the list.
• Reliable performance characteristics.

A linked list is a chain of nodes:

Nodes have two responsibilities:

1. Hold a value.
2. Hold a reference to the next node. A null reference indicates the end of the list.

In this chapter, you’ll implement a linked list and learn about the common operations associated with it. You’ll also learn about the time complexity of each operation.

Open up the starter project for this chapter so you can dive into the code.

Node

Create a folder called lib in the root of your project. Then add a new file to this folder called linked_list.dart. At the top of that file add class called Node with the following code:

class Node<T> {
  Node({required this.value, this.next});
  T value;
  Node<T>? next;
}

Since Node only knows about a single value, T is the standard letter people use to mean that the node can hold any type. Later when you create a linked list of nodes, you’ll use E to refer to the type since they are elements of the list.

Making Nodes Printable…Recursively

Override toString so that you can print Node later. Add this inside your newly created class:

@override
String toString() {
  if (next == null) return '$value';
  return '$value -> ${next.toString()}';
}

This will recursively print all of the nodes after this one in the linked list.

Note: When a method calls itself, this is known as recursion. A recursive method must have a base case, which is its exit strategy so that the method doesn’t keep calling itself forever. In the example above, the base case is when the next node is null.

Recursion can have a tendency to make your brain dizzy, but it’s also very useful. You’ll see recursion a lot in this book and hopefully by the time you’re finished, you’ll feel more comfortable with it.

Creating a Linked List by Hand

Now it’s time to try out your shiny new Node! Open bin/starter.dart and add the file import:

import 'package:starter/linked_list.dart';

Change starter to whatever your project name is if you aren’t using the starter project.

Then add the following code to main :

final node1 = Node(value: 1);
final node2 = Node(value: 2);
final node3 = Node(value: 3);

node1.next = node2;
node2.next = node3;

print(node1);

You’ve just created three nodes and connected them:

Run the code and you’ll see the following output in the console:

1 -> 2 -> 3

The current method of building lists leaves a lot to be desired. You can easily see that building long lists this way is impractical. A common way to alleviate this problem is to build a LinkedList that manages the Node objects. You’ll do just that!

LinkedList

A linked list has the concept of a head and tail, which refers to the first and last nodes of the list respectively:

Implement these characteristics by adding the following class below Node in linked_list.dart:

class LinkedList<E> {
  Node<E>? head;
  Node<E>? tail;

  bool get isEmpty => head == null;

  @override
  String toString() {
    if (isEmpty) return 'Empty list';
    return head.toString();
  }
}

You know that the list is empty if the head is null. Also, since you already designed Node to recursively print any nodes that follow it, you can print the entire linked list just by calling head.toString.

Adding Values to a List

As mentioned before, you’re going to provide an interface to manage the Node objects. You’ll first take care of adding values. There are three ways to add values to a linked list, each having its own unique performance characteristics:

1. push: Adds a value at the front of the list.
2. append: Adds a value at the end of the list.
3. insertAfter: Adds a value after a particular node in the list.

You’ll implement each of these in the following sections and analyze their performance characteristics.

Pushing to the Front of a List

Adding a value at the front of the list is known as a push operation. This is also known as head-first insertion. The code for it is refreshingly simple.

Add the following method to LinkedList:

void push(E value) {
  head = Node(value: value, next: head);
  tail ??= head;
}

You create a new node and point to the node that used to be head. Then you set this new node as head. In the case in which you’re pushing into an empty list, the new node is both the head and tail of the list.

Go back to bin/starter.dart and replace the contents of main with the following code, and then run the program:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print(list);

Your console output should show this:

1 -> 2 -> 3

That was a lot easier than building the list by chaining nodes together by hand!

Appending to the End of a List

The next operation you’ll look at is append. This is meant to add a value at the end of the list, and it’s known as tail-end insertion.

In LinkedList, add the following code just below push:

void append(E value) {
  // 1
  if (isEmpty) {
    push(value);
    return;
  }

  // 2
  tail!.next = Node(value: value);

  // 3
  tail = tail!.next;
}

This code is relatively straightforward:

1. Like before, if the list is empty, you’ll need to update both head and tail to the new node. Since append on an empty list is functionally identical to push, you simply invoke push to do the work for you.
2. In all other cases, you create a new node after the tail node. tail is guaranteed to be non-null since you push in the isEmpty case.
3. Since this is tail-end insertion, your new node is also the new tail of the list.

Test it out by replacing the contents of main with the following:

final list = LinkedList<int>();
list.append(1);
list.append(2);
list.append(3);

print(list);

Run that and you should see the following output in the console:

1 -> 2 -> 3

Inserting in Middle of a List

The third and final operation for adding values is insertAfter. This operation inserts a value after a particular node in the list, and requires two steps:

1. Finding a particular node in the list.
2. Inserting the new node after it.

First, you’ll implement the code to find the node that you want to insert a value after.

In LinkedList, add the following code just below append:

Node<E>? nodeAt(int index) {
  // 1
  var currentNode = head;
  var currentIndex = 0;

  // 2
  while (currentNode != null && currentIndex < index) {
    currentNode = currentNode.next;
    currentIndex += 1;
  }
  return currentNode;
}

nodeAt will try to retrieve a node in the list based on the given index. Since you can only access the nodes of the list from the head node, you’ll have to make an iterative traversal. Here’s the play-by-play:

1. You create a new reference to head and set up a counter to keep track of where you are in the list.
2. Using a while loop, you move the reference down the list until you’ve reached the desired index. Empty lists or out-of-bounds indexes will result in a null return value.

Now you need to insert the new node.

Add the following method just below nodeAt:

Node<E> insertAfter(Node<E> node, E value) {
  // 1
  if (tail == node) {
    append(value);
    return tail!;
  }

  // 2
  node.next = Node(value: value, next: node.next);
  return node.next!;
}

Here’s what you’ve done:

1. In the case where this method is called with the tail node, you’ll call the functionally equivalent append method. This will take care of updating tail.
2. Otherwise, you simply link up the new node with the rest of the list and return the new node.

Test your insert method out by replacing the body of main with the following:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Before: $list');

var middleNode = list.nodeAt(1)!;
list.insertAfter(middleNode, 42);

print('After:  $list');

Run that and you should see the following output:

Before: 1 -> 2 -> 3
After:  1 -> 2 -> 42 -> 3

You successfully inserted a node with a value of 42 after the middle node.

You might think it’s a little strange to insert a value after the node at some index, since with normal lists you insert a value at some index. The reason it’s like this for the linked list data structure, though, is because as long as you have a reference to a node, it’s very fast, O(1) time complexity, to insert another node after the known one. However, there’s no way to insert before a given node (thus replacing its index position) without knowing the node before it. And this requires the much slower task of iterating through the list.

Performance

Whew! You’ve made good progress so far. To recap, you’ve implemented the three operations that add values to a linked list and a method to find a node at a particular index.

Next, you’ll focus on the opposite action: removal operations.

Removing Values From a List

There are three main operations for removing nodes:

1. pop: Removes the value at the front of the list.
2. removeLast: Removes the value at the end of the list.
3. removeAfter: Removes the value after a particular node in the list.

You’ll implement all three and analyze their performance characteristics.

Popping From the Front of a List

Removing a value at the front of a linked list is often referred to as pop. This operation is almost as simple as push, so dive right in.

Add the following method to LinkedList:

E? pop() {
  final value = head?.value;
  head = head?.next;
  if (isEmpty) {
    tail = null;
  }
  return value;
}

By moving the head down a node, you’ve effectively removed the first node of the list. In the event that the list becomes empty, you set tail to null. pop returns the value that was removed from the list. This value is nullable, since the list may be empty.

Test it out by replacing the contents of main with the following:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Before: $list');

final poppedValue = list.pop();

print('After:  $list');
print('Popped value: $poppedValue');

Run that and you’ll see the following result:

Before: 1 -> 2 -> 3
After:  2 -> 3
Popped value: 1

Removing From the End of a List

Removing the last node of the list is somewhat inconvenient. Although you have a reference to the tail node, you can’t chop it off without getting the reference to the node before it. Thus, you’ll have to do an arduous traversal.

Add the following code just below pop:

E? removeLast() {
  // 1
  if (head?.next == null) return pop();

  // 2
  var current = head;
  while (current!.next != tail) {
    current = current.next;
  }

  // 3
  final value = tail?.value;
  tail = current;
  tail?.next = null;
  return value;
}

Note the following points about the numbered sections above:

1. If the list only consists of one node, removeLast is functionally equivalent to pop. Since pop will handle updating the head and tail references, you’ll just delegate this work. pop will also handle the case of an empty list.
2. You start at the beginning and keep searching the nodes until current.next is tail. This signifies that current is the node right before tail.
3. You collect the return value from the tail and after that rewire the node before the tail to be the new tail.

Test out your new functionality in main:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Before: $list');

final removedValue = list.removeLast();

print('After:  $list');
print('Removed value: $removedValue');

Run that and you should see the following in the console:

Before: 1 -> 2 -> 3
After:  1 -> 2
Removed value: 3

removeLast requires you to traverse all the way down the list. This makes for an O(n) operation, which is relatively expensive.

Removing a Value From the Middle of a List

The final remove operation is removing a node at a particular point in the list. This is achieved much like insertAfter. You’ll first find the node immediately before the node you wish to remove and then unlink it.

Add the following to your LinkedList:

E? removeAfter(Node<E> node) {
  final value = node.next?.value;
  if (node.next == tail) {
    tail = node;
  }
  node.next = node.next?.next;
  return value;
}

You drop the next node from the list by resetting the link of the given node to the next-next node, in effect skipping the one that used to come after. Special care needs to be taken if the removed node is the tail node since the tail reference will need to be updated.

Head back to main to try it out. You know the drill:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Before: $list');

final firstNode = list.nodeAt(0);
final removedValue = list.removeAfter(firstNode!);

print('After:  $list');
print('Removed value: $removedValue');

You should see the following output in the console:

Before: 1 -> 2 -> 3
After:  1 -> 3
Removed value: 2

Try adding more elements and play around with the value of the node index. Similar to insertAfter, the time complexity of this operation is O(1), but it requires you to have a reference to a particular node beforehand.

Performance

You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:

At this point, you’ve defined an interface for a linked list that most programmers around the world can relate to. However, there’s work to be done to adhere to Dart semantics. In the next part of the chapter, you’ll focus on making the interface more Dart-like.

Making a List Iterable

With most Dart collections, you can iterate through them using a for loop. For example, here is a basic implementation of looping through a standard list:

final numbers = [1, 2, 3];
for (final number in numbers) {
  print(number);
}

However, if you were to try to do that with your LinkedList implementation, you’d get an error. You can try by running the following code in main:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

for (final element in list) {
  print(element);
}

The error reads:

The type 'LinkedList<int>' used in the 'for' loop must implement Iterable.

The reason that you can loop through various collections in Dart is because they implement the Iterable interface. You can do the same to make LinkedList iterable.

Add extends Iterable<E> to LinkedList so that the first line of the class looks as follows:

class LinkedList<E> extends Iterable<E> {

Iterable requires an iterator, so create the missing override:

@override
// TODO: implement iterator
Iterator<E> get iterator => throw UnimplementedError();

After you’ve finished making the iterator, you’ll come back and update this getter.

Since Iterable also includes isEmpty, add the @override annotation above your isEmpty getter. It should look like so now:

@override
bool get isEmpty => head == null;

Note: Rather than extending Iterable, you could have also implemented it. However, the abstract Iterable class contains a lot of default logic that you would have to rewrite yourself if you had used the implement keyword. By using extends, you only need to implement iterator.

What’s an Iterator?

An iterator tells an iterable class how to move through its elements. To make an iterator, you create a class that implements the Iterator interface. This abstract class has the following simple form:

abstract class Iterator<E> {
  E get current;
  bool moveNext();
}

You don’t need to write that yourself. It’s already included in Dart. Here’s what the parts mean:

• current refers to the current element in the collection as you are iterating through it. According to Iterator semantics, current is undefined until you’ve called moveNext at least once.
• moveNext updates the new value of current, so it’s your job here to point to whatever item is next in the list. Returning false from this method means that you’ve reached the end of the list. After that point, you should consider current undefined again.

Creating an Iterator

Now that you know what an iterator is, you can make one yourself. Create the following incomplete class below LinkedList:

class _LinkedListIterator<E> implements Iterator<E> {
  _LinkedListIterator(LinkedList<E> list) : _list = list;
  final LinkedList<E> _list;
}

You pass in a reference to the linked list so that the iterator has something to work with.

Since you implemented Iterator, you still need to add the required current getter and moveNext method.

Implementing current

First add the following code for current:

Node<E>? _currentNode;

@override
E get current => _currentNode!.value;

Someone looping through your LinkedList probably doesn’t care about the concept of nodes. They just want the values, so when you return current you extract the value from the current node, which you are storing as a separate private variable named _currentNode. Note that accessing current when _currentNode is null will cause a crash. As long as you implement moveNext correctly and people follow Iterator semantics, though, this will never happen.

Implementing moveNext

Add the missing moveNext method now:

bool _firstPass = true;

@override
bool moveNext() {
  // 1
  if (_list.isEmpty) return false;

  // 2
  if (_firstPass) {
    _currentNode = _list.head;
    _firstPass = false;
  } else {
    _currentNode = _currentNode?.next;
  }

  // 3
  return _currentNode != null;
}

Here’s what you did:

1. If the list is empty, then there’s no need to go any further. Let the iterable know that there are no more items in this collection by returning false.
2. Since _currentNode is null to start with, you need to set it to head on the first pass. After that just point it to the next node in the chain.
3. Returning true lets the iterable know that there are still more elements, but when the current node is null, you know that you’ve reached the end of the list.

Looping Through a List

Now that your iterator is finished, you can use it in your LinkedList. Replace the unimplemented iterator getter that you added earlier to LinkedList with the following:

@override
Iterator<E> get iterator => _LinkedListIterator(this);

Now you’re ready to see if it works. Rerun the same code that you unsuccessfully tried earlier:

final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

for (final element in list) {
  print(element);
}

This time it works! It prints out the following values as expected:

1
2
3

The Iterable interface only allows iterating through the elements in one direction. Dart also has a BidirectionalIterator interface for two-way movement. That’s not possible with LinkedList, though, because this data structure also only allows movement in one direction.

Looping through a collection is not the only benefit of implementing Iterable. You now have access to all sorts of methods like where, map, contains, and elementAt. Just keep in mind that these are O(n) operations, though. Even the innocuous-looking length requires iterating through the whole list to calculate.

Note: The dart:collection library also contains a class named LinkedList. It only accepts elements of type LinkedListEntry, though, so it isn’t as flexible as yours was for making a list of arbitrary values. Additionally, the Dart version is a doubly linked list (linking to previous as well as next elements), whereas yours was a singly linked list. If you want to use a standard Dart collection that allows adding and removing at the ends in constant or amortized constant time, check out the Queue class.

Challenges

These challenges will serve to solidify your knowledge of data structures. You can find the answers at the end of the book and in the supplemental materials.

Challenge 1: Print in Reverse

Create a function that prints the nodes of a linked list in reverse order. For example:

1 -> 2 -> 3 -> null

// should print out the following:
3
2
1

Challenge 2: Find the Middle Node

Create a function that finds the middle node of a linked list. For example:

1 -> 2 -> 3 -> 4 -> null
// middle is 3

1 -> 2 -> 3 -> null
// middle is 2

Challenge 3: Reverse a Linked List

Create a function that reverses a linked list. You do this by manipulating the nodes so that they’re linked in the other direction. For example:

// before
1 -> 2 -> 3 -> null

// after
3 -> 2 -> 1 -> null

Challenge 4: Remove All Occurrences

Create a function that removes all occurrences of a specific element from a linked list. The implementation is similar to the removeAfter method that you implemented earlier. For example:

// original list
1 -> 3 -> 3 -> 3 -> 4

// list after removing all occurrences of 3
1 -> 4

Key Points

• Linked lists are linear and unidirectional. As soon as you move a reference from one node to another, you can’t go back.
• Linked lists have O(1) time complexity for head first insertions, whereas standard lists have O(n) time complexity for head-first insertions.
• Implementing the Dart Iterable interface allows you to loop through the elements of a collection as well as offering a host of other helpful methods.