Java - 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;
        }
        lastNode = null;
      } else {
        previousToLast.next = lastNode.next;
        previousToLast.next.prev = previousToLast;
        lastNode = null;
      }
    }
  }
}

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.

//node structure
class Node {
    int data;
    Node next;
    Node prev;
};

class LinkedList {
  Node head;

  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.next = null;
    if(head == null) {
      head = newNode;
      newNode.next = head;
      newNode.prev = head;
    } else {
      Node temp = new 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;
          }
          lastNode = null;
        } else {
          previousToLast.next = lastNode.next;
          previousToLast.next.prev = previousToLast;
          lastNode = null;
        }
      }
    }
  } 

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(true) {
        System.out.print(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }     
};

// test the code 
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new LinkedList();

    //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();     
  }
}

The above code will give the following output:

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