C Program to Insert a Node at the middle of a Linked List
Insertion in the middle of a Linked List in C
We will look at different methods to do insertion in the middle of a Singly Linked list in C
We will look at two different methods –
- Method 1: Uses additional size variable to keep track of Linked List Size
- Method 2: No additional variable, we calculate the size in realtime
Now lets have look on how to write a routine to add a node in the middle of the linked list
Method 1
Method 2
Method 1
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int size = 0;
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)
{
newNode->data = data;
newNode->next = *head;
*head = newNode;
size++;
return;
}
// otherwise
struct Node *temp = *head;
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}
void display (struct Node *node)
{
printf ("Linked List : ");
// as linked list will end when Node is Null
while (node != NULL)
{
printf ("%d ", node->data);
node = node->next;
}
printf ("\n\n");
}
int main ()
{
//creating 2 pointers of type struct Node
//So these can point to address of struct type variable
struct Node *head = NULL;
struct Node *node2 = NULL;
// allocate 3 nodes in the heap
head = (struct Node *) malloc (sizeof (struct Node));
node2 = (struct Node *) malloc (sizeof (struct Node));
head->data = 10; // data set for head node
head->next = node2; // next pointer assigned to address of node2
node2->data = 50;
node2->next = NULL;
size = 2;
display (head);
insertMiddle (&head, 20);
display (head);
insertMiddle (&head, 40);
display (head);
insertMiddle (&head, 30);
display (head);
return 0;
}
Output
Linked List : 10 50 Linked List : 10 20 50 Linked List : 10 20 40 50 Linked List : 10 20 30 40 50
Method 2
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int getCurrSize (struct Node *node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return 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)
{
newNode->data = data;
newNode->next = *head;
*head = newNode;
return;
}
// otherwise
struct Node *temp = *head;
int size = getCurrSize (*head);
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
void display (struct Node *node)
{
printf ("Linked List : ");
// as linked list will end when Node is Null
while (node != NULL)
{
printf ("%d ", node->data);
node = node->next;
}
printf ("\n\n");
}
int main ()
{
//creating 4 pointers of type struct Node
//So these can point to address of struct type variable
struct Node *head = NULL;
struct Node *node2 = NULL;
// allocate 3 nodes in the heap
head = (struct Node *) malloc (sizeof (struct Node));
node2 = (struct Node *) malloc (sizeof (struct Node));
head->data = 10; // data set for head node
head->next = node2; // next pointer assigned to address of node2
node2->data = 50;
node2->next = NULL;
display (head);
insertMiddle (&head, 20);
display (head);
insertMiddle (&head, 40);
display (head);
insertMiddle (&head, 30);
display (head);
return 0;
}
Output
Linked List : 10 50 Linked List : 10 20 50 Linked List : 10 20 40 50 Linked List : 10 20 30 40 50
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
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Login/Signup to comment