Welcome! In this lesson, we'll expand on our linked list implementation using Scala. As you know by now, when creating your own linked lists, you need to manually create and manageme nodes and pointers. You'll learn how to build and improve on linked lists by defining your own classes and methods, providing an efficient way to perform data operations.

Linked lists are composed of nodes, where each node holds a value and a reference to the next node in the sequence. In Scala, we can manually implement linked lists using classes and case classes. We'll focus on singly linked lists, which have nodes linked in one direction, allowing for straightforward implementation and traversal. The implementation involves defining a Node and a LinkedList class or object to manage the nodes.

To create linked lists manually in Scala, we begin by defining a Node class to represent each element of the list, along with a LinkedList class to handle operations:

class Node[T](val value: T, var next: Option[Node[T]] = None)

class LinkedList[T] {
  var head: Option[Node[T]] = None
  
  def append(value: T): Unit = {
    head match {
      case None => head = Some(new Node(value))
      case Some(h) =>
        @annotation.tailrec
        def findLast(node: Node[T]): Node[T] =
          node.next match {
            case Some(nextNode) => findLast(nextNode)
            case None => node
          }
        val last = findLast(h)
        last.next = Some(new Node(value))
    }
  }
}

Here, we define a Node class with a generic type, T, and an Option type for next to represent the potential absence of nodes. The LinkedList class manages appending elements to the list.

When implementing linked list operations in Scala manually, we create methods for appending, prepending, removing the first node, and searching for values:

class LinkedList[T] {
  var head: Option[Node[T]] = None

  def append(value: T): Unit = { /* as before */ }
  
  def prepend(value: T): Unit = {
    val newHead = new Node(value, head)
    head = Some(newHead)
  }
  
  def removeFirst(): Unit = {
    head match {
      case Some(node) => head = node.next
      case None => println("List is empty.")
    }
  }
  
  def find(value: T): Option[Node[T]] = {
    var current = head
    while (current.exists(_.value != value)) {
      current = current.flatMap(_.next)
    }
    current
  }
}

In this example, you can see that the operations for adding, removing, and finding nodes are achieved through the linked list structure.

Traversal in Scala involves iterating over linked list nodes, often using recursive methods or while loops:

def traverse(): Unit = {
  def loop(node: Option[Node[T]]): Unit = {
    node match {
      case Some(n) =>
        println(n.value)
        loop(n.next)
      case None => // End of list
    }
  }
  
  loop(head)
}

This method allows us to print all values in the list using recursion, illustrating Scala's functional programming style.

Advanced operations can be manually implemented to provide more control over the linked list data structure:

def addAfter(target: T, value: T): Unit = {
  val newNode = new Node(value)
  find(target) match {
    case Some(node) =>
      val tmp = node.next
      node.next = Some(newNode)
      newNode.next = tmp
    case None => println("Target node not found.")
  }
}

def clear(): Unit = {
  head = None
}

def contains(value: T): Boolean = {
  find(value).isDefined
}

These operations offer refined control over node placement and list management.

Congratulations! You've learned the foundational techniques for creating, manipulating, and traversing linked lists in Scala. Remember to practice implementing your custom linked lists, experimenting with adding and removing elements, and effectively traversing the list. This exploration will deepen your understanding and prepare you for more advanced data structure implementations. Happy coding!