Imagine you have a list of players in a game that repeats turns endlessly. Why is a circular linked list better than a singly linked list for this?
Think about what happens when you reach the end of the list in each case.
A circular linked list connects the last node back to the first, so you can keep moving forward endlessly without extra code to restart. A singly linked list ends at the last node, so you must manually restart from the head.
What is the output of this C# code that creates a circular linked list of 3 nodes and prints 5 nodes?
class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } class CircularList { public Node head; public void Create() { head = new Node(1); Node second = new Node(2); Node third = new Node(3); head.next = second; second.next = third; third.next = head; // circular link } public void Print(int count) { Node temp = head; for (int i = 0; i < count; i++) { System.Console.Write(temp.data + " -> "); temp = temp.next; } System.Console.WriteLine("null"); } } var cl = new CircularList(); cl.Create(); cl.Print(5);
The list loops back to the start after the last node.
The circular linked list connects node 3 back to node 1. Printing 5 nodes cycles through 1,2,3, then again 1,2 before stopping.
Which real world scenario best fits the use of a circular linked list?
Think about a process that repeats over and over without stopping.
Round robin scheduling and turn-based games require cycling through participants repeatedly, which a circular linked list models naturally.
What is wrong with this code that inserts a new node at the end of a circular linked list?
void InsertEnd(Node head, int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}Remember the last node in a circular linked list points back to the head, not null.
In a circular linked list, the last node's next points to head, so the loop must check for temp.next != head to find the last node. Checking for null causes an infinite loop.
What is the output after deleting node with value 2 from this circular linked list?
class Node {
public int data;
public Node next;
public Node(int d) { data = d; next = null; }
}
class CircularList {
public Node head;
public void Create() {
head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second;
second.next = third;
third.next = head;
}
public void Delete(int key) {
if (head == null) return;
Node curr = head, prev = null;
while (curr.data != key) {
if (curr.next == head) return; // not found
prev = curr;
curr = curr.next;
}
if (curr == head) {
Node last = head;
while (last.next != head) last = last.next;
head = head.next;
last.next = head;
} else {
prev.next = curr.next;
}
}
public void Print(int count) {
Node temp = head;
for (int i = 0; i < count; i++) {
System.Console.Write(temp.data + " -> ");
temp = temp.next;
}
System.Console.WriteLine("null");
}
}
var cl = new CircularList();
cl.Create();
cl.Delete(2);
cl.Print(4);After deleting 2, the list cycles between 1 and 3.
Node with data 2 is removed. The list becomes 1 -> 3 -> back to 1. Printing 4 nodes cycles 1,3,1,3.