Count nodes in Circular linked list
Given a circular linked list, count the number of nodes in it. For example, the output is 5 for the below list.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
We use the concept used in Circular Linked List | Set 2 (Traversal). While traversing, we keep track of the count of nodes.
C++
|
// c++ program to count number of nodes in
// a circular linked list.
#include <bits/stdc++.h>
using namespace std;
/*structure for a node*/
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* Function to insert a node at the beginning
of a Circular linked list */
struct Node* push(struct Node* last, int data)
{
if (last == NULL) {
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp->next = last;
return last;
}
// Creating a node dynamically.
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
// Adjusting the links.
temp->next = last->next;
last->next = temp;
return last;
}
/* Function to count nodes in a given Circular
linked list */
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 */
int main()
{
/* Initialize lists as empty */
Node* head = NULL;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
cout << countNodes(head);
return 0;
}
// This code is contributed by anushikaseth.
|
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 beginning
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
|
Python3
|
# Python3 program to count number of nodes in
# a circular linked list.
# structure for a node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to insert a node at the beginning
# of a Circular linked list */
def push(head_ref,data):
ptr1 = Node(0)
temp = head_ref
ptr1.data = data
ptr1.next = head_ref
# If the linked list is not None then set
# the next of last node
if (head_ref != None) :
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
def countNodes(head):
temp = head
result = 0
if (head != None) :
while True :
temp = temp.next
result = result + 1
if (temp == head):
break
return result
# Driver Code
if __name__=='__main__':
# Initialize lists as empty */
head = None
head = push(head, 12)
head = push(head, 56)
head = push(head, 2)
head = push(head, 11)
print( countNodes(head))
# This code is contributed by Arnab Kundu
|
C#
|
// C# program to count number of nodes in
// a circular linked list.
using System;
class GFG
{
/* structure for a node */
public class Node
{
public int data;
public Node next;
};
/* Function to insert a node at the beginning
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 code */
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);
Console.Write( countNodes(head));
}
}
// This code is contributed by Arnab Kundu
|
Javascript
|
<script>
// javascript program to count number of nodes in
// a circular linked list. /* ure for a node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/*
* Function to insert a node at the beginning of a Circular linked list
*/
function push(head_ref , data) {
var ptr1 = new Node();
var 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
*/
function countNodes(head) {
var temp = head;
var result = 0;
if (head != null) {
do {
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program to test above functions */
/* Initialize lists as empty */
var head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
document.write(countNodes(head));
// This code contributed by umadevi9616
</script>
|
Output:
4This article is contributed by Rishabh jain. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Article Tags :
Linked List
circular linked list
Practice Tags :
Linked List
circular linked list
Read Full Article
Required knowledge
Do while loop, Functions, Pointers, Structures, Dynamic Memory Allocation
Logic to count nodes in a Circular Linked List
Step by step descriptive logic to count nodes in a circular linked list.
- Create a Circular Linked List and assign reference of first node to head.
- Initialize count = 0; variable to store total nodes in list.
- Initialize another variable to traverse list, say current = head;.
- Increment count++ and current = current->next;.
- Repeat step 4 till you reach head node after traversing once.
Program to count nodes in Circular Linked List
/** * C program to count nodes in a Circular Linked List */ #include <stdio.h> #include <stdlib.h> /* Basic structure of node */ struct node { int data; struct node * next; }; /* Function declaration */ void createList(struct node **head, int n); void displayList(struct node *head); int count(struct node *head); int main() { int n, choice; struct node *head = NULL; /* * Run forever until user chooses 0 */ while(choice != 0) { printf("--------------------------------------------\n"); printf(" CIRCULAR LINKED LIST PROGRAM \n"); printf("--------------------------------------------\n"); printf("1. Create List\n"); printf("2. Display list\n"); printf("3. Count nodes\n"); printf("0. Exit\n"); printf("--------------------------------------------\n"); printf("Enter your choice : "); scanf("%d", &choice); switch(choice) { case 1: printf("Enter total node to create: "); scanf("%d", &n); createList(&head, n); break; case 2: displayList(head); getchar(); // Hold screen getchar(); // Hold screen break; case 3: printf("Total nodes = %d\n", count(head)); getchar(); // Hold screen getchar(); // Hold screen break; case 0: printf("Exiting from application"); exit(0); break; default: printf("Error! Invalid choice. Please choose between 0-3"); } printf("\n\n\n\n\n"); } return 0; } /** * Function to count total number of nodes in Circular Linked List */ int count(struct node *head) { int total = 0; struct node *current = head; // Iterate till end of list do { current = current->next; total++; } while (current != head); // Return total nodes in list return total; } /** * Creates a circular linked list of n nodes. */ void createList(struct node **head, int n) { int i, data; struct node *prevNode, *newNode; prevNode = NULL; newNode = NULL; /* Creates and links rest of the n-1 nodes */ for(i=1; i<=n; i++) { // Create a new node newNode = (struct node *) malloc(sizeof(struct node)); printf("Enter data of %d node: ", i); scanf("%d", &data); newNode->data = data; newNode->next = NULL; // Link the previous node with newly created node if (prevNode != NULL) prevNode->next = newNode; // Move the previous node ahead prevNode = newNode; // Link head node if not linked if (*head == NULL) *head = newNode; } // Link last node with first node prevNode->next = *head; printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n"); } /** * Display node content of circular linked list */ void displayList(struct node *head) { struct node *current; int n = 1; // Nothing to print in list if(head == NULL) { printf("List is empty.\n"); return; } current = head; printf("DATA IN THE LIST:\n"); do { // Print current node printf("Data %d = %d\n", n++, current->data); // Move to next node current = current->next; } while (current != head); }Output
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Count nodes
0. Exit
--------------------------------------------
Enter your choice : 1
Enter total node to create: 5
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
Enter data of 5 node: 50
CIRCULAR LINKED LIST CREATED SUCCESSFULLY
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Count nodes
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 30
Data 4 = 40
Data 5 = 50
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Count nodes
0. Exit
--------------------------------------------
Enter your choice : 3
Total nodes = 5
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Count nodes
0. Exit
--------------------------------------------
Enter your choice : 0
Exiting from application
Happy coding 😉