Tutorialspoint.dev

Count nodes in Circular linked list

Given a circular linked list, count number of nodes in it. For example output is 5 for below list.



We use the concept used in Circular Linked List | Set 2 (Traversal). While traversing, we keep track of count of nodes.

C++

// C program to count number of nodes in
// a circular linked list.
#include <stdio.h>
#include <stdlib.h>
  
/* structure for a node */
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to insert a node at the begining
   of a Circular linked list */
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;
  
    /* If linked list is not NULL then set
       the next of last node */
    if (*head_ref != NULL) {
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    } else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1;
}
  
/* Function to print nodes in a given Circular
   linked list */
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 to test above functions */
int main()
{
    /* Initialize lists as empty */
    struct Node* head = NULL;
    push(&head, 12);
    push(&head, 56);
    push(&head, 2);
    push(&head, 11);
  
    printf("%d", countNodes(head));
  
    return 0;
}

Java

// Java program to count number of nodes in 
// a circular linked list. 
class GFG
{
  
/* ure for a node */
static class Node
    int data; 
    Node next; 
}; 
  
/* Function to insert a node at the begining 
of a Circular linked list */
static Node push( Node head_ref, int data) 
    Node ptr1 = new Node(); 
    Node temp = head_ref; 
    ptr1.data = data; 
    ptr1.next = head_ref; 
  
    /* If linked list is not null then set 
    the next of last node */
    if (head_ref != null)
    
        while (temp.next != head_ref) 
            temp = temp.next; 
        temp.next = ptr1; 
    } else
        ptr1.next = ptr1; /*For the first node */
  
    head_ref = ptr1;
    return head_ref;
  
/* Function to print nodes in a given Circular 
linked list */
static int countNodes( Node head) 
    Node temp = head; 
    int result = 0
    if (head != null)
    
        do 
        
            temp = temp.next; 
            result++; 
        } while (temp != head); 
    
  
    return result; 
  
/* Driver program to test above functions */
public static void main(String args[])
    /* Initialize lists as empty */
    Node head = null
    head = push(head, 12); 
    head = push(head, 56); 
    head = push(head, 2); 
    head = push(head, 11); 
  
    System.out.printf("%d", countNodes(head)); 
}
  
// This code is contributed by Arnab Kundu

4

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter