Find Length of a Linked List (Iterative and Recursive)

Function to find the length of Linked list.

Recursive Solution:

int getLengthRecur (start)

1) if start is NULL, return 0.

2) else return 1 + getLengthRecur (start->next)

Iterative solution:

1) Initialize count as 0

2) Initialize a node pointer, current = start.

3) Repeat while current is not NULL

     a) current = current -> next

     b) count++;

4) Return count

Java code for both approaches:

/** Linked list Node*/

class Node {

   int data;

   Node next;

   Node(int d)  {

      data = d;

      next = null;

   }

}

/**

 * @author rajesh.kumar

 */

class LinkedList {

   Node start;

   /**

    * Inserts a new Node at front of the list.

    * @param value

    */

   public voidadd(int value) {

      /* 1 & 2: Allocate the Node & Put in the data*/

      Node nNode = newNode(value);

      /* 3. Make next of new Node as head */

      nNode.next = start;

      /* 4. Move the head to point to new Node */

      start = nNode;

   }

   /** Returns count of nodes in linked list */

   public intgetLengthIter() {

      Node temp = start;

      int count = 0;

      while (temp != null) {

         count++;

         temp = temp.next;

      }

      return count;

   }

   private intgetLengthRecur() {

      Node node = start;

      if(node!=null) {

         return1+getLengthRecur(node.next);  

      } else {

         return 0;

      }

   }

   private intgetLengthRecur(Node node) {

      if(node!=null) {

         return1+getLengthRecur(node.next);

      } else {

         return 0;

      }

   }

   public static void main(String[] args) {

      LinkedList list = newLinkedList();

      list.add(1);

      list.add(2);

      list.add(3);

      list.add(4);

      list.add(5);

      System.out.println("Ietrative Length #" + list.getLengthIter());

      System.out.println("Recursive Length #" + list.getLengthRecur());

   }

}

Output:

     Ietrative Length #5

     Recursive Length #5