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
Post a Comment