## Sunday, 22 May 2016

### 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
*/
Node start;

/**
* Inserts a new Node at front of the list.
* @param value
*/
public void add(int value) {
/* 1 & 2: Allocate the Node & Put in the data*/
Node nNode = new Node(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 int getLengthIter() {
Node temp = start;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}

private int getLengthRecur() {
Node node = start;
if(node!=null) {
return 1+getLengthRecur(node.next);
} else {
return 0;
}
}

private int getLengthRecur(Node node) {
if(node!=null) {
return 1+getLengthRecur(node.next);
} else {
return 0;
}
}

public static void main(String[] args) {

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

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

Output:
Ietrative Length #5
Recursive Length #5