WikiGalaxy
Operations on Circular Linked List
Introduction:
A Circular Linked List is a linked list where the last node points to the first node, forming a circle. This structure allows for efficient traversal from any node.
Insertion at the Beginning:
Inserting at the beginning involves adjusting the last node's next pointer to the new node and pointing the new node to the current head.
Insertion at the End:
To insert at the end, traverse to the last node and adjust its next pointer to the new node, then point the new node to the head.
Deletion of a Node:
Deletion involves finding the node to be deleted and adjusting the previous node's next pointer to skip the deleted node.
Traversal:
Traversal can start from any node and continue until the starting node is reached again, ensuring all nodes are visited.
// Diagram for Circular Linked List Operations
Step 1: [Head] -> [Data | Next] -> [Data | Next] -> [Data | Head]
Step 2: Insertion at Beginning
[New] -> [Head] -> [Data | Next] -> [Data | Head]
Step 3: Insertion at End
[Head] -> [Data | Next] -> [Data | New] -> [Head]
Step 4: Deletion of a Node
[Head] -> [Data | Next] -> [Head]
Step 5: Traversal
Start at any node and visit all nodes until returning to the start
class CircularLinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
}
void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
}
void deleteNode(int key) {
if (head == null) return;
Node temp = head, prev = null;
while (temp.data != key) {
if (temp.next == head) {
System.out.println("Node not found");
return;
}
prev = temp;
temp = temp.next;
}
if (temp.next == head && prev == null) {
head = null;
return;
}
if (temp == head) {
prev = head;
while (prev.next != head) {
prev = prev.next;
}
head = temp.next;
prev.next = head;
} else if (temp.next == head) {
prev.next = head;
} else {
prev.next = temp.next;
}
}
void traverse() {
if (head != null) {
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
}
Explanation of Code:
The CircularLinkedList class provides methods to insert nodes at the beginning and end, delete nodes by key, and traverse the list. Each operation maintains the circular nature of the list.
