To find length of linked list is one of warm-up interview question. Idea here is to write sample program to find length of list using recursion, iterative way of finding is not a big deal(iterate linked list and maintains a counter & increment for each node).A better understanding of recursion is important to solve various Linked list problems and finding length is list one of the easy problem which gives an overview of recursion.

Explanation:- For each recursive call, null check for head is performed, if head is null it indicates - we have reached at end of the list and it returns 0. Otherwise, else block is executed and length is incremented by 1 and recursive call is made for next node.

Explanation:- Iterate the list until we reaches at end of list and increment length for each node. Once we reach at end of list, we have length of list.

Below is the complete sample program for the length calculation using recursion and iterative approach:-

========Sample output========

length of list(recursion) : 7

length of list(Iterative) : 7

==========================

1. Find

2. Find

3. Count number of

4. Find

5. Check whether the given

**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

ReplyDeleteLinkedlist Interview Questionsfor 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.Mua vé tại Aivivu, tham khảo

ReplyDeletevé máy bay đi Mỹ hạng thương gia

giá vé máy bay đi từ mỹ về việt nam

vé máy bay từ canada về việt nam giá rẻ

bay nhật bản việt nam

Máy bay từ Hàn Quốc về Việt Nam

Vé máy bay từ Đài Loan về VN

khách sạn cách ly ở tphcm

chuyến bay chuyên gia về việt nam