Find length of linked list

Write a program to find length of linked list (Iterative and recursive method).

In last post : Linked list -insert,remove and traverse, we learned about basics of linked lists. In this post, we will learn how to find length of linked listThere are two ways to find length of linked list, iterative and recursive.

Iterative method to find length of linked list

Iterative method is same as traversing linked list, only additional thing to do is to keep count of number of nodes encountered before hitting end of linked list.

Algorithm for iterative method

1. Initialize counter to zero
2. Set current pointer to head pointer of list
3. Traverse linked list till end i.e. while current != NULL, repeat
   3.a increment counter
   3.b move current pointer to next i.e current <- current->next
4. return counter
#include <stdio.h>
#include <stdlib.h>
 
/* Node declaration */
typedef struct Node {
  int data;
  struct Node * next;
} Node;
 
/* Create a node of linked list */
Node * create_node(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * new_node  = (Node *)malloc(sizeof(Node));
	new_node->data = data;
	new_node->next = *headRef;
	*headRef  = new_node;
}
 
/* Finds length of linked list using iterative method */
int findLength(Node *head){
	/* 
	There is argument that we need to have current pointer, 
	we can use head pointer itself, as we are passing 
        head as value and any operation on head is not going 
        to reflect on calling function anyway.
	But for readability of code, we will have current pointer.
	*/
	Node *current = head;
	int counter = 0;
 
	while(current != NULL){
		counter++;
		current = current->next;
	}
	return counter;
}
 
int main(void) {
 
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
 
	printf("\nLength of linked list : %d", findLength(head));
	return 0;
}

Recursive method to find length of linked list

Recursive method is easy to understand. All we need to do is decrease one node from linked list and then count length of reduces linked list. Since finding length of reduced list is same as original list, same function can be called again and hence recursion. What will be terminating condition for this recursion? Well, we there are no node is the list. What shall be the length of such a list? Obviously, zero. Now, we add the removed node to that zero length list, and the length becomes 1, and then add the node which was removed previous to last node and then length becomes 2. We do so till we reach the point where we started removing nodes from linked list.  
Algorithm for recursive method  

1. If length of linked list zero, i.e. Pointer head == NULL, return 0
2. Else, remove node, and find length of remaining list
3. Add one (for the remove node) to returned length of remaining list
4. return the sum found in step 3.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
  int data;
  struct Node * next;
} Node;
 
Node * create_node(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
/* Finds length of linked list using recursive method */
int findLengthRecursive(Node * head){
	/* Terminating condition : If head is null, 
          mean there is no node in linked list */
	if(!head) return 0;
 
	return 1 + findLengthRecursive(head->next);
}

int main(void) {
 
	Node * head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
 
	printf("\nLength of linked list : %d", 
                  findLengthRecursive(head));
	return 0;
}

So which implementation is better? Well it depends. Most of the time iterative method is preferred. Reason being, recursive call involve stack implicitly and if length of linked list too long, lot of frames will be put on process stack before we start returning from recursion. This may lead to stack overflow.
Below output explains execution of recursive method.

However, I wrote recursive method code, just to make it easier to understand how recursion works on linked, and we will use this in many other problems which we will solve in future.

Complexity wise both methods to find length of linked list have same time complexity as O(n) as we need to traverse n nodes before getting length. However, recursive method implicitly requires stack space and hence requires additional space of O(n) order.

Please share if there is something is missing or wrong. If you are interested in contributing to website, please contact us.