C - Delete last node by key of the Doubly Linked List

In this method, last node in the doubly linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->20->40 and the last occurrence of 20 is deleted, the List becomes 10->20->30->40.

If the head of the doubly linked list is not null, create three nodes: 1. lastNode - to track the last node with value equal to key, 2. previousToLast - to track node previous to lastNode, and 3. temp - to traverse through the list. Then traverse the list to its end while updating lastNode and previousToLast whenever find a node with value equal to the specified key. At last delete lastNode and update links accordingly.

The function pop_last is created for this purpose. It is a 3-step process.

void pop_last(struct Node** head_ref, int key) {     

  //1. if head is not null create three nodes
  //   lastNode - to track last node with value
  //   equal to key, previousToLast - to track 
  //   node previous to lastNode, temp - to
  //   traverse through the list
  if(*head_ref != NULL) {
    struct Node *previousToLast, *lastNode, *temp; 
    previousToLast = NULL;
    lastNode = NULL;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if((*head_ref)->data == key) 
      lastNode = *head_ref;
    
    temp = *head_ref;
    while(temp->next != NULL) {
      if(temp->next->data == key) {
        previousToLast = temp;
        lastNode = temp->next;
      }
      temp = temp->next;
    }
 
    //3. Delete the lastNode and update all links
    if(lastNode != NULL) {
      if(lastNode == *head_ref) {
        *head_ref = (*head_ref)->next;
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        if(previousToLast->next != NULL)
          previousToLast->next->prev = previousToLast;        
        free(lastNode);
      }
    }
  }
}

The below is a complete program that uses above discussed concept to delete last occurrence of the specified key (if exists) of the doubly linked list.

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

//node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  newNode->prev = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
  } else {
    temp = *head_ref;
    while(temp->next != NULL) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->prev = temp;
  }
}

//Delete last node by key
void pop_last(struct Node** head_ref, int key) {     

  if(*head_ref != NULL) {
    struct Node *previousToLast, *lastNode, *temp; 
    previousToLast = NULL;
    lastNode = NULL;

    if((*head_ref)->data == key) 
      lastNode = *head_ref;
    
    temp = *head_ref;
    while(temp->next != NULL) {
      if(temp->next->data == key) {
        previousToLast = temp;
        lastNode = temp->next;
      }
      temp = temp->next;
    }

    if(lastNode != NULL) {
      if(lastNode == *head_ref) {
        *head_ref = (*head_ref)->next;
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        if(previousToLast->next != NULL)
          previousToLast->next->prev = previousToLast;        
        free(lastNode);
      }
    }
  }
}  

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (temp != NULL) {
      printf("%i ",temp->data);
      temp = temp->next;  
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code
int main() {
  struct Node* MyList = NULL;

  //Add five elements at the end of the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 20);
  push_back(&MyList, 40);
  PrintList(MyList);

  //Delete the last occurrence of 20
  pop_last(&MyList, 20);
  PrintList(MyList);  

  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 20 40 
The list contains: 10 20 30 40