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 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) {
LinkedList list = new
LinkedList();
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
No comments:
Post a Comment