# 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]

private var head: Node[A] = EmptyNode()

def insert(data: A): Unit = {
}

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
}
}
}

def display(): Unit = {
def recursiveDisplay(node: Node[A]): Unit = {
node match {
case DataNode(data, next) =>
print(data + " -> ")
recursiveDisplay(next)
case EmptyNode() => println("End")
}
}
}
}
``````

### 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.