Data Structure - Circular Singly Linked List
A circular singly linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and the next part that stores the pointer to the next node as shown in the below image:
The first node also known as HEAD is always used as a reference to traverse the list. The last node points to HEAD. A circular singly linked list can be visualized as a chain of nodes, where every node points to the next node. Along with this, next of the last node is linked to the head node.
Implementation of Circular Singly Linked List
Representation:
In C, a node can be created using structure. In C++, circular singly linked list can be created using a class and a Node using structures. The LinkedList class contains Node as class member.
In Java, Python, C# and PHP, circular singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
//node structure struct Node { int data; Node* next; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ head = NULL; } };
//node structure struct Node { int data; struct Node* next; };
# node structure class Node: #constructor to create a new node def __init__(self, data): self.data = data self.next = None #class Linked List class LinkedList: #constructor to create an empty LinkedList def __init__(self): self.head = None
//node structure class Node { int data; Node next; }; class LinkedList { Node head; //constructor to create an empty LinkedList LinkedList(){ head = null; } };
//node structure class Node { public int data; public Node next; }; class LinkedList { public Node head; //constructor to create an empty LinkedList public LinkedList(){ head = null; } };
//node structure class Node { public $data; public $next; } class LinkedList { public $head; //constructor to create an empty LinkedList public function __construct(){ $this->head = null; } };
Create a Circular Singly Linked List
Let us create a simple circular singly linked list which contains three data nodes.
#include <iostream> using namespace std; //node structure struct Node { int data; Node* next; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ head = NULL; } }; // test the code int main() { //create an empty LinkedList LinkedList MyList; //Add first node. Node* first = new Node(); first->data = 10; //linking with head node MyList.head = first; //linking next of the node with head first->next = MyList.head; //Add second node. Node* second = new Node(); second->data = 20; //linking with first node first->next = second; //linking next of the node with head second->next = MyList.head; //Add third node. Node* third = new Node(); third->data = 30; //linking with second node second->next = third; //linking next of the node with head third->next = MyList.head; return 0; }
#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; }; // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; //linking with head node MyList = first; //linking next of the node with head first->next = MyList; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; //linking with first node first->next = second; //linking next of the node with head second->next = MyList; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; //linking with second node second->next = third; //linking next of the node with head third->next = MyList; return 0; }
# node structure class Node: #constructor to create a new node def __init__(self, data): self.data = data self.next = None #class Linked List class LinkedList: #constructor to create an empty LinkedList def __init__(self): self.head = None # test the code # create an empty LinkedList MyList = LinkedList() #Add first node. first = Node(10) #linking with head node MyList.head = first #linking next of the node with head first.next = MyList.head #Add second node. second = Node(20) #linking with first node first.next = second #linking next of the node with head second.next = MyList.head #Add third node. third = Node(30) #linking with second node second.next = third #linking next of the node with head third.next = MyList.head
//node structure class Node { int data; Node next; }; class LinkedList { Node head; //constructor to create an empty LinkedList LinkedList(){ head = null; } }; // test the code public class Implementation { public static void main(String[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //Add second node. Node second = new Node(); second.data = 20; //linking with first node first.next = second; //linking next of the node with head second.next = MyList.head; //Add third node. Node third = new Node(); third.data = 30; //linking with second node second.next = third; //linking next of the node with head third.next = MyList.head; } }
using System; //node structure class Node { public int data; public Node next; }; class LinkedList { public Node head; //constructor to create an empty LinkedList public LinkedList(){ head = null; } }; // test the code class Implementation { static void Main(string[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //Add second node. Node second = new Node(); second.data = 20; //linking with first node first.next = second; //linking next of the node with head second.next = MyList.head; //Add third node. Node third = new Node(); third.data = 30; //linking with second node second.next = third; //linking next of the node with head third.next = MyList.head; } }
<?php //node structure class Node { public $data; public $next; } class LinkedList { public $head; //constructor to create an empty LinkedList public function __construct(){ $this->head = null; } }; // test the code //create an empty LinkedList $MyList = new LinkedList(); //Add first node. $first = new Node(); $first->data = 10; //linking with head node $MyList->head = $first; //linking next of the node with head $first->next = $MyList->head; //Add second node. $second = new Node(); $second->data = 20; //linking with first node $first->next = $second; //linking next of the node with head $second->next = $MyList->head; //Add third node. $third = new Node(); $third->data = 30; //linking with second node $second->next = $third; //linking next of the node with head $third->next = $MyList->head; ?>
Traverse a Circular Singly Linked List
A circular singly linked list can be traversed from any node of the list using a temp node. Keep on moving the temp node to the next one and displaying its content. Stop the traversal, after reaching the starting node.
#include <iostream> using namespace std; //node structure struct Node { int data; Node* next; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ head = NULL; } //display the content of the list void PrintList() { Node* temp = head; if(temp != NULL) { cout<<"The list contains: "; while(true) { cout<<temp->data<<" "; temp = temp->next; if(temp == head) break; } cout<<endl; } else { cout<<"The list is empty.\n"; } } }; // test the code int main() { //create an empty LinkedList LinkedList MyList; //Add first node. Node* first = new Node(); first->data = 10; //linking with head node MyList.head = first; //linking next of the node with head first->next = MyList.head; //Add second node. Node* second = new Node(); second->data = 20; //linking with first node first->next = second; //linking next of the node with head second->next = MyList.head; //Add third node. Node* third = new Node(); third->data = 30; //linking with second node second->next = third; //linking next of the node with head third->next = MyList.head; //print the content of list MyList.PrintList(); return 0; }
The above code will give the following output:
The list contains: 10 20 30
#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; }; //display the content of the list void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) { printf("The list contains: "); while (1) { printf("%i ",temp->data); temp = temp->next; if(temp == head_ref) break; } printf("\n"); } else { printf("The list is empty.\n"); } } // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; //linking with head node MyList = first; //linking next of the node with head first->next = MyList; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; //linking with first node first->next = second; //linking next of the node with head second->next = MyList; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; //linking with second node second->next = third; //linking next of the node with head third->next = MyList; //print the content of list PrintList(MyList); return 0; }
The above code will give the following output:
The list contains: 10 20 30
# node structure class Node: #constructor to create a new node def __init__(self, data): self.data = data self.next = None #class Linked List class LinkedList: #constructor to create an empty LinkedList def __init__(self): self.head = None #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (True): print(temp.data, end=" ") temp = temp.next if(temp == self.head): break print() else: print("The list is empty.") # test the code # create an empty LinkedList MyList = LinkedList() #Add first node. first = Node(10) #linking with head node MyList.head = first #linking next of the node with head first.next = MyList.head #Add second node. second = Node(20) #linking with first node first.next = second #linking next of the node with head second.next = MyList.head #Add third node. third = Node(30) #linking with second node second.next = third #linking next of the node with head third.next = MyList.head #print the content of list MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30
//node structure class Node { int data; Node next; }; class LinkedList { Node head; //constructor to create an empty LinkedList LinkedList(){ head = null; } //display the content of the list void PrintList() { Node temp = new Node(); temp = this.head; if(temp != null) { System.out.print("The list contains: "); while(true) { System.out.print(temp.data + " "); temp = temp.next; if(temp == this.head) break; } System.out.println(); } else { System.out.println("The list is empty."); } } }; // test the code public class Implementation { public static void main(String[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //Add second node. Node second = new Node(); second.data = 20; //linking with first node first.next = second; //linking next of the node with head second.next = MyList.head; //Add third node. Node third = new Node(); third.data = 30; //linking with second node second.next = third; //linking next of the node with head third.next = MyList.head; //print the content of list MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30
using System; //node structure class Node { public int data; public Node next; }; class LinkedList { public Node head; //constructor to create an empty LinkedList public LinkedList(){ head = null; } //display the content of the list public void PrintList() { Node temp = new Node(); temp = this.head; if(temp != null) { Console.Write("The list contains: "); while(true) { Console.Write(temp.data + " "); temp = temp.next; if(temp == this.head) break; } Console.WriteLine(); } else { Console.WriteLine("The list is empty."); } } }; // test the code class Implementation { static void Main(string[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //Add second node. Node second = new Node(); second.data = 20; //linking with first node first.next = second; //linking next of the node with head second.next = MyList.head; //Add third node. Node third = new Node(); third.data = 30; //linking with second node second.next = third; //linking next of the node with head third.next = MyList.head; //print the content of list MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30
<?php //node structure class Node { public $data; public $next; } class LinkedList { public $head; //constructor to create an empty LinkedList public function __construct(){ $this->head = null; } //display the content of the list public function PrintList() { $temp = new Node(); $temp = $this->head; if($temp != null) { echo "The list contains: "; while(true) { echo $temp->data." "; $temp = $temp->next; if($temp == $this->head) break; } echo "\n"; } else { echo "The list is empty.\n"; } } }; // test the code //create an empty LinkedList $MyList = new LinkedList(); //Add first node. $first = new Node(); $first->data = 10; //linking with head node $MyList->head = $first; //linking next of the node with head $first->next = $MyList->head; //Add second node. $second = new Node(); $second->data = 20; //linking with first node $first->next = $second; //linking next of the node with head $second->next = $MyList->head; //Add third node. $third = new Node(); $third->data = 30; //linking with second node $second->next = $third; //linking next of the node with head $third->next = $MyList->head; //print the content of list $MyList->PrintList(); ?>
The above code will give the following output:
The list contains: 10 20 30
Recommended Pages
- Circular Singly Linked List - Insert a new node at the start
- Circular Singly Linked List - Insert a new node at the end
- Circular Singly Linked List - Insert a new node at a given position
- Circular Singly Linked List - Delete the first node
- Circular Singly Linked List - Delete the last node
- Circular Singly Linked List - Delete a node at a given position
- Circular Singly Linked List - Delete all nodes
- Circular Singly Linked List - Count nodes
- Circular Singly Linked List - Delete even nodes
- Circular Singly Linked List - Delete odd nodes
- Circular Singly Linked List - Search an element
- Circular Singly Linked List - Delete first node by key
- Circular Singly Linked List - Delete last node by key
- Circular Singly Linked List - Delete all nodes by key
- Circular Singly Linked List - Reverse the List
- Circular Singly Linked List - Swap node values