What is a Linked List?
- A linked list is a linear data structure used for storing collections of data
- Successive elements are connected by pointers
- The last element points to NULL
- Each element is a separate object and is called a Node
- Each node in a linked list comprises of two parts
- Data
- Reference to Next Node
LinkedList Node
Linked List
How to Find the Length of a Linked List?
There are two ways to find the length of a linked list:
- Iterative Approach
- Recursive Approach
Length of Linked List using Iterative Approach
We will use the Linked list traversal to find the length of a linked list.
- Head Points to the First Node of The List.
- Initialize the count variable with value 0
- Initialize the temp variable with Head
- As we access each Node, the value of count variable is increased by 1.
- Stop The process when we reach null.
- Do not change the head reference.
Iterative Approach for LinkedList Length
Code in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
package com.journaldev.ds; public class MyLinkedList { public class Node { int data; Node next; } public Node head; public Node tail; public int size; public int getFirst() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.head.data; } public int getLast() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.tail.data; } public void display() { Node temp = this.head; while (temp != null) { System.out.println(temp.data + " "); temp = temp.next; } } public void addFirst(int item) { Node nn = new Node(); nn.data = item; if (this.size == 0) { this.head = nn; this.tail = nn; this.size = this.size + 1; } else { nn.next = this.head; this.head = nn; this.size = this.size + 1; } } public int length() { Node temp = this.head; int count = 0; while (temp != null) { count++; temp = temp.next; } return count; } public static void main(String[] args) { MyLinkedList ll = new MyLinkedList(); ll.addFirst(10); ll.addFirst(20); ll.addFirst(30); ll.addFirst(40); ll.addFirst(50); System.out.println("Length of Linked List is " + ll.length()); } } |
Code in C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <stdio.h> #include <stdlib.h> /* A structure of linked list node */ struct node { int data; struct node *next; } *head; void initialize(){ head = NULL; } /* Inserts a node in front of a singly linked list. */ void insert(int num) { /* Create a new Linked List node */ struct node* newNode = (struct node*) malloc(sizeof(struct node)); newNode->data = num; /* Next pointer of new node will point to head node of linked list */ newNode->next = head; /* make new node as the new head of linked list */ head = newNode; printf("Inserted Element : %dn", num); } int getLength(struct node *head){ int length =0; while(head != NULL){ head = head->next; length++; } return length; } /* Prints a linked list from head node till the tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { initialize(); /* Creating a linked List*/ insert(8); insert(3); insert(2); insert(7); insert(9); printf("nLinked Listn"); printLinkedList(head); printf("nLinked List Length : %d", getLength(head)); return 0; } |
Output
Iterative Solution Output
Length of Linked List using Recursive Solution
Base Case:
- Last Node points to Null value
- Return 0
Recursive Case:
- At each step update the Value of Current Node to the Next Node
- Call= 1+fun(curr.next)
Recursive Solution
Example:
There are 3 elements in the linked list: LL1, LL2, and LL3.
We will Observe What happens in the Memory Stack when the Recursive Call is made.
MEMORY STACK:
Memory Stack
The main function calls LL1, LL1 calls LL2, LL2 calls LL3, LL3 calls null value.
As Null value is reached, we return from here.
0 is returned to LL3, LL3 returns 1 to LL2, LL2 returns 2 to LL1.
LL1 finally returns 3 to the main function.
Code in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
package com.journaldev.ds; public class MyLinkedList { public class Node { int data; Node next; } public Node head; public Node tail; public int size; public int getfirst() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.head.data; } public int RemoveFirst() throws Exception { if (this.size == 0) { throw new Exception("LL is empty"); } Node temp = this.head; if (this.size == 1) { this.head = null; this.tail = null; size = 0; } else { this.head = this.head.next; this.size--; } return temp.data; } public void addFirst(int item) { Node nn = new Node(); nn.data = item; if (this.size == 0) { this.head = nn; this.tail = nn; this.size = this.size + 1; } else { nn.next = this.head; this.head = nn; this.size = this.size + 1; } } public int lengthUsingRecursiveApproach (){ return lengthUsingRecursiveApproach(this.head); } private int lengthUsingRecursiveApproach(Node curr) { // TODO Auto-generated method stub if (curr == null) { return 0; } return 1 + lengthUsingRecursiveApproach (curr.next); } public static void main(String[] args) { MyLinkedList ll = new MyLinkedList(); // insert elements into the Linked List ll.addFirst(10); ll.addFirst(20); ll.addFirst(30); ll.addFirst(40); ll.addFirst(50); // Length of List System.out.println("Recursive Approach length " + ll.lengthUsingRecursiveApproach(ll.head)); } } |
Code in C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); (*head_ref) = new_node; } int getCount(struct Node* head) { // Base case if (head == NULL) return 0; return 1 + getCount(head->next); } int main() { struct Node* head = NULL; push(&head, 1); push(&head, 3); push(&head, 1); push(&head, 2); push(&head, 1); printf("count of nodes is %d", getCount(head)); return 0; } |
Output
Recursive Solution Output
Time Complexity
O(N) in both the recursive and iterative solution, as all we need, is a single traversal to know the length.