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