In a circular singly linked list, the last node in the list contains a pointer to the first node in the list. There is a single-linked circular list and a double-linked circular list.
Traverses a single linked circular list until it reaches the same node that started it. Such a single circular list has no beginning or end. There is no null value in the next part of any node.
The layout shown below is for a single-linked list.
Declaration:
You can declare a node in a circular linked list as another node, as shown below.
struct Node
{
int data;
struct Node *next;
};
To implement a circular linked list, we keep an external “last” pointer that points to the last node in the circular linked list. So last-> next points to the first node in the linked list.
Doing this avoids having to go through the entire list when inserting a new node at the beginning or end of the list. This is because last points to the last node and last-> next points to the first node.
This was not possible if the outer pointer was pointing to the first node.
Insertion in Circular Singly Linked List:
You can insert a node in a circular linked list as the first node (empty list), first, last, or between other nodes. Let’s take a look at each of these insert operations using the figure below.
A node can be added in four ways:
- Insertion in an empty list.
- Insertion at the beginning of the list.
- Insertion at the end of the list.
- Insertion in between the nodes.
1. Insert in an empty list:
If the circular list has no nodes and the list is empty, the last pointer is null. Then point the last pointer to node N as above and insert a new node N. The pointer after N points to node N itself because it only has one node. Therefore, N is the first and last node in the list.
For example:
Here Code:
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp -> data = data;
last = temp;
temp -> next = last;
return last;
}
2. Insert at the beginning of the list:
As shown in the expression above, when you add a node to the beginning of the list, the pointer next to the last node points to the new node N, making it the first node.
N->next = last->next Last->next = N
For example:
Here Code:
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
return last;
}
3. Insert at the end of the list:
To insert a new node at the end of the list, follow these steps:
N-> next = last ->next; last ->next = N last = N
For example:
Here Code:
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
4. Insertion in between the nodes:
If you need to insert a new node N between N3 and N4, you must first go through the list to find the node where the new node will be inserted (in this case N3).
Once you find the node, do the following:
N -> next = N3 -> next; N3 -> next = N
This will insert a new node N after N3.
For example:
Here Code:
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while (p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
Below is a complete program that creates a single linked circular list using all of the above methods.
For example:
Here Code:
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
temp -> data = data;
last = temp;
last -> next = last;
return last;
}
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
return last;
}
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
void traverse(struct Node *last)
{
struct Node *p;
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
p = last -> next;
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
int main()
{
struct Node *last = NULL;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
return 0;
}
Conclusion:
A circular linked list is a type of data structure that maintains a loop that is used to store the first node in the list in the last node in the linked list and is therefore called circular. These lists are useful for building continuous loops that are used in various complex data structures and games, such as the Fibonacci sequence.
Recommended Posts:
- How to reverse a linked list?
- How to swap nodes in a linked list without Swapping data?
- How to write C functions that modify head pointer of a Linked List?
- Find Length of a Linked List (Iterative and Recursive)?
- A Programmer’s approach of looking at Array vs. Linked List
- Deletion in Linked List
- How to delete a node in a linked list at a given Location?
- Insertion in Linked List
- Differences between Arrays and Linked Lists?
- Introduction to Linked List