Circular Linked List

A circular linked list is a variation of linked list in which the last node points to the first node, forming a circular loop. This forms a non-linear data structure without endpoints.

It can be either singly or doubly linked. The nodes form a continuous cycle without null termination.

Circular linked lists are useful for implementations like round-robin scheduling, buffers, etc where continuous wrapping around is needed.

Solution

Here is an implementation of circular singly linked list:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node {
  int data;
  Node next;
}

class CircularList {
  Node head; 
  Node tail;

  // add node to end 
  public void add(int data) {
    Node node = new Node();
    node.data = data;
    if (head == null) {
      head = tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
    tail.next = head; 
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node {
  int data;
  Node* next;
};

class CircularList {
public:
  Node *head, *tail;

  // add node to end
  void add(int data) {
    Node* node = new Node();
    node->data = data;
    if (head == NULL) {
      head = tail = node; 
    } else {
      tail->next = node;
      tail = node;
    }
    tail->next = head;
  }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class CircularList:

  def __init__(self):
    self.head = None
    self.tail = None
  
  # add node to end 
  def add(self, data):
    node = Node(data)
    if not self.head:
      self.head = self.tail = node
    else:
      self.tail.next = node
      self.tail = node
    self.tail.next = self.head # circular 

The key aspect is linking tail to head to create the circular loop.

Circular lists provide a data structure with no endpoints.

Description: Circular Linked List

A Circular Linked List is a variant of the standard Linked List data structure. The last node in a Circular Linked List points back to the first node instead of having a null reference. This creates a closed-loop, making it possible to iterate through the list infinitely.

Solution:

Below are implementations for a simple Circular Linked 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    Node head;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }

    public void display() {
        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.display();
    }
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class CircularLinkedList {
private:
    Node* head;

public:
    CircularLinkedList() : head(nullptr) {}

    void add(int data) {
        Node* newNode = new Node{data, nullptr};
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    void display() {
        Node* temp = head;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        cout << endl;
    }
};

int main() {
    CircularLinkedList list;
    list.add(1);
    list.add(2);
    list.add(3);
    list.display();
    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
25
26
27
28
29
30
31
32
33
34
35
36
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def add(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        temp = self.head
        while True:
            print(temp.data, end=" ")
            temp = temp.next
            if temp == self.head:
                break
        print()

if __name__ == "__main__":
    clist = CircularLinkedList()
    clist.add(1)
    clist.add(2)
    clist.add(3)
    clist.display()

Key Takeaways

Circular Linked List has its last node point back to the first node.
It allows for endless iteration through the list, unlike a singly linked list.
The implementations in Java, C++, and Python illustrate the basic operations of adding an element and displaying the list.