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