## Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

#### Section V: Graphs

Section 5: 5 chapters

# 5. Chapter 5 Solutions Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

## Solution to Challenge 1

One solution is to have two references traverse down the list nodes, where one is twice as fast as the other. Once the faster reference reaches the end, the slower reference will be in the middle. Update the function to the following:

``````Node<E>? getMiddle<E>(LinkedList<E> list) {
var slow = list.head;
var fast = list.head;

while (fast?.next != null) {
fast = fast?.next?.next;
slow = slow?.next;
}

return slow;
}
``````

In the `while` loop, `fast` checks the next two nodes, while `slow` only gets one. This is known as the runner’s technique.

Write the following in your `main` function:

``````var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
print(list);

final middleNode = getMiddle(list);
print('Middle: \${middleNode?.value}');
``````

You should see the following output:

``````1 -> 2 -> 3
Middle: 2
``````

The time complexity of this algorithm is O(n) since you traversed the list in a single pass. The runner’s technique helps solve a variety of problems associated with a linked list.

## Solution to Challenge 2

To reverse a linked list, you must visit each node and update the `next` reference to point in the other direction. This can be a tricky task since you’ll need to manage multiple references to multiple nodes.

### The Easy Way

You can trivially reverse a list by using the `push` method along with a new temporary list. Either add a `reverse` method to `LinkedList` or create an extension like so:

``````extension ReversibleLinkedList<E> on LinkedList<E> {
void reverse() {
final tempList = LinkedList<E>();
for (final value in this) {
tempList.push(value);
}
}
}
``````

### But Wait…

Although O(n) is the optimal time complexity for reversing a list, there’s a significant resource cost in the previous solution. As it is now, `reverse` will have to allocate new nodes for each `push` method on the temporary list. You can avoid using the temporary list entirely and reverse the list by manipulating the `next` pointers of each node. The code ends up being more complicated, but you reap considerable benefits in terms of performance.

``````void reverse() {
var previous = head;
var current = head?.next;
previous?.next = null;

// more to come...
}
``````

``````while (current != null) {
final next = current.next;
current.next = previous;
previous = current;
current = next;
}
``````
``````head = previous;
``````

### Try it Out!

Test the `reverse` method by writing the following in `main`:

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

print('Original list: \$list');
list.reverse();
print('Reversed list: \$list');
``````
``````Original list: 1 -> 2 -> 3
Reversed list: 3 -> 2 -> 1
``````

## Solution to Challenge 3

This solution traverses down the list, removing all nodes that match the element you want to remove. Each time you perform a removal, you need to reconnect the predecessor node with the successor node. While this can get complicated, it’s well worth it to practice this technique. Many data structures and algorithms will rely on clever uses of pointer arithmetic.

### Trimming the Head

Suppose you want to remove 1 from the following list:

``````extension RemovableLinkedList<E> on LinkedList<E> {
void removeAll(E value) {

}
}
``````
``````while (head != null && head!.value == value) {
}
``````

### Unlinking the Nodes

Like many of the algorithms associated with linked lists, you’ll leverage your pointer arithmetic skills to unlink the nodes. Write the following at the bottom of `removeAll`:

``````var previous = head;
var current = head?.next;
while (current != null) {
if (current.value == value) {
previous?.next = current.next;
current = previous?.next;
continue;
}
// more to come
}
``````

### Keep Traveling…

Can you tell what’s missing? As it is right now, the `while` loop may never terminate. You need to move the `previous` and `current` pointers along. Write the following at the bottom of the `while` loop, replacing the `// more to come` comment:

``````previous = current;
current = current.next;
``````
``````tail = previous;
``````

### Try it Out!

Write the following in `main`:

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

list.removeAll(3);
print(list);
``````
``````1 -> 1 -> 2 -> 2
``````
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now