Circular Singly Linked List - DSA
In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked list as well as circular doubly linked list.
We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.
Circular Singly Linked List In DSA
A circular singly linked list is a data structure that consists of a collection of nodes, where each node has two parts: a data part and a pointer part. The data part contains the actual data that needs to be stored, while the pointer part contains a reference to the next node in the list.
In a circular singly linked list, the last node in the list points back to the first node, creating a circular structure. This means that we can traverse the list starting from any node and loop through the entire list without encountering a null reference, which would signify the end of the list.
The advantage of a circular singly linked list over a traditional singly linked list is that it allows us to efficiently traverse the list in both directions. This is because we can start at any node and follow the links in either direction until we arrive back at the starting node. Additionally, we can easily add or remove nodes from the list, as we only need to update a small number of pointers.
Diagrammatic Representation of Linked List 2
Circular linked lists are primarily used for operating system task management. A record of pages visited by a user in the past is kept in the form of a circular list of links, which can be recalled by clicking a previous button in many of the many uses of circular lists of links in computer science, including browser browsing.
Time Complexity
Space Complexity
Operations on Circular Singly linked list
Node Creation
struct node{
int data;
struct node *link;
} *head;
Insertion – Adding a new node at the nth position in a circular linked list
At the beginning
Pseudo Code to insert a node in a circular linked list at the beginning
void Insert_Beginning(){
int item;
printf("\n\nInserting Node in beginning : ");
struct node *ptr, *temp;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
printf("\nOverflow");
else{
printf("\nEnter Data Value : ");
scanf("%d",&item);
ptr->data = item;
if(head == NULL){
head = ptr;
ptr->link = head;
}
else{
temp = head;
while (temp->link != head)
temp = temp->link;
ptr->link = head;
temp->link = ptr;
head = ptr;
}
printf("Node Inserted...!");
}
}
At the end –
Pseudo Code to insert a node in a circular linked list at the end
void Insert_Last(){
printf("\n\nInserting Node at last : ");
int n;
printf("\nHow many node to insert : ");
scanf("%d",&n);
for(int i=0;i<n;i++){
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
printf("\nOverflow");
else{
printf("\nEnter Data Value : ");
scanf("%d",&item);
ptr->data = item;
if(head == NULL){
head = ptr;
ptr->link = head;
}
else{
temp = head;
while (temp->link != head)
temp = temp->link;
temp->link = ptr;
ptr->link = head;
}
}
printf("Node Inserted...!");
}
}
At any random position
void Insert_Random()
{
printf("\nInserting Node at random position :\n");
int i, location, item;
struct node *ptr, *temp;
printf("Enter Data value : ");
scanf("%d",&item);
printf("Enter the position : ");
scanf("%d",&location);
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = item;
if(ptr == NULL){
printf("\nOverflow");
}
else{
temp = head;
location --;
while(location != 1){
temp = temp->link;
location--;
}
ptr->link = temp->link;
temp->link = ptr;
printf("\nNode Inserted");
}
}
Delete any particular key
void Delete_Key(){
struct node *ptr, *temp;
int key,i;
printf("\n\nDeleting Node : ");
printf("\nEnter key to delete : ");
scanf("%d",&key);
temp = head;
while(temp->data != key){
ptr = temp;
temp = temp->link;
}
ptr->link = temp->link;
free(temp);
printf("Node Deleted..!");
}
Delete from the beginning
void Delete_Begin(){
struct node *temp;
printf("\n\nDeleting Node from beginning : ");
if(head == NULL)
printf("\nUnderflow");
else if(head->link == head){
free(head);
head = NULL;
printf("\nOnly node deleted...!");
}
else{
temp = head;
while (temp->link != head)
temp = temp->link;
temp->link = head->link;
free(head);
head = temp->link;
printf("\nNode Deleted...!");
}
}
Delete from the last
void Delete_Last(){
printf("\n\nDeleting node from last : ");
struct node *temp, *ptr;
if(head == NULL)
printf("\nUnderflow");
else if(head->link == head){
free(head);
head = NULL;
printf("\nOnly Node deleted...!");
}
else{
ptr = head;
while(ptr->link != head){
temp = ptr;
ptr = ptr->link;
}
temp->link = head;
free(ptr);
printf("\nNode Deleted...!");
}
}
Delete node of any specific position
void Delete_Random(){
struct node *ptr, *temp;
int position;
printf("\n\nDeleting Node of random position : ");
printf("\nEnter position : ");
scanf("%d",&position);
ptr = head;
while(position != 1){
temp = ptr;
ptr = ptr->link;
if(ptr == NULL){
printf("Node Can't be deleted...!");
return;
}
position --;
}
temp->link = ptr->link;
free(ptr);
printf("Node Deleted...!");
}
Search
void Search(){
printf("\n\nSearch position of key : ");
struct node *temp;
int key, flag = 0, i=1;
temp = head;
if(temp == NULL)
printf("\nEnpty List");
else{
printf("\nEnter key : ");
scanf("%d",&key);
if(temp->data == key){
printf("Item found at position : %d",i);
flag = 0;
}
else{
while(temp->link != head){
if(temp->data == key){
printf("Item found at location : %d",i);
flag = 0;
break;
}
i++;
temp = temp->link;
}
}
}
if(flag != 0)
printf("Item not found...!");
}
Also Read: Linked List - 1 in Data Structures
Circular Doubly Linked List
A circular doubly linked list is a type of data structure that consists of a collection of nodes, where each node stores a value and maintains pointers to the previous and next nodes in the list. Unlike a singly linked list, where each node has only a pointer to the next node, a circular doubly linked list has a pointer to both the previous and next nodes, allowing for efficient traversal in both directions.
In a circular doubly linked list, the last node in the list points to the first node, creating a circular structure. This means that you can traverse the list in either direction indefinitely, without ever reaching the end of the list.
Diagrammatic Representation
Time Complexity
Time Complexity
Operations on Circular Singly linked list
Node Creation
struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;
Insertion at the beginning
void Insert_Begining(){
int n;
cout<<"\n\nInserting node in begining...!";;
cout<<endl<<"Enter how many elemnts to insert : ";
cin>>n;
for(int i=0;i<n;i++)
{
struct node *ptr;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
cout<<"\nOverflow";
else{
cout<<"\nEnter data value : ";;
cin>>item;
if(head == NULL){
ptr->prev = NULL;
ptr->next = head;
head = ptr;
ptr->data = item;
}
else{
ptr->data = item;
ptr->prev = NULL;
ptr->next = head;
head->prev = ptr;
head = ptr;
}
cout<<"Node Inserted...!";;
}
}
}
Insertion at the beginning
void Insert_Last(){
cout<<"\n\nInserting node in the last ";
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr==NULL)
cout<<endl<<"OVERFLOW"<<endl;
else{
cout<<"Enter value : ";
cin>>item;
ptr->data = item;
if(head == NULL){
head = ptr;
ptr->next = head;
ptr->prev = head;
}
else{
temp = head;
while(temp->next != head)
temp = temp->next;
temp->next = ptr;
ptr->prev = temp;
head->prev = ptr;
ptr->next = head;
}
}
cout<<endl<<"Node Inserted !";
}
Insertion at the beginning
void Insert_Random(){
cout<<endl<<endl<<"Inserting node at random position : "<<endl;
int i, location, item;
struct node *ptr, *temp;
cout<<"Enter the position : ";
cin>>location;
cout<<"Enter data value : ";
cin>>item;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = item;
if(ptr == NULL)
cout<<endl<<"OVERFLOW";
else{
temp = head;
location --;
while(location != 1){
temp = temp->next ;
location --;
}
ptr->data = item;
ptr->prev = temp;
ptr->next = temp->next;
temp->next->prev = ptr;
temp->next = ptr;
cout<<endl<<"Node Inserted";
}
}
Delete from the beginning
void Delete_Beginning(){
cout<<endl<<endl<<"Deleting node from the beginning";
struct node *temp;
if(head == NULL)
cout<<endl<<"UNDERFLOW";
else if(head->next == head){
head = NULL;
free(head);
cout<<"the only node deleted";
}
else{
temp = head;
while (temp->next!=head)
{
temp = temp->next;
}
temp->next = head->next;
head->next->prev = temp;
free(head);
head = temp->next;
}
cout<<endl<<"Node Deleted ! ";
}
Comments