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.


Comments