# Find Length of a Linked List (Iterative and Recursive)

Write a function to count the number of nodes in a given singly linked list.

For example, the function should return 5 for linked list 1->3->1->2->1.

Iterative Solution

1) Initialize count as 0
2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
a) current = current -> next
b) count++;
4) Return count

Following are implementations of above algorithm to find count of nodes.

## C++

 // Iterative C++ program to find length  // or count of nodes in a linked list  #include using namespace std;    /* Link list node */ class Node  {      public:     int data;      Node* next;  };     /* Given a reference (pointer to pointer) to the head  of a list and an int, push a new node on the front  of the list. */ void push(Node** head_ref, int new_data)  {      /* allocate node */     Node* new_node =new Node();        /* put in the data */     new_node->data = new_data;         /* link the old list off the new node */     new_node->next = (*head_ref);         /* move the head to point to the new node */     (*head_ref) = new_node;  }     /* Counts no. of nodes in linked list */ int getCount(Node* head)  {      int count = 0; // Initialize count      Node* current = head; // Initialize current      while (current != NULL)      {          count++;          current = current->next;      }      return count;  }     /* Driver program to test count function*/ int main()  {      /* Start with the empty list */     Node* head = NULL;         /* Use push() to construct below list      1->2->1->3->1 */     push(&head, 1);      push(&head, 3);      push(&head, 1);      push(&head, 2);      push(&head, 1);         /* Check the count function */     cout<<"count of nodes is "<< getCount(head);      return 0;  }     // This is code is contributed by rathbhupendra

## C

 // Iterative C program to find length or count of nodes in a linked list #include #include    /* Link list node */ struct Node {     int data;     struct Node* next; };    /* Given a reference (pointer to pointer) to the head   of a list and an int, push a new node on the front   of the list. */ void push(struct Node** head_ref, int new_data) {     /* allocate node */     struct Node* new_node =             (struct Node*) malloc(sizeof(struct Node));        /* put in the data  */     new_node->data  = new_data;        /* link the old list off the new node */     new_node->next = (*head_ref);        /* move the head to point to the new node */     (*head_ref)    = new_node; }    /* Counts no. of nodes in linked list */ int getCount(struct Node* head) {     int count = 0;  // Initialize count     struct Node* current = head;  // Initialize current     while (current != NULL)     {         count++;         current = current->next;     }     return count; }    /* Driver program to test count function*/ int main() {     /* Start with the empty list */     struct Node* head = NULL;        /* Use push() to construct below list      1->2->1->3->1  */     push(&head, 1);     push(&head, 3);     push(&head, 1);     push(&head, 2);     push(&head, 1);        /* Check the count function */     printf("count of nodes is %d", getCount(head));     return 0; }

## Java

 // Java program to count number of nodes in a linked list    /* Linked list Node*/ class Node {     int data;     Node next;     Node(int d)  { data = d;  next = null; } }    // Linked List class class LinkedList {     Node head;  // head of list        /* Inserts a new Node at front of the list. */     public void push(int new_data)     {         /* 1 & 2: Allocate the Node &                   Put in the data*/         Node new_node = new Node(new_data);            /* 3. Make next of new Node as head */         new_node.next = head;            /* 4. Move the head to point to new Node */         head = new_node;     }        /* Returns count of nodes in linked list */     public int getCount()     {         Node temp = head;         int count = 0;         while (temp != null)         {             count++;             temp = temp.next;         }         return count;     }        /* Driver program to test above functions. Ideally        this function should be in a separate user class.        It is kept here to keep code compact */     public static void main(String[] args)     {         /* Start with the empty list */         LinkedList llist = new LinkedList();         llist.push(1);         llist.push(3);         llist.push(1);         llist.push(2);         llist.push(1);            System.out.println("Count of nodes is " +                            llist.getCount());     } }

## Python

 # A complete working Python program to find length of a # Linked List iteratively    # Node class class Node:     # Function to initialise the node object     def __init__(self, data):         self.data = data # Assign data         self.next = None # Initialize next as null       # Linked List class contains a Node object class LinkedList:        # Function to initialize head     def __init__(self):         self.head = None           # This function is in LinkedList class. It inserts     # a new node at the beginning of Linked List.     def push(self, new_data):            # 1 & 2: Allocate the Node &         #     Put in the data         new_node = Node(new_data)            # 3. Make next of new Node as head         new_node.next = self.head            # 4. Move the head to point to new Node         self.head = new_node           # This function counts number of nodes in Linked List     # iteratively, given 'node' as starting node.     def getCount(self):         temp = self.head # Initialise temp         count = 0 # Initialise count            # Loop while end of linked list is not reached         while (temp):             count += 1             temp = temp.next         return count       # Code execution starts here if __name__=='__main__':     llist = LinkedList()     llist.push(1)     llist.push(3)     llist.push(1)     llist.push(2)     llist.push(1)     print ("Count of nodes is :",llist.getCount())

## C#

 // C# program to count number // of nodes in a linked list using System;        /* Linked list Node*/ public class Node {     public int data;     public Node next;     public Node(int d)      {          data = d; next = null;      } }    // Linked List class public class LinkedList {     Node head; // head of list        /* Inserts a new Node at front of the list. */     public void push(int new_data)     {         /* 1 & 2: Allocate the Node &                 Put in the data*/         Node new_node = new Node(new_data);            /* 3. Make next of new Node as head */         new_node.next = head;            /* 4. Move the head to point to new Node */         head = new_node;     }        /* Returns count of nodes in linked list */     public int getCount()     {         Node temp = head;         int count = 0;         while (temp != null)         {             count++;             temp = temp.next;         }         return count;     }        /* Driver program to test above functions. Ideally     this function should be in a separate user class.     It is kept here to keep code compact */     public static void Main()     {         /* Start with the empty list */         LinkedList llist = new LinkedList();         llist.push(1);         llist.push(3);         llist.push(1);         llist.push(2);         llist.push(1);            Console.WriteLine("Count of nodes is " +                         llist.getCount());     } }    /* This code contributed by PrinciRaj1992 */

