C++ Data Structures - Circular Doubly Linked List Other Related Topics

C++ - Count nodes in the Circular Doubly Linked List



Counting nodes in a circular doubly linked list is very useful while working on it. It requires creating a temp node pointing to the head of the list and a variable called i with initial value 0. If the temp node is not null, increase i by 1 and move to the next node using temp next. Repeat the process till the temp node reaches the head. The final value of i will be the total number of nodes in the circular doubly linked list.

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

int countNodes() {
  
  //1. create a temp node pointing to head
  Node* temp = head;

  //2. create a variable to count nodes
  int i = 0;
  
  //3. if the temp node is not null increase 
  //   i by 1 and move to the next node, repeat
  //   the process till the temp becomes null
  if(temp != NULL) {
    i++;
    temp = temp->next;
  }
  while(temp != head) {
    i++;
    temp = temp->next;
  }

  //4. return the count
  return i;  
} 

The below is a complete program that uses above discussed concept of counting the total number of nodes of a 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;
      }    
    }

    //count nodes in the list
    int countNodes() {
      Node* temp = head;
      int i = 0;
      if(temp != NULL) {
        i++;
        temp = temp->next;
      }
      while(temp != head) {
        i++;
        temp = temp->next;
      }
      return i;  
    } 

    //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 four elements in the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.push_back(40);

  //Display the content of the list.
  MyList.PrintList();

  //number of nodes in the list
  cout<<"No. of nodes: "<<MyList.countNodes();
  
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 40
No. of nodes: 4