C Program for Circular Linked List Insertion in the middle
Circular Linked List insertion in the middle in C
We will write a Program to do insertion in the middle in a Circular Linked List in C
We will be looking at two different approaches
- Approach 1: Follows solution with an extra size variable that keeps track of the current size of Circular Linked List
- Approach 2: Follows solution where we have an additional function to calculate the size of the circular linked list anytime.
Structure Of Node
struct node
{
int data;
struct node* next;
}; 
Approach 1
Approach 2
Approach 1
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int size = 0;
void insert (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
// if its the first node being entered
if (*head == NULL)
{
*head = newNode;
(*head)->next = *head;
size++;
return;
}
// if LL already as >=1 node
struct Node *curr = *head;
// traverse till last node in LL
while (curr->next != *head)
{
curr = curr->next;
}
curr->next = newNode;
newNode->next = *head;
*head = newNode;
size++;
}
void insertMiddle (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
// if the LL was empty
if (*head == NULL)
{
// use insert function to insert
insert (head, data);
return;
}
// otherwise
struct Node *temp = *head;
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// Unique case when there is only one node in CLL
// we will be inserting at the last,
// inserting 2nd node at the last
// Example size = 1 will result in mid = 1 so entering after 1st node
// where size itself is 1 so entering last node
if (mid == size)
{
newNode->next = *head;
(*head)->next = newNode;
size++;
return;
}
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}
void display (struct Node *head)
{
// if there are no node in LL
if (head == NULL)
return;
struct Node *temp = head;
//need to take care of circular structure of LL
do
{
printf ("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
printf ("\n");
}
int main ()
{
struct Node *head = NULL;
insert (&head, 25);
insert (&head, 5);
display (head);
insertMiddle (&head, 10);
display (head);
insertMiddle (&head, 20);
display (head);
insertMiddle (&head, 15);
display (head);
return 0;
}
Output
5 25 5 10 25 5 10 20 25 5 10 15 20 25
Approach 2
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int calcSize (struct Node *head);
void insertStart (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
// if its the first node being entered
if (*head == NULL)
{
*head = newNode;
(*head)->next = *head;
return;
}
// if LL already as >=1 node
struct Node *curr = *head;
// traverse till last node in LL
while (curr->next != *head)
{
curr = curr->next;
}
// assign LL's last node's next as this new node
curr->next = newNode;
// assign newNode's next as current head
newNode->next = *head;
// change head to this new node
*head = newNode;
}
void insertMiddle (struct Node **head, int data)
{
int size = calcSize (*head);
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
// if the LL was empty
if (*head == NULL)
{
// use insert function to insert
insertStart (head, data);
return;
}
// otherwise
struct Node *temp = *head;
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// Unique case when there is only one node in CLL
// we will be inserting at the last,
// inserting 2nd node at the last
// Example size = 1 will result in mid = 1 so entering after 1st node
// where size itself is 1 so entering last node
if (mid == size)
{
newNode->next = *head;
(*head)->next = newNode;
size++;
return;
}
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}
int calcSize (struct Node *head)
{
int size = 0;
struct Node *temp = head;
if (temp == NULL)
return size;
do
{
size++;
temp = temp->next;
}
while (temp != head);
return size;
}
void display (struct Node *head)
{
// if there are no node in LL
if (head == NULL)
return;
struct Node *temp = head;
//need to take care of circular structure of LL
do
{
printf ("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
printf ("\n");
}
int main ()
{
struct Node *head = NULL;
insertStart (&head, 25);
insertStart (&head, 5);
display (head);
insertMiddle (&head, 10);
display (head);
insertMiddle (&head, 20);
display (head);
insertMiddle (&head, 15);
display (head);
return 0;
}
Output
5 25 5 10 25 5 10 20 25 5 10 15 20 25
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Circular Linked List
- Introduction to Circular Linked List
Click Here - Circular Linked List Applications
Click Here - Circular Linked List in –
- Insertion in Circular Linked List –
- Insertion at the beginning–
- Insertion at the end –
- Insertion at nth position –
- Deletion in Circular Linked List –
- Deletion from beginning in Circular Linked List –
- Deletion from nth position in Circular Linked List –
- Deletion from end in Circular Linked List –
- Insertion and Deletion in Circular Linked List – C | C++ | Java
- Split a Circular Linked List in two halves –
- Count nodes in Circular Linked List –
- Sorted Insert In Circular Linked List –
- Insertion in the middle in Circular Linked List –
Circular Linked List
- Introduction to Circular Linked List
- Circular Linked List Applications
- Circular Linked List in – C | C++ | Java
- Insertion in Circular Linked List – C | C++ | Java
- Deletion in Circular Linked List – C | C++ | Java
- Insertion and Deletion in a Circular Linked List – C | C++ | Java
- Split a Circular Linked List in two halves – C | C++ | Java
- Count nodes in Circular Linked List – C | C++ | Java
- Sorted Insert In Circular Linked List – C | C++ | Java
- Insertion in the middle in Circular Linked List – C | C++ | Java
Login/Signup to comment