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.