1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach 1: Iterative approach
2.1.
Steps of algorithm
2.2.
Implementation
2.2.1.
Code in Java
2.2.2.
Code in C++
2.2.3.
Complexity Analysis
3.
Approach 2: Recursive approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Code in Java
3.2.2.
Code in C++
3.2.3.
Complexity Analysis
4.
4.1.
How big is a LinkedList in Java by default?
4.2.
4.3.
4.4.
Would it be better to use iteration or recursion?
5.
Conclusion
Last Updated: Mar 27, 2024

# Length of a Linked List(Iterative and Recursive method)

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

Data elements are stored dynamically in a linked list as a linear data structure.

A node represents those data elements, and a link or pointer connects them.

There are two fields in each node:

1. The data is contained in a linked list.
2. An address for the node after it.

Fig: 1.1

The size of a linked list can be modified according to the requirements. There is a null in the second field of the last node since it does not point to anything.

Fig: 1.2

Recommended Topic, Floyds Algorithm

### Problem Statement

Let's move on to the main problem we need to solve in this blog: we're given a linked list comprised of n nodes. What we need to do now is determine the length of the linked list.

### Sample Example

Input:

In Fig 1.2, we have a LinkedList Stack,

Linked List: A => B => C => D

Output:

The LinkedList in Fig. 1.2 has a length of 4 because it has four linked nodes.

## Approach 1: Iterative approach

Iterating continuously until a certain condition is met typically involves repeating a certain number of steps. Depending on the issue, the iterations can be large or small. All of this depends on the program we are using to iterate.

The data elements in the linked list below are in the order A => B => C => D.

Fig 1.3

As you can see, the currentPointer is at Node A, so when it enters the while loop, it will check if the current node is null. If not, the length gets increased by one, while the currentPoniter.next points to B. If the current node is not null, the loop will continue to work, and the length will increase by one until the current node is null.

### Steps of algorithm

Step-1: Initialize the pointer's current position as "currentPointer = head".

Step-2: Initialize the length of nodes as "length=0".

Step-3: Enter the while loop and perform the following operations if the current node is not empty:

length = length+1

currentPointer= currentPointer.next

Step-4: Return the length.

### Implementation

Java program to calculate the length of the given Linked List.

#### Code in Java

``````// Node for LinkedList
class Node
{
String data;
Node next;
Node(String d){
data = d;
next = null;
}
}
// class for creating a LinkedList
{
{
// adding the data to new_node
Node new_node = new Node(val);
// initializing the next node as head node
// Now head node is equal to the new_node
}
public static void main(String[] args)
{
System.out.println("Length of the LinkedList: " +  element.getLength());
}
// returns the length of the Linked List
public int getLength()
{
int length = 0;
while (currentPointer != null)
{
length++;
currentPointer = currentPointer.next;
}
return length;
}
}``````

C++ program to calculate the length of the given Linked List.

#### Code in C++

``````#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
const char* data;
Node* next;
};
// class for creating a LinkedList
{
// allocating new_node
Node* new_node =new Node();
new_node->data = val;
}
// returns the length of the Linked List
{
int length = 0;
while (currentPointer != NULL)
{
length++;
currentPointer = currentPointer->next;
}
return length;
}
// Main function
int main()
{
// Printing the length of the LinkedList by calling the getLength()
return 0;
}  ``````

Output:

``Length of the LinkedList: 4``

#### Complexity Analysis

Time Complexity: The linked list is traversed once, so the time complexity is O(n).

Space Complexity: We're not using any extra space, so space complexity is O(1).

## Approach 2: Recursive approach

A recursive algorithm calls itself bypassing its return value as a parameter to the next algorithm. The parameter is input, while the return value is output.

The data elements in the linked list below are in the order A => B => C => D.

Fig 1.4

As you can see, the currentPointer is at the head of Node A, so as it enters the while loop, it will check to see if the current node is null. If not, one will be added to the block containing the getLength() element, so the loop will continue until the next node is null. As a result, if the next node is null, it will go backward, adding 1 to every value.

### Algorithm

Step-1: For the base case, In getLength(head), if the head == NULL, return 0.

Step-2: Else recursively call the same Function for CurrentPointer. Next, add 1 to its result.

Step-3: Return the length.

### Implementation

Java program to calculate the length of the given Linked List.

#### Code in Java

``````// Node for LinkedList
class Node
{
String data;
Node next;
Node(String d){
data = d;
next = null;
}
}
{
{
// adding the data to new_node
Node new_node = new Node(val);
// initializing the next node as head node
// Now head node is equal to the new_node
}
public static void main(String[] args)
{
//  Printing the length of LinkedList by calling the getLength()
System.out.println("Length of the LinkedList: " +  element.getLength());
}
// function to call the getCount()
public int getLength (){
}
// function to call the getCount()
private int getCount(Node currentPointer) {
if (currentPointer == null) {
return 0;
}
return 1 + getCount(currentPointer.next);
}
}``````

C++ program to calculate the length of the given Linked List.

#### Code in C++

``````#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
const char* data;
Node* next;
};
// class for creating a LinkedList
{
// allocating new_node
Node* new_node =new Node();
new_node->data = val;
}
// Recursive function to calculate the length
{
// Base case
return 0;
else
}
// Main function
int main()
{
// Printing the length of the LinkedList by calling the getLength()
return 0;
}  ``````

Output:

``Length of the LinkedList: 4``

#### Complexity Analysis

Time Complexity: The traversal of the linked list is O(n) since the list is traversed only once.

Space Complexity: Due to the recursive nature of the function call stack, the space complexity is O(n).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

#### How big is a LinkedList in Java by default?

LinkedList only constructs an empty list without any initial capacity while generating a list with ten capacities by default.

A LinkedList is a linear data structure that contains objects at each node. LinkedList is not a contiguous memory structure, unlike Arrays. LinkedList elements are linked with pointers.

There is a type of linked list called a singly linked list, and this type of list is unidirectional; that is, it can only be traversed from head to tail.

#### Would it be better to use iteration or recursion?

It can sometimes be more challenging to determine the time complexity of recursive code than iterative code. In comparison to iteration, recursion has a lot of overhead. Due to the fact that all function calls must be stored on a stack, it is typically much slower. There is no such overhead with iteration.

## Conclusion

In this blog, we have seen how to find the length of a LinkedList using iterative and Recursive methods.