Find length of Linked list - Recursive and iterative approach

To find length of linked list is one of warm-up interview question. Idea here is to write sample program to find length of list using recursion, iterative way of finding is not a big deal(iterate linked list and maintains a counter & increment for each node).A better understanding of recursion is important to solve various Linked list problems and finding length is list one of the easy problem which gives an overview of recursion.
Using recursion:- Below is sample code line which calculates length of list recursively(Download complete sample program).

/* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
 int length = 0;
 /* If list is empty or we have reached at end of list */
 if (head == null)
  return 0;
 else
  /* call this method again with next node */
  length = 1 + findLengthOfListRecursion(head.getNext());
 return length;
}

Explanation:- For each recursive call, null check for head is performed, if head is null it indicates - we have reached at end of the list and it returns 0. Otherwise, else block is executed and length is incremented by 1 and recursive call is made for next node.

Using Iterative approach :- Below is sample code line which calculates length of list by traversing list (Download complete sample program).

/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
 int length = 0;
 /* If list is empty, return length is 0 */
 if (head == null) {
  return length;
 } else {
  Node current = head;
  /* Iterate list and increment length for each node */
  while (current != null) {
   length += 1;
   current = current.getNext();
  }
 }
 return length;
}

Explanation:- Iterate the list until we reaches at end of list and increment length for each node. Once we reach at end of list, we have length of list.

Below is the complete sample program for the length calculation using recursion and iterative approach:-

public class LengthOfLinkedlist {
 static Node head;

 /* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
 int length = 0;
 /* If list is empty or we have reached at end of list */
 if (head == null)
  return 0;
 else
  /* call this method again with next node */
  length = 1 + findLengthOfListRecursion(head.getNext());
 return length;
}

/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
 int length = 0;
 /* If list is empty, return length is 0 */
if (head == null) {
 return length;
} else {
 Node current = head;
 /* Iterate list and increment length for each node */
  while (current != null) {
   length += 1;
   current = current.getNext();
  }
 }
 return length;
}

 /* Add New node at start of linked list */
private static void insertFirst(int data) {
 Node newNode = createNewNode(data);
 if (head == null) {
  head = newNode;
 } else {
  newNode.setNext(head);
  head = newNode;
 }
}

private static Node createNewNode(int data) {
 return new LengthOfLinkedlist().new Node(data);
}

class Node {

 private int data;
 private Node next; // reference(handler) for next Node.

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 public Node getNext() {
  return next;
 }

 public void setNext(Node next) {
  this.next = next;
 }

 public int getData() {
  return data;
 }
}

public static void main(String[] args) {
 /* Setup a linked list */
 insertFirst(142);
 insertFirst(135);
 insertFirst(141);
 insertFirst(141);
 insertFirst(145);
 insertFirst(148);
 insertFirst(145);

 /* Find length of linked list using recursive call */
 int length = LengthOfLinkedlist.findLengthOfListRecursion(head);
 System.out.println("length of list(recursion) : " + length);

 /* Find length of linked list using recursive call */
 int length2 = LengthOfLinkedlist.findLengthOfListIterative(head);
 System.out.println("length of list(Iterative) : " + length2);
 }
}

========Sample output========
length of list(recursion) : 7
length of list(Iterative) : 7
==========================

Some other linked list problems that use linked list iteration / length of linked list, try following questions:- 

1. Find sum of all elements of linked list.
2. Find mean of linked list, provided data is of number type.
3. Count number of odd and even numbers in the given linked list.
4.  Find middle element of  the linked list.(For even # of elements first node the two middle node is mean)
5. Check whether the given linked list is palindrome or not.

---