Output:

count of nodes is 5

Recursive Solution

int getCount(head)
1) If head is NULL, return 0.
2) Else return 1 + getCount(head->next)

Following are implementations of above algorithm to find count of nodes.

## C/C++

 // Recursive C program to find length or count of nodes in a linked list #include #include    /* Link list node */ struct Node {     int data;     struct Node* next; };    /* Given a reference (pointer to pointer) to the head   of a list and an int, push a new node on the front   of the list. */ void push(struct Node** head_ref, int new_data) {     /* allocate node */     struct Node* new_node =             (struct Node*) malloc(sizeof(struct Node));        /* put in the data  */     new_node->data  = new_data;        /* link the old list off the new node */     new_node->next = (*head_ref);        /* move the head to point to the new node */     (*head_ref)    = new_node; }    /* Counts the no. of occurrences of a node    (search_for) in a linked list (head)*/ int getCount(struct Node* head) {     // Base case     if (head == NULL)         return 0;        // count is 1 + count of remaining list     return 1 + getCount(head->next); }    /* Driver program to test count function*/ int main() {     /* Start with the empty list */     struct Node* head = NULL;        /* Use push() to construct below list      1->2->1->3->1  */     push(&head, 1);     push(&head, 3);     push(&head, 1);     push(&head, 2);     push(&head, 1);        /* Check the count function */     printf("count of nodes is %d", getCount(head));     return 0; }

## Java

 // Recursive Java program to count number of nodes in  // a linked list    /* Linked list Node*/ class Node {     int data;     Node next;     Node(int d)  { data = d;  next = null; } }    // Linked List class class LinkedList {     Node head;  // head of list        /* Inserts a new Node at front of the list. */     public void push(int new_data)     {         /* 1 & 2: Allocate the Node &                   Put in the data*/         Node new_node = new Node(new_data);            /* 3. Make next of new Node as head */         new_node.next = head;            /* 4. Move the head to point to new Node */         head = new_node;     }        /* Returns count of nodes in linked list */     public int getCountRec(Node node)     {         // Base case         if (node == null)             return 0;            // Count is this node plus rest of the list         return 1 + getCountRec(node.next);     }        /* Wrapper over getCountRec() */     public int getCount()     {         return getCountRec(head);     }        /* Driver program to test above functions. Ideally        this function should be in a separate user class.        It is kept here to keep code compact */     public static void main(String[] args)     {         /* Start with the empty list */         LinkedList llist = new LinkedList();         llist.push(1);         llist.push(3);         llist.push(1);         llist.push(2);         llist.push(1);            System.out.println("Count of nodes is " +                            llist.getCount());     } }

## Python

 # A complete working Python program to find length of a # Linked List recursively    # Node class class Node:     # Function to initialise the node object     def __init__(self, data):         self.data = data  # Assign data         self.next = None  # Initialize next as null       # Linked List class contains a Node object class LinkedList:        # Function to initialize head     def __init__(self):         self.head = None           # This function is in LinkedList class. It inserts     # a new node at the beginning of Linked List.     def push(self, new_data):            # 1 & 2: Allocate the Node &         #        Put in the data         new_node = Node(new_data)            # 3. Make next of new Node as head         new_node.next = self.head            # 4. Move the head to point to new Node         self.head = new_node        # This function counts number of nodes in Linked List     # recursively, given 'node' as starting node.     def getCountRec(self, node):         if (not node): # Base case             return 0         else:             return 1 + self.getCountRec(node.next)        # A wrapper over getCountRec()     def getCount(self):        return self.getCountRec(self.head)    # Code execution starts here if __name__=='__main__':     llist = LinkedList()     llist.push(1)     llist.push(3)     llist.push(1)     llist.push(2)     llist.push(1)     print 'Count of nodes is :',llist.getCount()

## C#

 // Recursive C# program to count number of nodes in  // a linked list  using System;       /* Linked list Node*/ public class Node  {      public int data;      public Node next;      public Node(int d)      {          data = d; next = null;      }  }     // Linked List class  public class LinkedList  {      Node head; // head of list         /* Inserts a new Node at front of the list. */     public void push(int new_data)      {          /* 1 & 2: Allocate the Node &                  Put in the data*/         Node new_node = new Node(new_data);             /* 3. Make next of new Node as head */         new_node.next = head;             /* 4. Move the head to point to new Node */         head = new_node;      }         /* Returns count of nodes in linked list */     public int getCountRec(Node node)      {          // Base case          if (node == null)              return 0;             // Count is this node plus rest of the list          return 1 + getCountRec(node.next);      }         /* Wrapper over getCountRec() */     public int getCount()      {          return getCountRec(head);      }         /* Driver program to test above functions. Ideally      this function should be in a separate user class.      It is kept here to keep code compact */     public static void Main(String[] args)      {          /* Start with the empty list */         LinkedList llist = new LinkedList();          llist.push(1);          llist.push(3);          llist.push(1);          llist.push(2);          llist.push(1);             Console.WriteLine("Count of nodes is " +                          llist.getCount());      }  }     // This code is contributed 29AjayKumar

Output:

count of nodes is 5

This article is attributed to GeeksforGeeks.org

## tags:

Linked List Linked List

code

load comments