Doubly Linked List Node Insertion in the middle in C
C Program to Insert in the middle of a Doubly Linked List
We will look at different ways of insertion in the middle for Doubly Linked list in C Program.
Methods Discussed
- Method 1: Using Global Size variable
- Method 2: Using an extra function to calculate real-time size
Basic Structure of a Doubly Linked List in C
struct Node{
int data;
struct Node *next;
struct Node *prev;
}; Insert in the middle of a Doubly Linked in C
Method 1
Method 2
Method 1
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next, *prev;
};
int size = 0;
void insert (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
//If the linked list already had atleast 1 node
if (*head != NULL)
(*head)->prev = newNode;
// changing the new head to this freshly entered node
*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)
{
// using insert function to insert at start
insert (head, data);
return;
}
// otherwise
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// will only happen when there is one node in Doubly Linked List
// we will have to insert 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 = NULL;
newNode->prev = *head;
(*head)->next = newNode;
size++;
return;
}
struct Node *temp = *head;
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
// (mid+1)th node prev to this newNode
(temp->next)->prev = newNode;
// newNode's prev to this current middle node
newNode->prev = temp;
// newNode's next to (mid+1)th node
newNode->next = temp->next;
// current mid node's next becomes this newNode
temp->next = newNode;
// this new inserted after the middle node successfully
size++;
}
//function to print the doubly linked list
void display (struct Node *node)
{
printf ("\n\n");
struct Node *end = NULL;
printf ("List in Forward direction: ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}
printf ("\nList in backward direction: ");
while (end != NULL)
{
printf (" %d ", end->data);
end = end->prev;
}
}
int main ()
{
struct Node *head = NULL;
insert (&head, 500);
insert (&head, 100);
display (head);
insertMiddle (&head, 200);
display (head);
insertMiddle (&head, 400);
display (head);
insertMiddle (&head, 300);
display (head);
return 0;
}
Output
List in Forward direction: 100 500 List in backward direction: 500 100 List in Forward direction: 100 200 500 List in backward direction: 500 200 100 List in Forward direction: 100 200 400 500 List in backward direction: 500 400 200 100 List in Forward direction: 100 200 300 400 500 List in backward direction: 500 400 300 200 100
Method 2
Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next, *prev;
};
int getLength (struct Node *node);
void insert (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
//If the linked list already had atleast 1 node
if (*head != NULL)
(*head)->prev = newNode;
// changing the new head to this freshly entered node
*head = newNode;
}
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)
{
// using insert function to insert at start
insert (head, data);
return;
}
// otherwise
int size = getLength (*head);
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
// will only happen when there is one node in Doubly Linked List
// we will have to insert 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 = NULL;
newNode->prev = *head;
(*head)->next = newNode;
return;
}
struct Node *temp = *head;
// traverse to current mid position
while (--mid)
{
temp = temp->next;
}
// (mid+1)th node prev to this newNode
(temp->next)->prev = newNode;
// newNode's prev to this current middle node
newNode->prev = temp;
// newNode's next to (mid+1)th node
newNode->next = temp->next;
// current mid node's next becomes this newNode
temp->next = newNode;
// this newNode inserted after the middle node successfully
}
int getLength (struct Node *node)
{
int len = 0;
while (node != NULL)
{
node = node->next;
len++;
}
return len;
}
//function to print the doubly linked list
void display (struct Node *node)
{
printf ("\n\n");
struct Node *end = NULL;
printf ("List in Forward direction: ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}
printf ("\nList in backward direction: ");
while (end != NULL)
{
printf (" %d ", end->data);
end = end->prev;
}
}
int main ()
{
struct Node *head = NULL;
insert (&head, 500);
insert (&head, 100);
display (head);
insertMiddle (&head, 200);
display (head);
insertMiddle (&head, 400);
display (head);
insertMiddle (&head, 300);
display (head);
return 0;
}
Output
List in Forward direction: 100 500 List in backward direction: 500 100 List in Forward direction: 100 200 500 List in backward direction: 500 200 100 List in Forward direction: 100 200 400 500 List in backward direction: 500 400 200 100 List in Forward direction: 100 200 300 400 500 List in backward direction: 500 400 300 200 100
Login/Signup to comment