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

In this method, last node in the circular 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 circular singly 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(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 != NULL) {
    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->data == key) 
      lastNode = head;
    
    temp = head;
    while(temp->next != head) {
      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) {
        if(head->next == head)
          head = NULL;
        else {
          head->prev->next = head->next;
          head = head->next;
        }
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        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 circular doubly linked list.

#include <iostream>
using namespace std;

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

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
      } else {
        Node* temp = head;
        while(temp->next != head)
          temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        newNode->prev = temp;
        head->prev = newNode;
      }    
    }

    //Delete last node by key
    void pop_last(int key) {     
      if(head != NULL) {
        Node *previousToLast, *lastNode, *temp; 
        previousToLast = NULL;
        lastNode = NULL;
        
        if(head->data == key) 
          lastNode = head;
        
        temp = head;
        while(temp->next != head) {
          if(temp->next->data == key) {
            previousToLast = temp;
            lastNode = temp->next;
          }
          temp = temp->next;
        }

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

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(true) {
          cout<<temp->data<<" ";
          temp = temp->next;
          if(temp == head) 
            break;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }     
};

// test the code 
int main() {
  LinkedList MyList;

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

  //Delete last occurrence of 20
  MyList.pop_last(20);
  MyList.PrintList();

  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