Program for all operations on circular linked list in C
In a Circular linked list, every element has a link to its next element in the sequence and the last element has a link to the first element. A circular linked list is similar to the singly linked list except that the last node points to the first node. Below is the image to illustrate the same:
Some common operations of a circular linked list are implemented below:
Insertion at the beginning: Inserting a new node as the first node. The next pointer of last will point to this node and this new node will point to the previous first node.
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in the list
struct node* last = NULL;
// Function to insert a node in the
// starting of the list
void insertAtFront[]
{
// Stores the number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be "
"inserted: \n"];
scanf["%d", &data];
// If the new node is the only
// node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else last node contains the
// reference of the new node and
// new node contains the reference
// of the previous first node
else {
temp->info = data;
temp->next = last->next;
// last node now has reference
// of the new node temp
last->next = temp;
}
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
// While first node is not
// reached again, print,
// since the list is circular
do {
printf["\nData = %d", temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Function Call
insertAtFront[];
insertAtFront[];
insertAtFront[];
// Print list
viewList[];
return 0;
}
|
Output:
Insertion at the end: Inserting a new node as the last node. The next pointer of last will point to this node and this new node will point to the first node.
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in the list
struct node* last = NULL;
// Function to add a new node at the
// end of the list
void addatlast[]
{
// Stores number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be "
"inserted : \n"];
scanf["%d", &data];
// If the new node is the
// only node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else the new node will be the
// last node and will contain
// the reference of head node
else {
temp->info = data;
temp->next = last->next;
last->next = temp;
last = temp;
}
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
do {
printf["\nData = %d",
temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Function Call
addatlast[];
addatlast[];
addatlast[];
// Print list
viewList[];
return 0;
}
|
Output:
Insertion after a specific element: Below is the program to insert a node after a specified node in the linked list.
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in list
struct node* last = NULL;
// Function to add a new node
// at the end of the list
void addatlast[]
{
// Stores number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be inserted : \n"];
scanf["%d", &data];
// If the new node is the
// only node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else the new node will be the
// last node and will contain
// the reference of head node
else {
temp->info = data;
temp->next = last->next;
last->next = temp;
last = temp;
}
}
// Function to insert after any
// specified element
void insertafter[]
{
// Stores data and element after
// which new node is to be inserted
int data, value;
// Initialize a new node
struct node *temp, *n;
// Input data
printf["\nEnter number after which"
" you want to enter number: \n"];
scanf["%d", &value];
temp = last->next;
do {
// Element after which node is
// to be inserted is found
if [temp->info == value] {
n = [struct node*]malloc[sizeof[struct node]];
// Input Data
printf["\nEnter data to be"
" inserted : \n"];
scanf["%d", &data];
n->info = data;
n->next = temp->next;
temp->next = n;
// If temp is the last node
// so now n will become the
// last node
if [temp == last]
last = n;
break;
}
else
temp = temp->next;
} while [temp != last->next];
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
do {
printf["\nData = %d",
temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Initialize the list
addatlast[];
addatlast[];
addatlast[];
// Function Call
insertafter[];
// Print list
viewList[];
return 0;
}
|
Output:
Delete first element: Deleting the first node of the linked list. For this, the next pointer of last will point to the second node of the linked list. Below is the program for the same:
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in list
struct node* last = NULL;
// Function to add a new node
// at the end of the list
void addatlast[]
{
// Stores number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be"
" inserted: \n"];
scanf["%d", &data];
// If the new node is the only
// node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else the new node will be the
// last node and will contain
// the reference of head node
else {
temp->info = data;
temp->next = last->next;
last->next = temp;
last = temp;
}
}
// Function to delete the first
// element of the list
void deletefirst[]
{
struct node* temp;
// If list is empty
if [last == NULL]
printf["\nList is empty.\n"];
// Else last node now contains
// reference of the second node
// in the list because the
// list is circular
else {
temp = last->next;
last->next = temp->next;
free[temp];
}
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
do {
printf["\nData = %d",
temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Initialize the list
addatlast[];
addatlast[];
addatlast[];
// Function Call
deletefirst[];
// Print list
viewList[];
return 0;
}
|
Output:
Delete the last element: Deleting the last node of the linked list. For this, the second last node will point to the first node of the list. Below is the program for the same:
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in list
struct node* last = NULL;
// Function to add a new node
// at the end of the list
void addatlast[]
{
// Stores number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be inserted : \n"];
scanf["%d", &data];
// If the new node is the only
// node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else the new node will be
// last node and will contain
// the reference of head node
else {
temp->info = data;
temp->next = last->next;
last->next = temp;
last = temp;
}
}
// Function to delete the last node
// in the list
void deletelast[]
{
struct node* temp;
// If list is empty
if [last == NULL]
printf["\nList is empty.\n"];
temp = last->next;
// Traverse the list till
// the second last node
while [temp->next != last]
temp = temp->next;
// Second last node now contains
// the reference of the first
// node in the list
temp->next = last->next;
last = temp;
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
do {
printf["\nData = %d",
temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Initialize the list
addatlast[];
addatlast[];
addatlast[];
// Function Call
deletelast[];
// Print the list
viewList[];
return 0;
}
|
Output:
Delete at a given position: Delete an element from a specified position in the linked list. Below is the program for the same:
|
// C program for the above operation
#include
#include
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in list
struct node* last = NULL;
// Function to add a new node
// at the end of the list
void addatlast[]
{
// Stores number to be inserted
int data;
// Initialize a new node
struct node* temp;
temp = [struct node*]malloc[sizeof[struct node]];
// Input data
printf["\nEnter data to be inserted : \n"];
scanf["%d", &data];
// If the new node is the
// only node in the list
if [last == NULL] {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else the new node will be
// last node and will contain
// the reference of head node
else {
temp->info = data;
temp->next = last->next;
last->next = temp;
last = temp;
}
}
// Function to delete an element
// at a specified index in the list
void deleteAtIndex[]
{
// Stores the index at which
// the element is to be deleted
int pos, i = 1;
struct node *temp, *position;
temp = last->next;
// If list is empty
if [last == NULL]
printf["\nList is empty.\n"];
// Else
else {
// Input Data
printf["\nEnter index : "];
scanf["%d", &pos];
// Traverse till the node to
// be deleted is reached
while [i next;
i++;
}
// After the loop ends, temp
// points at a node just before
// the node to be deleted
// Reassigning links
position = temp->next;
temp->next = position->next;
free[position];
}
}
// Function to print the list
void viewList[]
{
// If list is empty
if [last == NULL]
printf["\nList is empty\n"];
// Else print the list
else {
struct node* temp;
temp = last->next;
do {
printf["\nData = %d", temp->info];
temp = temp->next;
} while [temp != last->next];
}
}
// Driver Code
int main[]
{
// Initialize the list
addatlast[];
addatlast[];
addatlast[];
// Function Call
deleteAtIndex[];
// Print the list
viewList[];
return 0;
}
|
Output:
Circular Singly Linked List
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.
The following image shows a circular singly linked list.
Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.
Circular Linked List
In this article, you will learn what circular linked list is and its types with implementation.
A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.
There are basically two types of circular linked list:
1. Circular Singly Linked List
Here, the address of the last node consists of the address of the first node.
2. Circular Doubly Linked List
Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node.
Note: We will be using the singly circular linked list to represent the working of circular linked list.
Linked List Operations: Traverse, Insert and Delete
In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.
There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.
Here's a list of basic linked list operations that we will cover in this article.
- Traversal - access each element of the linked list
- Insertion - adds a new element to the linked list
- Deletion - removes the existing elements
- Search - find a node in the linked list
- Sort - sort the nodes of the linked list
Before you learn about linked list operations in detail, make sure to know about Linked List first.
Things to Remember about Linked List
- head points to the first node of the linked list
- next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.
In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:
struct node { int data; struct node *next; };Circular Linked List Program in C
Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.
C Program to implement Circular linked list
Write a C Program to implement Circular linked list operations.Here’s simple Menu Driven C Program to implement circularlinked list operations like Creation, Insertion, Deletion, Display, Count, Add Node, Delete Node, Search, Reverse, etc. in C Programming Language.
Circular Linked List In C++
The arrangement shown below is for a singly linked list.
A circular linked list can be a singly linked list or a doubly linked list. In a doubly circular linked list, the previous pointer of the first node is connected to the last node while the next pointer of the last node is connected to the first node.
Its representation is shown below.
Declaration
We can declare a node in a circular linked list as any other node as shown below:
struct Node { int data; struct Node *next; };In order to implement the circular linked list, we maintain an external pointer “last” that points to the last node in the circular linked list. Hence last->next will point to the first node in the linked list.
By doing this we ensure that when we insert a new node at the beginning or at the end of the list, we need not traverse the entire list. This is because the last points to the last node while last->next points to the first node.
This wouldn’t have been possible if we had pointed the external pointer to the first node.
Basic Operations
The circular linked list supports insertion, deletion, and traversal of the list. We will discuss each of the operations in detail now.
Insertion
We can insert a node in a circular linked list either as a first node [empty list], in the beginning, in the end, or in between the other nodes. Let us see each of these insertion operations using a pictorial representation below.
#1] Insert in an empty list
When there are no nodes in circular list and the list is empty, the last pointer is null, then we insert a new node N by pointing the last pointer to the node N as shown above. The next pointer of N will point to the node N itself as there is only one node. Thus N becomes the first as well as last node in the list.
#2] Insert at the beginning of the list
As shown in the above representation, when we add a node at the beginning of the list, the next pointer of the last node points to the new node N thereby making it a first node.
N->next = last->next
Last->next = N
#3] Insert at the end of the list
To insert a new node at the end of the list, we follow these steps:
N-> next = last ->next;
last ->next = N
last = N
#4] Insert in between the list
Suppose we need to insert a new node N between N3 and N4, we first need to traverse the list and locate the node after which the new node is to be inserted, in this case, its N3.
After the node is located, we perform the following steps.
N -> next = N3 -> next;
N3 -> next = N
This inserts a new node N after N3.
Deletion
The deletion operation of the circular linked list involves locating the node that is to be deleted and then freeing its memory.
For this we maintain two additional pointers curr and prev and then traverse the list to locate the node. The given node to be deleted can be the first node, the last node or the node in between. Depending on the location we set the curr and prev pointers and then delete the curr node.
A pictorial representation of the deletion operation is shown below.
Traversal
Traversal is a technique of visiting each and every node. In linear linked lists like singly linked list and doubly linked lists, traversal is easy as we visit each node and stop when NULL is encountered.
However, this is not possible in a circular linked list. In a circular linked list, we start from the next of the last node which is the first node and traverse each node. We stop when we once again reach the first node.
Now we present an implementation of the circular linked list operations using C++ and Java. We have implemented insertion, deletion and traversal operations here. For a clear understanding, we have depicted the circular linked list as
Thus to the last node 50, we again attach node 10 which is the first node, thereby indicating it as a circular linked list.
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty[struct Node *last, int new_data] { // if last is not null then list is not empty, so return if [last != NULL] return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin[struct Node *last, int new_data] { //if list is empty then add the node by calling insertInEmpty if [last == NULL] return insertInEmpty[last, new_data]; //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd[struct Node *last, int new_data] { //if list is empty then add the node by calling insertInEmpty if [last == NULL] return insertInEmpty[last, new_data]; //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter[struct Node *last, int new_data, int after_item] { //return null if list is empty if [last == NULL] return NULL; struct Node *temp, *p; p = last -> next; do { if [p ->data == after_item] { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if [p == last] last = temp; return last; } p = p -> next; } while[p != last -> next]; cout next=[*head]->next; free[*head]; *head=last->next; } // end of list is reached or node to be deleted not there in the list while[last->next!=*head&&last->next->data!=key] { last=last->next; } // node to be deleted is found, so free the memory and display the list if[last->next->data==key] { d=last->next; last->next=d->next; cout