Linked List Challenge Solution 1

📚 Official Books Data Structures & Algorithms in Swift
1

The task is to:

Create a function that prints the nodes of a linked list in reverse order. For example:
1 -> 2 -> 3 -> nil

// should print out the following:
3
2
1

The solution in the book is the following:

private func printInReverse<T>(_ node: Node<T>?) {
  guard let node = node else { return }
  printInReverse(node.next)
  print(node.value)
}

func printInReverse<T>(_ list: LinkedList<T>) {
  printInReverse(list.head)
}

Evidently, the challenge is solved using “recursion” here. I had to lookup what recursion meant as it wasn’t even mentioned earlier in the book. I would expect a solution to use methods mentioned in the book at least. The explanation was also very vague for a solution that uses a method not discussed in the book. I strongly suggest a short section on recursion be added to the book.

Anyway, after several hours I just don’t understand how this solution works. I understand how to accomplish this iteratively, but recursion is not clicking for me. I understand a few points about the solution such as, we only move to the next node and print once we get to the end of the list but that’s it.

In other words, I understand how we print “3” (the first reversed node) but not the others. How are we able to go backwards (i.g. 2 → 1) if a linked list is unidirectional???

I also don’t understand the role of the below function:

func printInReverse<T>(_ list: LinkedList<T>) {
  printInReverse(list.head)
}

Can someone please explain how this works?

1 Like
2

@mjhios Recursion happens when a certain function calls itself. All recursive function calls are stored on the stack which works in LIFO mode. LIFO stands for last in first out and is a fancy way of saying that you can only add and remove items at the top of the stack. You can think of the stack as a pile of books or dishes. If you attempt to either add or remove anything in the middle or at the bottom of the stack everything else collapses. So it makes sense to only be able to work with the top item of the stack in this case no matter what.

printInReverse(_ list:) is a generic overload of printInReverse(_ node:). The list version of the function calls its overloaded node version using the head of the list as its argument. printInReverse(list.head) doesn’t print anything to the console if list.head is nil since it’s an empty list in this case and calls printInReverse(list.head.next) otherwise. Each printInReverse(_ node:) function call calls printInReverse(_ node:) for the next node in the list if the current node isn’t nil. The compiler pushes all recursive function calls to the stack in the order they happen using the LIFO rule. This is how the stack trace looks like for a list with three nodes:

printInReverse(list.head.next.next)
printInReverse(list.head.next)
printInReverse(list.head)

Once you reach the end of the list and the current node is nil, the compiler automatically unwinds the stack for you under the hood. Each recursive function call gets popped from the stack using the LIFO principle. The compiler first pops printInReverse(list.head.next.next) from the stack which prints list.head.next.next.value to the console which is 3 in this case. The compiler then pops printInReverse(list.head.next) from the stack which prints list.head.next.value to the console which is 2 in this case. The compiler finally pops printInReverse(list.head) from the stack which prints list.head.value to the console which is 1 in this case. The stack is empty so you are done.

It’s very important that the chain of recursive function calls stops at some point so the compiler can unwind the recursive stack safely. Otherwise you get a stack overflow error. You can think of this as an endless loop with no exit condition.

You can read even more about recursion vs iteration over here:

Please let me know if you have any more questions or other issues about the whole thing when you get a chance. Thank you!

1 Like
3

@shogunkaramazov Thanks for the reply! I didn’t know the compiler was using a Stack (LIFO) under the hood. Nice! Just a few points I still don’t understand.

You mentioned:

printInReverse(_ list:) is an overload of printInReverse(_ node:) . The list version of the function calls its overloaded node version using the head of the list as its argument. printInReverse(list.head) doesn’t print anything to the console if list.head is nil since it’s an empty list in this case and calls printInReverse(list.head.next) otherwise.

Above you mentioned that printInReverse(list.head) doesn’t print anything if list.head is nil (end of list). Instead it calls printInReverse(list.head.next) but I thought it would call printInReverse(list.head.next.next) which would be list.head.next.next.value or 3 in this case?

Also, I’m still not sure I understand the role of the below function:

 func printInReverse<T>(_ list: LinkedList<T>) {
  printInReverse(list.head)
}

If I understand correctly, all it does is get a linked list, call printInReverse<T>(_ node: Node<T>?), and push list.head (1, 2, 3) to the call stack. Once the list is nil printInReverse<T>(_ node: Node<T>?) pops (and prints) the node values 3, 2, 1 right? Or am I still not understanding how it interacts with the helper function?

Thanks, I really appreciate it!

4

@mjhios This is what happens step by step with a list that has three nodes:

  1. printInReverse(list) calls printInReverse(list.head).

  2. The stack pushes printInReverse(list.head) which checks that list.head isn’t nil and calls printInReverse(list.head.next).

  3. The stack pushes printInReverse(list.head.next) which checks that list.head.next isn’t nil and calls printInReverse(list.head.next.next).

  4. The stack pushes printInReverse(list.head.next.next) which checks that list.head.next.next isn’t nil and calls printInReverse(list.head.next.next.next).

  5. printInReverse(list.head.next.next.next) checks that list.head.next.next.next is nil and returns.

  6. The stack pops printInReverse(list.head.next.next) which prints list.head.next.next.value that is 3 in this case and returns.

  7. The stack pops printInReverse(list.head.next) which prints list.head.next.value that is 2 in this case and returns.

  8. The stack pops printInReverse(list.head) which prints list.head.value that is 1 in this case and returns.

  9. printInReverse(list) returns.

Please let me know if you have any more questions or other issues about the whole thing when you get a chance. Thank you!

1 Like