 # Insertion in doubly linked list | Operations on doubly linked list

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 • 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.

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 pointersstruct 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 nodesscanf("%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 NULLhead->next = NULL; // HEAD nodes's next is set to NULLlast = 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 nodenewNode->next = NULL;last->next = newNode; // Link previous node with the new nodelast = 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 listwhile(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 headnewNode->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 ## Insertion at the end of the doubly linked list • 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 pointersstruct 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 nodesscanf("%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 NULLhead->next = NULL; // HEAD nodes's next is set to NULLlast = 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 nodenewNode->next = NULL;last->next = newNode; // Link previous node with the new nodelast = 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 listwhile(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 NULLnewNode->prev = last;  // prev pointer of newNode is referenced to the last nodelast->next = newNode; // next pointer of the last node is referenced to the newNodelast = newNode;  // newNode is made as the last node}}`

OUTPUT ## Insertion at the given position in the doubly linked list • 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 pointersstruct 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 nodesscanf("%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 NULLhead->next = NULL; // HEAD nodes's next is set to NULLlast = 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 nodenewNode->next = NULL;last->next = newNode; // Link previous node with the new nodelast = 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 nodenewNode->prev = temp; // Connect new node with n - 1th nodeif(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 ### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`