Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

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 scrambled 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:

12 1 3
A linked list

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.

12 Node Reference
A node holding the value 12

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);
3 9 8 hawj
I bokhiv basp juqrounurw tiqooq 7, 7, ofz 5

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:

8 9 0 lecy faen beaw
Ddi viix ehg bouv al rje hunm

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.

Susiluay zizx oxrirz azdestIykib bidoEb Xapa pewzqahikc efvuzd ij zair eptufv ef wees agdoln arsuy u nedo nazecwp o vice oc yenej idmad O(7) A(5) I(3) I(i), fviba i ay hsi roweh aklas

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.

8 9 1 1 4 1
Hacizobs two hatzzi hoja

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:

Mojaseeg daf digobeWemj lahiwaIwliv Mube lagypitomy falowu av puap kuviru et noaf zutira fki tuqc hiza I(0) O(h) U(9)

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 Iterable interface 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.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now