Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Algorithm
2.1.
Implementation
2.1.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
How can you determine how many nodes there are in a list?
3.2.
How do you create a node in a circular linked list?
3.3.
What does a circular linked list, for instance, entail?
3.4.
What is the structure of the nodes in a doubly circular linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count the no of Nodes in a Circular Linked List

Author Palak Mishra
1 upvote

Introduction

We'll learn how to compute the number of nodes in a circular linked list in this article.
A circular linked list is one in which the start and last nodes are connected to create a circle. The last node's address is equal to the first node's address.

                                         

Problem Statement

The aim is to calculate the number of nodes in a circular linked list.

Example

Input 1

nodes-: 27, 18, 23, 5, 8, 12

 

Output 

total number of nodes is-: 6

 

Input 2

nodes-: 1, 5, 7, 14, 16, 22, 19, 8, 9, 

 

Output 

total number of nodes is-: 9

Algorithm

  • Make a singly linked list structure that includes the node's address and data.
  • Make a push() function to push data into the node.
  • To convert a singly linked list into a circular linked list, store the address of the first node in the last node.
  • Create a count function that counts all of the nodes in a circular linked list.

Implementation

//Count the number of nodes in a circular linked list with a C program.
#include <stdio.h> 
#include <stdlib.h> 
  
/*a node's structure*/
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/*Insert a node at the start of a circular linked list with this function.  */
void push(struct Node** head_ref, int data) 
{ 
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); 
    struct Node* temp = *head_ref; 
    ptr1->data = data; 
    ptr1->next = *head_ref; 
  
    /* Set the next of the final node if the linked list is not NULL. */
    if (*head_ref != NULL) { 
        while (temp->next != *head_ref) 
            temp = temp->next; 
        temp->next = ptr1; 
    } else
        ptr1->next = ptr1; /*For the initial node */
  
    *head_ref = ptr1; 
} 
  
/* Nodes in a Circular linked list are printed using this function.*/
int countNodes(struct Node* head) 
{ 
    struct Node* temp = head; 
    int result = 0; 
    if (head != NULL) { 
        do { 
            temp = temp->next; 
            result++; 
        } while (temp != head); 
    } 
  
    return result; 
} 
  
/* Driver program */
int main() 
{ 
    /* Initialize lists as empty */
    struct Node* head = NULL; 
    push(&head, 9); 
    push(&head, 18); 
    push(&head, 27); 
    push(&head, 45); 
  
    printf("number of nodes are:%d", countNodes(head)); 
  
    return 0; 
}

You can also try this code with Online C Compiler
Run Code

Also read - Merge sort in linked list

Output: 

number of nodes are: 4 
You can also try this code with Online C Compiler
Run Code

 

Complexity Analysis

Time Complexity: O(N) Because we have to traverse the whole list.

Space Complexity: The space complexity is O(1) as we are not using any auxiliary space.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Frequently Asked Questions

How can you determine how many nodes there are in a list?

The number of nodes in a linked list can be counted using this algorithm.
1. Set the count variable to zero (count = 0).
2. Increment a count variable while traversing a linked list.
3. When a node points to a null, we’ve reached the end of a linked list and returned the count variable’s value.

How do you create a node in a circular linked list?

We use an external pointer that points to the list’s last node to implement a circular singly linked list. If we have a prior reference referring to the last node, last -> next will point to the first node. Last -> next points to node P, while last -> last points to node Z.

What does a circular linked list, for instance, entail?

The initial and last nodes of a circular linked list are joined to form a circle. The address of the previous node is the same as the address of the first node in this case.

What is the structure of the nodes in a doubly circular linked list?

A circular doubly linked list is a more complex data structure in which each node holds references to both the preceding and following node. There are no NULLs in any of the nodes in a circular doubly linked list.

Conclusion

We used traversal techniques to determine the length of the linked list, as mentioned in this article. By traversing the linked list until we reached the last node, we counted the number of nodes. The crucial thing to remember is that the previous node in a circular linked tree points to the head, not NULL. Therefore, we compared the head pointer and traversed until the current node was the head.

We hope that this article has helped you enhance your knowledge regarding the subject of Circular Linked List. 

After reading about the circular linked list, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about Doubly Linked List, How to Convert all Linked HashMap Values to a List in Java and Difference between a singly linked list and a doubly linked list  Also see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

  1. Circular Linked List Traversal
  2. Convert a given Binary Tree to Doubly Linked List
  3. Reverse a Doubly-Linked List in Given Size
  4. Memory-efficient doubly linked list
     

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

 

Live masterclass