Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Deletion in a Doubly Linked List | C Program

Deletion in doubly linked list

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

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 for (A Value)

#include <stdio.h>
#include <stdlib.h>

struct Node{
  int data;
  struct Node *next;
  struct Node *prev;
};

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;
  // *head->prev = newNode; would not work it has (*head) must be used

  //changing the new head to this freshly entered node
  *head = newNode;
}

void delete(struct Node** head, int delVal)
{
  struct Node* temp = *head;
  struct Node* previous = (struct Node*) malloc(sizeof(struct Node));

  //Case when there is only 1 node in the list

  if(temp->next == NULL)
  {
    *head = NULL;
    free(temp);
    printf("Value %d, deleted \n",delVal);
    return;

  }
  //if the head node itself needs to be deleted
  if(temp!=NULL && temp->data==delVal)
  {
    //Case 1 head becomes 30
    *head = temp->next; //changing head to next in the list
    (*head)->prev = NULL; //assing new head's previous value to NULL

    //case 1: 22 deleted and freed
    free(temp);
    printf("Value %d, deleted \n",delVal);

    return;
  }
  
  //run until we find the value to be deleted in the list
  while (temp != NULL && temp->data != delVal) 
  { 
    //store previous link node as we need to change its next val
    previous = temp;
    temp = temp->next;
  }

  //if value is not present then
  //temp will have traversed to last node NULL
  if(temp==NULL)
  {
    printf("Value not found\n");
    return;
  }

  // Case 2: (24)->next = 16 (as 20->next = 16) 
  // Case 3: (16)->next = NULL (as 12->next = NULL)
  previous->next = temp->next;

  //If the last node is to be deleted
  if(temp->next == NULL)
  {
// Case 3: Just need to free the memory printf("Value %d, deleted \n",delVal); free(temp); return; } struct Node* temp2 = (struct Node*) malloc(sizeof(struct Node)); // Case 2 : temp2 = 20->next = 16 temp2 = temp->next; temp2->prev = previous; free(temp); //case 2: 20 deleted and freed printf("Value %d, deleted \n",delVal); } //function to print the doubly linked list void display(struct Node* node) { printf("List :"); while (node != NULL) { printf(" %d ", node->data); node = node->next; } printf("\n"); } int main() { struct Node* head = NULL; /*Need & i.e. address as we need to change head address only needs to traverse and access items temporarily*/ insert(&head,12); insert(&head,16); insert(&head,20); insert(&head,24); insert(&head,30); insert(&head,22); /*No need for & i.e. address as we do not need to change head address*/ display(head); //deleting first occurance of a value in linked list delete(&head,22); display(head); delete(&head,20); display(head); delete(&head,12); display(head); delete(&head,30); display(head); delete(&head,16); display(head); delete(&head,24); display(head); return 0; }

Output

List : 22  30  24  20  16  12
Value 22, deleted
List : 30  24  20  16  12
Value 20, deleted
List : 30  24  16  12
Value 12, deleted
List : 30  24  16
Value 30, deleted
List : 24  16
Value 16, deleted
List : 24
Value 24, deleted
List: