5.
Linked Lists
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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:
- Hold a value.
- Hold a reference to the next node. A
nullreference 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 a 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
Override toString so that you can print Node later. Add this inside your newly created class:
@override
String toString() {
StringBuffer buffer = StringBuffer();
Node<T>? currentNode = this;
while (true) {
buffer.write(currentNode?.value);
currentNode = currentNode?.next;
if (currentNode == null) break;
buffer.write(' -> ');
}
return buffer.toString();
}
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';
final node1 = Node(value: 1);
final node2 = Node(value: 2);
final node3 = Node(value: 3);
node1.next = node2;
node2.next = node3;
print(node1);
1 -> 2 -> 3
LinkedList
A linked list has the concept of a head and tail, which refer to the first and last nodes of the list respectively:
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();
}
}
Adding Values to a List
Since you’re building a manager for Node objects, you must provide a way to add values. There are three ways to add values to a linked list, each having its own unique 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.
void push(E value) {
head = Node(value: value, next: head);
tail ??= head;
}
final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
print(list);
1 -> 2 -> 3
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.
void append(E value) {
// 1
if (isEmpty) {
push(value);
return;
}
// 2
tail!.next = Node(value: value);
// 3
tail = tail!.next;
}
final list = LinkedList<int>();
list.append(1);
list.append(2);
list.append(3);
print(list);
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:
Node<E>? nodeAt(int index) {
// 1
var currentNode = head;
var currentIndex = 0;
// 2
while (currentNode != null && currentIndex < index) {
currentNode = currentNode.next;
currentIndex++;
}
return currentNode;
}
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!;
}
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');
Before: 1 -> 2 -> 3
After: 1 -> 2 -> 42 -> 3
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.
Removing Values From a List
There are three main operations for removing nodes:
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.
E? pop() {
final value = head?.value;
head = head?.next;
if (isEmpty) {
tail = null;
}
return value;
}
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');
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.
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;
}
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');
Before: 1 -> 2 -> 3
After: 1 -> 2
Removed value: 3
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.
E? removeAfter(Node<E> node) {
final value = node.next?.value;
if (node.next == tail) {
tail = node;
}
node.next = node.next?.next;
return value;
}
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');
Before: 1 -> 2 -> 3
After: 1 -> 3
Removed value: 2
Performance
You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:
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);
}
final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
for (final element in list) {
print(element);
}
The type 'LinkedList<int>' used in the 'for' loop must implement Iterable.
class LinkedList<E> extends Iterable<E> {
@override
// TODO: implement iterator
Iterator<E> get iterator => throw UnimplementedError();
@override
bool get isEmpty => head == null;
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 interface class Iterator<E> {
E get current;
bool moveNext();
}
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;
}
Implementing current
First add the following code for current:
Node<E>? _currentNode;
@override
E get current => _currentNode!.value;
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;
}
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);
final list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
for (final element in list) {
print(element);
}
1
2
3
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: 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 2: 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 3: 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
Iterableinterface allows you to loop through the elements of a collection as well as offering a host of other helpful methods.
Where to Go From Here?
The nodes in this chapter only pointed to the next node in the list. This type of linked list is called a singly linked list. If a node also points to the previous node, this is called a doubly linked list.