Circular Linked List Implementation in Scala

1. Introduction

A Circular Linked List is a variant of the standard linked list where the last node of the list points back to the first node instead of having a null reference. This cyclic nature can be useful in certain scenarios like representing a cycle in a graph or simulating a round-robin scheduling algorithm.

2. Implementation Steps

1. Define the Node class which will represent each element of the list, containing the data and a pointer to the next node.

2. Implement the CircularLinkedList class with methods to:

- Add elements to the list (add).

- Remove elements (remove).

- Display the list (display).

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

3. Implementation in Scala

// Definition for a Node in Circular Linked List
class Node[A](var data: A, var next: Node[A] = null)

class CircularLinkedList[A] {

  private var head: Node[A] = null
  private var tail: Node[A] = null
  
  // Add an element to the list
  def add(data: A): Unit = {
    val newNode = new Node(data)
    if (head == null) {
      head = newNode
      tail = newNode
      newNode.next = head
    } else {
      tail.next = newNode
      newNode.next = head
      tail = newNode
    }
  }
  
  // Remove an element from the list
  def remove(data: A): Boolean = {
    if (head == null) return false
    var current = head
    var prev: Node[A] = null
    do {
      if (current.data == data) {
        if (prev == null) {
          tail.next = current.next
          head = current.next
        } else {
          prev.next = current.next
          if (current == tail) tail = prev
        }
        return true
      }
      prev = current
      current = current.next
    } while (current != head)
    false
  }
  
  // Display the list
  def display(): Unit = {
    if (head == null) return
    var current = head
    do {
      print(current.data + " -> ")
      current = current.next
    } while (current != head)
    println("back to " + current.data)
  }
}

Client Code:

val cll = new CircularLinkedList[Int]
cll.add(10)
cll.add(20)
cll.add(30)
cll.display()          // Expected: 10 -> 20 -> 30 -> back to 10
cll.remove(20)
cll.display()          // Expected: 10 -> 30 -> back to 10

Output:

10 -> 20 -> 30 -> back to 10
10 -> 30 -> back to 10

Explanation:

1. class Node[A](var data: A, var next: Node[A] = null): This is our generic Node with data and a single pointer for the next node.

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

3. add(data: A): This method adds a new node to the end of the list and adjusts the last node's next pointer to point to the head, maintaining its circular nature.

4. remove(data: A): This method searches for a node with the specified data and removes it from the list. If the head is removed, the head pointer is moved to the next node.

5. display(): This method traverses the list until it comes back to the head and then prints the entire list.

The implemented CircularLinkedList provides a basic structure for circular traversal and offers functionality to demonstrate the operations on it.