Deletion in a Doubly Linked List | C Program

Deletion in doubly linked list in C

In a doubly linked list, we need to delete a node from the linked list. we just need to copy the head pointer to pointer ptr and shift the head pointer to its next.

Deletion Time Complexity (AVG)Θ(1)
Deletion Time Complexity (Worst)O(1)
Space ComplexityO(1)

So when we want to delete the node in the doubly linked list we have three ways to delete the node in another position.

  •   Deletion at beginning
  •   Deletion at middle
  •   Deletion at last

In Disadvantages, Doubly linked list occupy more space and often more operations are required for the similar tasks as compared to singly linked lists.

It is easy to reverse the linked list.

If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the previous node.

Deletion in doubly
Deletion in a Doubly linked list in C

Deletion at Beginning

Algorithm

  • Check if there is only 1 node or not
  • If there is one node
    • Assign head to NULL
    • Free memory
  • Else
    • Assign head to next node in the list
    • Assign head->prev to NULL
    • Free memory

Deletion at middle

Algorithm

  • Traverse till the target node
  • create a node called the previous storing previous node of the target node
  • Assign previous node’s next pointer to the next node of the target node
  • For the next node of the target node, its previous pointer is assigned to the targets node’s previous node’s address
  • Free memory of target node

Deletion at last

  • Traverse till the target node
  • Check if this is the last node i.e. if node->next = NULL, then its last node
  • Assign last node’s previous node’s next pointer to the last node’s next node’s address, which basically is NULL in this case
  • Free the memory

Code for Deletion in a Doubly Linked List 

#include <stdio.h>
#include <stdlib.h> struct Node{ int data; struct Node *next; struct Node *prev; }; int getLength(struct Node* node); void insert(struct Node** head, int data){ struct Node* freshNode = (struct Node*) malloc(sizeof(struct Node)); freshNode->data = data; freshNode->next = *head; freshNode->prev = NULL; // If the linked list already had atleast 1 node if(*head !=NULL) (*head)->prev = freshNode; // freshNode will become head *head = freshNode; } void deleteFront(struct Node** head) { struct Node* tempNode = *head; // if DLL is empty if(*head == NULL){ printf("Linked List Empty, nothing to delete\n"); return; } // if Linked List has only 1 node if(tempNode->next == NULL){ printf("%d deleted\n", tempNode->data); *head = NULL; return; } // move head to next node *head = (*head)->next; // assign head node's previous to NULL (*head)->prev = NULL; printf("%d deleted\n", tempNode->data); free(tempNode); } void deleteEnd(struct Node** head){ struct Node* tempNode = *head; // if DLL is empty if(*head == NULL){ printf("Linked List Empty, nothing to delete\n"); return; } // if Linked List has only 1 node if(tempNode->next == NULL){ printf("%d deleted\n", tempNode->data); *head = NULL; return; } // else traverse to the last node while (tempNode->next != NULL) tempNode = tempNode->next; struct Node* secondLast = tempNode->prev; // Curr assign 2nd last node's next to Null secondLast->next = NULL; printf("%d deleted\n", tempNode->data); free(tempNode); } void deleteNthNode(struct Node** head, int n){ //if the head node itself needs to be deleted int len = getLength(*head); // not valid if(n < 1 || n > len){ printf("Enter valid position\n"); return; } // delete the first node if(n == 1){ deleteFront(head); return; } if(n == len){ deleteEnd(head); return; } struct Node* tempNode = *head; // traverse to the nth node while (--n){ tempNode = tempNode->next; } struct Node* previousNode = tempNode->prev; // (n-1)th node struct Node* nextNode = tempNode->next; // (n+1)th node // assigning (n-1)th node's next pointer to (n+1)th node previousNode->next = tempNode->next; // assigning (n+1)th node's previous pointer to (n-1)th node nextNode->prev = tempNode->prev; // deleting nth node printf("%d deleted \n", tempNode->data); free(tempNode); } // required for deleteNthNode 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) { 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; } printf("\n\n"); } int main() { struct Node* head = NULL; insert(&head,7); insert(&head,8); insert(&head,9); insert(&head,10); insert(&head,11); insert(&head,12); display(head); deleteFront(&head); display(head); deleteEnd(&head); display(head); // delete 3rd node deleteNthNode(&head, 3); display(head); // delete 1st node deleteNthNode(&head, 1); display(head); // delete 1st node deleteEnd(&head); display(head); return 0; }

Output

List in Forward direction:  12  11  10  9  8  7 
List in backward direction: 7  8  9  10  11  12 

12 deleted
List in Forward direction:  11  10  9  8  7 
List in backward direction: 7  8  9  10  11 

7 deleted
List in Forward direction:  11  10  9  8 
List in backward direction: 8  9  10  11 

9 deleted 
List in Forward direction:  11  10  8 
List in backward direction: 8  10  11 

11 deleted
List in Forward direction:  10  8 
List in backward direction: 8  10 

8 deleted
List in Forward direction:  10 
List in backward direction: 10 

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in 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

Circular Linked List