Using recursion:- Below is sample code line which calculates length of list recursively(Download complete sample program).
/* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
int length = 0;
/* If list is empty or we have reached at end of list */
if (head == null)
return 0;
else
/* call this method again with next node */
length = 1 + findLengthOfListRecursion(head.getNext());
return length;
}
Using Iterative approach :- Below is sample code line which calculates length of list by traversing list (Download complete sample program).
/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
int length = 0;
/* If list is empty, return length is 0 */
if (head == null) {
return length;
} else {
Node current = head;
/* Iterate list and increment length for each node */
while (current != null) {
length += 1;
current = current.getNext();
}
}
return length;
}
Below is the complete sample program for the length calculation using recursion and iterative approach:-
public class LengthOfLinkedlist {
static Node head;
/* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
int length = 0;
/* If list is empty or we have reached at end of list */
if (head == null)
return 0;
else
/* call this method again with next node */
length = 1 + findLengthOfListRecursion(head.getNext());
return length;
}
/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
int length = 0;
/* If list is empty, return length is 0 */
if (head == null) {
return length;
} else {
Node current = head;
/* Iterate list and increment length for each node */
while (current != null) {
length += 1;
current = current.getNext();
}
}
return length;
}
/* Add New node at start of linked list */
private static void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.setNext(head);
head = newNode;
}
}
private static Node createNewNode(int data) {
return new LengthOfLinkedlist().new Node(data);
}
class Node {
private int data;
private Node next; // reference(handler) for next Node.
public Node(int data) {
this.data = data;
this.next = null;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getData() {
return data;
}
}
public static void main(String[] args) {
/* Setup a linked list */
insertFirst(142);
insertFirst(135);
insertFirst(141);
insertFirst(141);
insertFirst(145);
insertFirst(148);
insertFirst(145);
/* Find length of linked list using recursive call */
int length = LengthOfLinkedlist.findLengthOfListRecursion(head);
System.out.println("length of list(recursion) : " + length);
/* Find length of linked list using recursive call */
int length2 = LengthOfLinkedlist.findLengthOfListIterative(head);
System.out.println("length of list(Iterative) : " + length2);
}
}
length of list(recursion) : 7
length of list(Iterative) : 7
==========================
Some other linked list problems that use linked list iteration / length of linked list, try following questions:-
1. Find sum of all elements of linked list.2. Find mean of linked list, provided data is of number type.
3. Count number of odd and even numbers in the given linked list.
4. Find middle element of the linked list.(For even # of elements first node the two middle node is mean)
5. Check whether the given linked list is palindrome or not.
Hi to every single one, it’s truly a good for me to visit this web page, I love your content, they are very nice and it includes helpful Information. Check out our website Linkedlist Interview Questions for more TutorialCup. related info! I am truly pleased to read this website posts which carries lots of helpful data, thanks for providing these kinds of statistics.
ReplyDelete