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(struct Node* head_ref) {
  
  //1. create a temp node pointing to head
  struct Node* temp = head_ref;
  
  //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_ref) {
    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 <stdio.h>
#include <stdlib.h>

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

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  newNode->prev = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
     newNode->prev = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
    newNode->prev = temp;
    (*head_ref)->prev = newNode;
  }
}

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

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        break;    
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code 
int main() {
  struct Node* MyList = NULL;

  //Add four elements in the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 40);

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

  //number of nodes in the list
  printf("No. of nodes: %i\n",countNodes(MyList));

  return 0; 
}

The above code will give the following output:

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