Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

5. Chapter 5 Solutions
Written by Kelvin Lau & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

Solution to Challenge 1

A straightforward way to solve this problem is to use recursion. Since recursion allows you to build a call stack, you just need to call the print statements as the call stack unwinds.

Add the following helper function to your project:

void printNodesRecursively<T>(Node<T>? node) {
  // 1
  if (node == null) return;

  // 2
  printNodesRecursively(node.next);

  // 3
  print(node.value);
}
  1. You start off with the base case: the condition for terminating the recursion. If node is null, then it means you’ve reached the end of the list.

  2. This is your recursive call, calling the same function with the next node.

  3. Where you add the print statement will determine whether you print the list in reverse order or not. Any code that comes after the recursive call is called only after the base case triggers, that is, after the recursive function hits the end of the list. As the recursive statements unravel, the node data gets printed out.

Finally, you need to call the helper method from a printInReverse function:

void printListInReverse<E>(LinkedList<E> list) {
  printNodesRecursively(list.head);
}

To test it out, write the following in your main function:

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

print('Original list: $list');
print("Printing in reverse:");
printListInReverse(list);

You should see the following output:

Original list: 1 -> 2 -> 3
Printing in reverse:
3
2
1

The time complexity of this algorithm is O(n) since you have to traverse each node of the list. The space complexity is likewise O(n) since you implicitly use the function call stack to process each element.

Solution to Challenge 2

One solution is to have two references traverse down the nodes of the list, 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;
}
var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
print(list);

final middleNode = getMiddle(list);
print('Middle: ${middleNode?.value}');
1 -> 2 -> 3
Middle: 2

Solution to Challenge 3

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);
    }
    head = tempList.head;
  }
}

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() {
  tail = head;
  var previous = head;
  var current = head?.next;
  previous?.next = null;

  // more to come...
}
xzon givriry qyuh tofjejt gne pavn ul cfo joyn

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 4

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:

cieg 7 8 9

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

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

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
}
fleg pmus dipqakx rarhehm

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:

var 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 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