Introduction to Linked List Problems with Scala

Today's lesson will build upon our foundational understanding of linked lists by diving into practical implementation exercises using Scala. These problems will sharpen your coding skills and prepare you for scenarios you might encounter in technical interviews.

Picture a scenario in which you have a sequence of events stored in a linked list. Your task is to look back in time — essentially, to reverse the chronology of these events. In technical terms, this means traversing a singly linked list in reverse order while keeping its structure intact. This skill is critical, whether for reversing transaction logs or simply navigating through a playlist from end to start.

Consider a browser's back-button functionality, where the most recently visited pages must be revisited in reverse order. This operation mirrors our task of reverse traversal in a linked list, capturing the essence of a real-world application.

One may consider creating a new linked list while iterating over the original list, inserting each element at the head of the new list. Although this approach might work, it is an overcomplicated approach that results in extra processing and memory usage that we can avoid.

A more sophisticated solution would use a stack. With a stack, we ensure an orderly collection of the nodes' values as we navigate the list. Once the traversal is complete, we extract the values in reverse, thanks to the stack's Last-In-First-Out property.

Let's visualize it with a deck of cards: We pick each card from the top (the head of the linked list) and place it into a pile (the stack). When we finish, we pick up the cards from the pile now in reverse order.

Let's tackle it with Scala:

object LinkedListReversal {

  class ListNode(var value: Int, var next: Option[ListNode] = None)

  def reversePrintLinkedList(head: Option[ListNode]): Unit = {
    // Instantiate a stack to hold node values.
    val stack = scala.collection.mutable.Stack[Int]()

    // Traverse the linked list and push node values to the stack.
    def traverse(currentNode: Option[ListNode]): Unit = currentNode match {
      case Some(node) =>
        stack.push(node.value)
        traverse(node.next)
      case None => ()
    }

    traverse(head)

    // Pop from the stack to obtain elements in reversed order.
    while (stack.nonEmpty) {
      println(stack.pop())
    }
  }
}

In this code, we create a mutable.Stack[Int] to store integers. We then iterate through the linked list using a small recursive helper function. For each node visited, we push its value onto the stack. After traversing the entire list, we pop the values off the stack. This reversal is possible because stacks operate on a Last In, First Out (LIFO) principle, which means the last element added to the stack will be the first one removed, thus reversing the order of the elements.

Note on Stack Choice: While we're using scala.collection.mutable.Stack for demonstration purposes due to its explicit stack semantics, modern Scala idiomatically prefers immutable collections. For LIFO operations, consider using a List (where :: prepends and pattern matching extracts the head), or scala.collection.immutable.ArrayDeque for better performance with larger datasets. We use mutable.Stack here to clearly illustrate the stack-based approach for educational purposes.