You can read about calculating length of a linked list by iterative method here.
In recursion, the iterative loop or explicit loop is replaced by recursive function calls.
In recursive calls, a stack is used to store values calculated during the recursion. And when stack unfolds, the recursion calls are replaced by those values.
Let us look at the code which is going to calculate the length
return 1 + length(head .next);
Look at the part – 1 and length(head .next) .
For current node we hard code 1, and then we move to the next node.
Let us take an example for a linked list :-
A -> B -> C -> D -> null => 1 + 1 + 1 + 1 + 0
Right after linked list, I have replaced the nodes with the 1.
And zero at the end is for null value, because null means, there is no node.
I will provide two implementations. One using an if-statement and other using ternary operator.
With If-Statement
private static int length(Node head) {
if(head == null) return 0;
return 1 + length(head .next);
}
Using ternary operator
private static int lengthWithoutIf (Node head) {
return head == null ? 0 : 1 + lengthWithoutIf(head .next);
}
You can use which ever way you like it.
Complete Code :-
public class LinkedListLengthRecursive {
private static class Node {
int data;
Node next;
Node prev;
Node(final int data) {
this .data = data;
}
}
public static void main(String ... args) {
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
a .next = b;
b .next = c;
c .next = d;
System.out.println("Length is :- " + length(a));
System .out .println("Length is :- " + lengthWithoutIf(a));
}
//Method 1
private static int length(Node head) {
if(head == null) return 0;
return 1 + length(head .next);
}
private static int lengthWithoutIf (Node head) {
return head == null ? 0 : 1 + lengthWithoutIf(head .next);
}
}