Cyclic List
Description
A cyclic list is a type of linked list in which the last node points back to the first node, forming a cyclic loop. This creates a non-linear data structure without endpoints.
Traversal in a cyclic list will repeat indefinitely in a circular fashion. The nodes form a closed ring structure.
Cyclic lists are useful for applications that require circular traversal like process scheduling, circular buffers, etc.
Solution
Here is an implementation of a cyclic singly linked list:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Node {
int data;
Node next;
}
class CyclicList {
Node head;
//...
public void print() {
Node n = head;
do {
System.out.print(n.data + " ");
n = n.next;
} while (n != head);
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| struct Node {
int data;
Node* next;
};
class CyclicList {
public:
Node* head;
//...
void print() {
Node* n = head;
do {
cout << n->data << " ";
n = n->next;
} while (n != head);
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Node:
def __init__(self, data):
self.data = data
self.next = None
class CyclicList:
def __init__(self):
self.head = None
def print(self):
n = self.head
while n.next != self.head:
print(n.data, end = ' ')
n = n.next
print(n.data)
|
The key property of cyclic lists is the last node pointing back to head. This creates the cyclic loop.
Description: Cyclic List
A cyclic list is a data structure where the last element is linked back to the first element, forming a loop. This is unlike regular linked lists, where the last element points to null
or None
. Cyclic lists are useful in scenarios that require round-robin processing or cyclic iteration through elements.
Solution
Creating a cyclic list is similar to creating a standard linked list. The key difference is in the way the last node is connected. Here’s how to implement a simple cyclic list in Java, C++, and Python.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public class CyclicList {
public static void main(String[] args) {
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second;
second.next = third;
third.next = head; // Make it cyclic
// Printing the list (breaking after one cycle to avoid infinite loop)
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <iostream>
struct Node {
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
int main() {
Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
head->next = second;
second->next = third;
third->next = head; // Make it cyclic
// Printing the list (breaking after one cycle to avoid infinite loop)
Node* temp = head;
do {
std::cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
std::cout << std::endl;
return 0;
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_cyclic_list(head):
temp = head
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == head:
break
print()
if __name__ == "__main__":
head = Node(1)
second = Node(2)
third = Node(3)
head.next = second
second.next = third
third.next = head # Make it cyclic
print_cyclic_list(head)
|
Key Takeaways
- A cyclic list is a special kind of linked list where the last node points back to the head node.
- Cyclic lists are useful for round-robin scheduling and looping through elements in a cycle.
- Creating a cyclic list involves setting the
next
pointer of the last node to point to the head node. - Care should be taken while traversing a cyclic list to avoid infinite loops.