C++ Data Structures - Circular Doubly Linked List Other Related Topics
Python Java C++ C C# PHP R SQL DS Algo InterviewQ

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



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

First, the head of the linked list is checked for null value. If the head is not null, the value stored in it is equal to the key, and head is the only element in the list then make the head as null. If the head is not null, the value stored in it is equal to the key, the list contains more than one element then make head next as head and update the link of last element of the list with the new head. Else, traverse to the node previous to the node with value equal to key, and adjust links.

The function pop_first is created for this purpose. It is a 4-step process.

void pop_first(int key) {
  
  //1. if head is not null, create three nodes- temp,
  //   nodeToDelete and lastNode - to traverse and to 
  //   track the last node and node to delete  
  if(head != NULL) {
    Node* temp = head;
    Node* nodeToDelete = head;
    Node* lastNode;
    
    //2. if the value store at head is the key and head
    //   is the only element in the list, make it null
    if(temp->data == key) {
      if(temp->next == head) {
        head = NULL;
      } else {

        //3. if the value store at head is the key and list
        //   contains more than 1 elements, adjust links
        lastNode = head->prev;
        head = head->next;
        lastNode->next = head;
        head->prev = lastNode;
        free(nodeToDelete); 
      }
    } else {
      
      //4. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while(temp->next != head) {
        if(temp->next->data == key) {
          nodeToDelete = temp->next;
          temp->next = temp->next->next;
          temp->next->prev = temp;
          free(nodeToDelete);
          break; 
        }
        temp = temp->next;
      }
    }
  }
}

The below is a complete program that uses above discussed concept to delete first 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 first node by key
    void pop_first(int key) {
      if(head != NULL) {
        Node* temp = head;
        Node* nodeToDelete = head;
        Node* lastNode;
        if(temp->data == key) {
          if(temp->next == head) {
            head = NULL;
          } else {
            lastNode = head->prev;
            head = head->next;
            lastNode->next = head;
            head->prev = lastNode;
            free(nodeToDelete); 
          }
        } else {
          while(temp->next != head) {
            if(temp->next->data == key) {
              nodeToDelete = temp->next;
              temp->next = temp->next->next;
              temp->next->prev = temp;
              free(nodeToDelete);
              break; 
            }
            temp = temp->next;
          }
        }
      }
    }

    //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(10);
  MyList.push_back(20);
  MyList.PrintList();

  //Delete first occurrence of 20
  MyList.pop_first(20);
  MyList.PrintList();

  return 0; 
}

The above code will give the following output:

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

5