Insertion in doubly linked list | Operations on doubly linked list

20 min read

Insertion in doubly linked list can happen at various places in the list. A few cases are:

  • At the beginning of the doubly linked list.
  • At the end of the doubly linked list.
  • At a given position in the doubly linked list.

 

Insertion at the beginning of the doubly linked list

insertion in doubly linked list beginning

  • Let us assume a newNode as shown above. The newNode with data = 25 has to be inserted at the beginning of the list.
  • The next pointer of the newNode is referenced to the head node and its previous pointer is referenced to NULL.
  • The previous pointer of the head node is referenced to the newNode.
  • The newNode is then made as the head node.

 

C program to insert insert a node at the beginning of a doubly linked list

#include <stdio.h>
#include <stdlib.h>
//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

void createList(int n);
void displayList();
void insertAtBeginning(int data);

int main()
{
int n, data, choice=1;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
displayList();
printf("\n\nEnter data of first node : ");
scanf("%d", &data);
insertAtBeginning(data);
displayList();
return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", i);
scanf("%d", &data);
newNode->data = data;
newNode->prev = last; // Link new node with the previous node
newNode->next = NULL;
last->next = newNode; // Link previous node with the new node
last = newNode; // Make new node as last node
}}}

void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
printf("\nTHE DOUBLY LINKED LIST IS :\n\n");
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}}}

/* Function to insert node at the beginning of the list */
void insertAtBeginning(int data)
{
struct node * newNode;
if(head == NULL)
{
printf("Error, List is Empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head; // Point to next node which is currently head
newNode->prev = NULL; // Previous node of first node is NULL
/* Link previous address field of head with newNode */
head->prev = newNode;
/* Make the new node as head node */
head = newNode;
}
}

OUTPUT

insert-beginning-dll


Insertion at the end of the doubly linked list

doubly-linked-list-insertion-end

  • Now, let us assume a newNode as shown above. The newNode with data = 25 has to be inserted at the end of the linked list.
  • Make the next pointer of the last node to point to the newNode .
  • The next pointer of the newNode is referenced to NULL and its prev pointer is made to point to the last node.
  • Then, the newNode is made as the last node.

 

C  program to insert a node at the end of a doubly linked list

#include <stdio.h>
#include <stdlib.h>
//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

void createList(int n);
void displayList();
void insertAtEnd(int data);

int main()
{
int n, data, choice=1;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
displayList();
printf("\n\nEnter data of Last node : ");
scanf("%d", &data);
insertAtEnd(data);
displayList();
return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", i);
scanf("%d", &data);
newNode->data = data;
newNode->prev = last; // Link new node with the previous node
newNode->next = NULL;
last->next = newNode; // Link previous node with the new node
last = newNode; // Make new node as last node
}
}
}

void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
printf("\nTHE DOUBLY LINKED LIST IS :\n\n");
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}}}

/* Function to insert node at the end of the list */
void insertAtEnd(int data)
{
struct node * newNode;
if(last == NULL)
{
printf("Error, List is empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL; // next pointer of newNode is NULL
newNode->prev = last; // prev pointer of newNode is referenced to the last node
last->next = newNode; // next pointer of the last node is referenced to the newNode
last = newNode; // newNode is made as the last node
}
}

OUTPUT

insert-end-dll

Insertion at the given position in the doubly linked list

doubly-linked-list-insertion-given-position

  • Now let us assume that a newNode with data = 25 has to be inserted at position 2 in the linked list.
  • Start traversing the list from head and move upto the position - 1. In this case, since we want to insert at second position, you need to traverse till (2 - 1) = 1 st node.
  • Once you reach the position - 1 node, the next pointer of the newNode is set to the address contained by the next pointer of the (position - 1) th node.
  • Make the next pointer of the (position - 1) th node to point to the newNode and the prev pointer of the newNode is pointed to the (position - 1) th node
  • Finally the newNode next 's prev pointer must be made to point to the newNode.

 

C program to insert a node at a given position in the linked list

#include <stdio.h>
#include <stdlib.h>
//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

void createList(int n);
void displayList();
void insert_given_pos(int data, int position);

int main()
{
int n, data, pos;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
displayList();
printf("\n\nEnter data of Last node : ");
scanf("%d", &data);
printf("\nEnter the position : ");
scanf("%d",&pos);
insert_given_pos(data, pos);
displayList();
return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", i);
scanf("%d", &data);
newNode->data = data;
newNode->prev = last; // Link new node with the previous node
newNode->next = NULL;
last->next = newNode; // Link previous node with the new node
last = newNode; // Make new node as last node
}}}

void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
printf("\nTHE DOUBLY LINKED LIST IS :\n\n");
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}
}
}

void insert_given_pos(int data, int position)
{
int i;
struct node * newNode, *temp;
if(head == NULL)
{
printf("Error, List is empty!\n");
}
else
{
temp = head;
i=0;
while(i<position-1 && temp!=NULL)
{
temp = temp->next;
i++;
}
if(temp!=NULL)
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = temp->next; // Connect new node with n + 1th node
newNode->prev = temp; // Connect new node with n - 1th node
if(temp->next != NULL)
{
/* Connect pos+1th node with new node */
temp->next->prev = newNode;
}
/* Connect pos-1th node with new node */
temp->next = newNode;
}
else
{
printf("Error, Invalid position\n");
}}}


OUTPUT

insert-position-dll


POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error