Doubly Linked List Implementation in Scala

1. Introduction

A Doubly Linked List is a type of linked list in which each node contains a data part and two pointers. The two pointers are:

1. A pointer to the next node in the sequence (next).

2. A pointer to the preceding node in the sequence (prev).

It allows for bidirectional traversal, meaning one can navigate both forward and backward.

2. Implementation Steps

1. Define the Node class which will represent each element of the list, containing the data and pointers to the previous and next nodes.

2. Implement the DoublyLinkedList class with methods to:

- Add elements to the end (append).

- Remove elements (remove).

- Display the list (display).

3. Write the client code to test the Doubly Linked List implementation.

3. Implementation in Scala

// Definition for a Doubly-Linked List Node
class Node[A](var data: A, var prev: Node[A] = null, var next: Node[A] = null)
class DoublyLinkedList[A] {
  private var head: Node[A] = null
  // Append an element to the end of the list
  def append(data: A): Unit = {
    val newNode = new Node(data)
    if(head == null) {
      head = newNode
    } else {
      var current = head
      while(current.next != null) {
        current = current.next
      }
      current.next = newNode
      newNode.prev = current
    }
  }
  // Remove a node from the list
  def remove(data: A): Boolean = {
    var current = head
    while(current != null) {
      if(current.data == data) {
        if(current.prev != null) current.prev.next = current.next
        if(current.next != null) current.next.prev = current.prev
        if(current == head) head = current.next
        return true
      }
      current = current.next
    }
    false
  }
  // Display the list
  def display(): Unit = {
    var current = head
    while(current != null) {
      print(current.data + " <-> ")
      current = current.next
    }
    println("null")
  }
}

Client Code:

val dll = new DoublyLinkedList[Int]
dll.append(10)
dll.append(20)
dll.append(30)
dll.display()          // Expected: 10 <-> 20 <-> 30 <-> null
dll.remove(20)
dll.display()          // Expected: 10 <-> 30 <-> null

Output:

10 <-> 20 <-> 30 <-> null
10 <-> 30 <-> null

Explanation:

1. class Node[A](var data: A, var prev: Node[A] = null, var next: Node[A] = null): This defines our generic Node with data and two pointers for the previous and next nodes.

2. class DoublyLinkedList[A]: This initializes our DoublyLinkedList class.

3. append(data: A): This method appends a new node to the end of the list.

4. remove(data: A): This method searches for a node with the specified data and removes it from the list, adjusting the previous and next pointers as necessary.

5. display(): This method traverses and prints the entire list.

The implemented DoublyLinkedList offers basic functionality to demonstrate the bidirectional structure and operations on it.