Expanding On Custom Linked Lists in Scala

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.