Linked List Implementation in Scala

1. Introduction

A Linked List is a linear data structure where each element is a separate object called a node. Each node comprises two items: the data and a reference to the next node. Linked Lists are dynamic data structures, and they can grow and be pruned, allocating and deallocating memory while the program is running.

2. Implementation Steps

1. Define a trait Node which will represent a node in the linked list.

2. Define two case classes: EmptyNode (represents the end of the list) and DataNode (represents a node with data and a link to the next node).

3. Define a class LinkedList which will encapsulate the linked list operations.

4. Implement methods such as insert, delete, display, etc.

5. Write the client code to test the Linked List implementation.

3. Implementation in Scala

sealed trait Node[A]
case class EmptyNode[A]() extends Node[A]

case class DataNode[A](data: A, next: Node[A]) extends Node[A]

class LinkedList[A] {

  private var head: Node[A] = EmptyNode()
  
  def insert(data: A): Unit = {
    val newNode = DataNode(data, head)
    head = newNode
  }
  
  def delete(data: A): Unit = {
    def recursiveDelete(previous: Node[A], current: Node[A]): Unit = {
      current match {
        case DataNode(d, next) if d == data => previous match {
          case pn: DataNode[A] => pn.next = next
          case _: EmptyNode[A] => head = next
        }
        case DataNode(_, next) => recursiveDelete(current, next)
        case _: EmptyNode[A] => // do nothing
      }
    }
    recursiveDelete(EmptyNode(), head)
  }
  
  def display(): Unit = {
    def recursiveDisplay(node: Node[A]): Unit = {
      node match {
        case DataNode(data, next) =>
          print(data + " -> ")
          recursiveDisplay(next)
        case EmptyNode() => println("End")
      }
    }
    recursiveDisplay(head)
  }
}

Client Code:

val ll = new LinkedList[Int]
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.display()
ll.delete(2)
ll.display()

Output:

3 -> 2 -> 1 -> End
3 -> 1 -> End

Explanation:

1. sealed trait Node[A]: A trait representing a generic node in the linked list.

2. EmptyNode and DataNode: Case classes representing the two possible node types. EmptyNode is the end of the list while DataNode has data and a reference to the next node.

3. class LinkedList[A]: The main class encapsulating linked list operations.

4. insert: Inserts a new node at the beginning of the list.

5. delete: Recursively searches for the first occurrence of the given data and deletes that node.

6. display: Recursively traverses the list and prints each node.

The LinkedList here is implemented as a singly linked list where each node has a reference only to the next node.