Write a program to create a circular linked list and insert a new node at the beginning or at any position in the given list. How to insert a new node at the beginning of a circular linked list in C. How to insert a new node at any position in a circular linked list in C. Algorithm to insert new node in Circular linked list in C program.
Required knowledge
Basic C programming, Functions, Dynamic memory allocation, Circular linked list
Algorithm to insert a new node at the beginning of a Circular linked list
For inserting new node at the beginning of a circular linked list. We need to connect new node with the first node and re-connect the last node with new node instead of head node.
Algorithm to insert new node at the beginning of Circular linked list
%%Input : head {Pointer to first node of the linked list}
Begin
If (head == NULL) then
write ('List is empty')
End if
Else then
alloc (newNode)
read (data)
newNode.data ← data;
newNode.next ← head;
current ← head;
While (current.next != head) do
current ← current.next;
End while
current.next ← newNode;
End if
EndAlgorithm to insert new node at the any position in Circular linked list
Algorithm to insert new node at any position of a circular linked list
%%Input : head {Pointer to first node of the list}
N {Position where to insert}
Begin
If (head == NULL) then
write ('List is empty')
End if
Else if (N == 1) then
insertAtBeginning()
End if
Else then
alloc (newNode)
read (data)
newNode.data ← data;
current ← head;
For count ← 2 to N-1 do
current ← current.next;
End for
newNode.next ← current.next;
current.next ← newNode;
End if
EndSteps to insert new node in a Circular linked list
Suppose we want to insert a new node in the circular linked list at 3 position i.e. just after 2nd position. The list initially contains 3 nodes. We will follow below steps to insert node at 2nd position in the list.
- Create a newNode and assign some data to its data field.
- Traverse to N-1 position in the list, in our case since we want to insert node at 3rd position therefore we would traverse to 3-1 = 2nd position in the list. Say current pointer points to N-1th node.
- Link the next pointer field of newNode with the node pointed by the next pointer field of current(N-1) node. Which means newNode.next = current.next.
- Connect the next pointer field of current node with the newly created node which means now next pointer field of current node will point to newNode and you are done.
Program to insert node in circular linked list
/**
* C program to insert a new node in a Circular Linked List
*/
#include <stdio.h>
#include <stdlib.h>
/*
* Basic structure of Node
*/
struct node {
int data;
struct node * next;
}*head;
/*
* Functions used in this program
*/
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtN(int data, int position);
int main()
{
int n, data, choice=1;
head = NULL;
/*
* Runs forever until user chooses 0
*/
while(choice != 0)
{
printf("============================================\n");
printf("CIRCULAR LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Display list\n");
printf("3. Insert at beginning\n");
printf("4. Insert at any position\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);
createList(n);
break;
case 2:
displayList();
break;
case 3:
printf("Enter data to be inserted at beginning: ");
scanf("%d", &data);
insertAtBeginning(data);
break;
case 4:
printf("Enter node position: ");
scanf("%d", &n);
printf("Enter data you want to insert at %d position: ", n);
scanf("%d", &data);
insertAtN(data, n);
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-4");
}
printf("\n\n\n\n\n");
}
return 0;
}
/**
* Creates a circular linked list of n nodes.
* @n Number of nodes to be created
*/
void createList(int n)
{
int i, data;
struct node *prevNode, *newNode;
if(n >= 1)
{
/*
* Creates and links the head node
*/
head = (struct node *)malloc(sizeof(struct node));
printf("Enter data of 1 node: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
prevNode = head;
/*
* Creates and links rest of the n-1 nodes
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
//Links the previous node with newly created node
prevNode->next = newNode;
//Moves the previous node ahead
prevNode = newNode;
}
//Links the last node with first node
prevNode->next = head;
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}
}
/**
* Displays the content of the list
*/
void displayList()
{
struct node *current;
int n = 1;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
current = head;
printf("DATA IN THE LIST:\n");
do {
printf("Data %d = %d\n", n, current->data);
current = current->next;
n++;
}while(current != head);
}
}
/**
* Inserts a new node at the beginning of the list
* @data Data of the first node
*/
void insertAtBeginning(int data)
{
struct node *newNode, *current;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
/*
* Creates new node, assign data and links it to head
*/
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head;
/*
* Traverses to last node and links last node
* with first node which is new node
*/
current = head;
while(current->next != head)
{
current = current->next;
}
current->next = newNode;
/*Makes new node as head node*/
head = newNode;
printf("NODE INSERTED SUCCESSFULLY\n");
}
}
/**
* Inserts a new node at any position in the list
* @data Data of the new node
* @position Position where to insert new node
*/
void insertAtN(int data, int position)
{
struct node *newNode, *current;
int i;
if(head == NULL)
{
printf("List is empty.\n");
}
else if(position == 1)
{
insertAtBeginning(data);
}
else
{
/*
* Creates new node and assign data to it
*/
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
/*
* Traverse to n-1 node
*/
current = head;
for(i=2; i<=position-1; i++)
{
current = current->next;
}
/* Links new node with node ahead of it and previous to it*/
newNode->next = current->next;
current->next = newNode;
printf("NODE INSERTED SUCCESSFULLY.\n");
}
}============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 1 Enter the total number of nodes in list: 2 Enter data of 1 node: 20 Enter data of 2 node: 40 CIRCULAR LINKED LIST CREATED SUCCESSFULLY ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 2 DATA IN THE LIST: Data 1 = 20 Data 2 = 40 ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 3 Enter data to be inserted at beginning: 10 NODE INSERTED SUCCESSFULLY ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 2 DATA IN THE LIST: Data 1 = 10 Data 2 = 20 Data 3 = 40 ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 4 Enter node position: 3 Enter data you want to insert at 3 position: 30 NODE INSERTED SUCCESSFULLY. ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 2 DATA IN THE LIST: Data 1 = 10 Data 2 = 20 Data 3 = 30 Data 4 = 40 ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 3. Insert at beginning 4. Insert at any position 0. Exit -------------------------------------------- Enter your choice : 0