C++ - 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++, doubly linked list can be created using a class and a Node using structures. The LinkedList class contains Node as class member.
//node structure struct Node { int data; Node* next; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ 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; }
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