How to find length of a linked list in iterative and recursive manners?

As we have already established that Linked Lists are data structures where each element is linked to the other and this linking makes it possible to trace through the data structure. So how would you find the length of a singly linked list? You can do it in two ways. Firstly by iterating through the data structure till the last element. And the second option is to do this recursively since each element has a consistent relationship with the next one. Following are the examples of both the approaches

Our Linked List will be made of Node Objects which looks something like this

class Node {
 int value;
 Node next;

 public boolean add(Node n) {
  if (n == this) { //To prevent cyclic linked list
   return false;
  }
  Node node = this;
  while (node.next != null && node.next != this) {
   node = node.next;
  }
  if (node.next == null) {
   node.next = n;
   return true;
  }
  return false;
 }

 public Node(int x) {
  value = x;
 }
}

1. For the first approach the we will be iterating through the Linked list till we reach the last element. Sample code below

private static int getLength(Node node) {
 Node temp = null;
 int length = 0;
 if (node != null) {
  temp = node;
  length++;
  while (temp.next != null) {
   length++;
   temp = temp.next;
  }
  return length;
 }
 return 0;
}

2. For the second approach we will send the node object to the recursive method. In case the node is null the method will terminate returning 0 otherwise it will add 1 to the result of the length of the list starting from the next element. Sample code below

private static int getLengthRecursive(Node node) {
 if (node == null) {
  return 0;
 }
 return 1 + getLengthRecursive(node.next);
}

Now we need a testing method.

public class LinkedListUtil {

 public static void main(String[] args) {
  Node linkedList = new Node(1);
  linkedList.add(new Node(2));
  linkedList.add(new Node(3));
  linkedList.add(new Node(4));
  System.out.println("The length of the linked list is " +
   getLength(linkedList));
   System.out.println("The length of the linked list with 
   recursive solution is " + getLengthRecursive(linkedList));
  }
 }

The output is :

The length of the linked list is 4
The length of the linked list with recursive solution is 4

So we can see that the recursive solution is much cleaner and more extensible than the iterative one which no doubt is much easier to implement in this case.

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself