.png)
Length of a Singly Linked List
Problem Statement
Given the head pointer of a singly linked list, determine the total number of nodes present in the linked list.
You are required to return an integer representing the length of the list.
The length of a linked list is defined as the total number of nodes that can be reached by starting from the head node and following the next references until a null reference is encountered.
Before Solving: What Is a Linked List?
A singly linked list is a linear data structure consisting of nodes. Each node contains:
- Data — the value stored in the node.
- A reference (pointer) to the next node in the sequence.
Unlike arrays:
- Linked lists are not stored in contiguous memory.
- Each node can exist anywhere in memory.
- Traversal is sequential.
- There is no direct index-based access.
Structure of a Node:
Data | Next Pointer
Example Linked List:
Head
↓
[10 | * ] → [20 | * ] → [30 | NULL]
This list contains 3 nodes.
What Does “Length” Mean Here?
The length is simply the number of nodes in the list.
It is important to understand that:
- Length is NOT memory size.
- Length is NOT the number of bytes.
- Length is NOT the number of links.
- Length is the count of nodes.
If the list is empty:
Head = NULL
Length = 0
Observational Thinking Before Coding
Before writing code, we must think logically.
To count nodes:
- We must visit each node exactly once.
- Since there is no indexing, we must traverse sequentially.
- We need a variable that keeps track of how many nodes we have visited.
Key Insight:
Traversal is mandatory. There is no shortcut.
Types of Approaches
There are two fundamental ways to solve this:
- Iterative Approach
- Recursive Approach
APPROACH 1: ITERATIVE METHOD
Conceptual Understanding
In a singly linked list, each node contains:
- Data
- Pointer to the next node
To calculate the length:
- Start at the head.
- Visit each node.
- Count every node visited.
- Stop when you reach NULL.
Since linked lists do not support indexing, traversal is mandatory.
Algorithm (Step-by-Step)
- If head is NULL → return 0.
- Initialize counter = 0.
- Set temp = head.
- While temp != NULL:
- Increment counter
- Move temp = temp->next
- Return counter.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
#include
#include
struct Node {
int data;
struct Node* next;
};
int lengthIterative(struct Node* head) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
printf("Length (Iterative): %d\n", lengthIterative(head));
return 0;
}
Output
Length (Iterative): 3
C++ Implementation
#include
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int lengthIterative(Node* head) {
int count = 0;
Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Length (Iterative): " << lengthIterative(head) << endl;
return 0;
}
Output
Length (Iterative): 3
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static int lengthIterative(Node head) {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.println("Length (Iterative): " + lengthIterative(head));
}
}
Output
Length (Iterative): 3
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def length_iterative(head):
count = 0
temp = head
while temp is not None:
count += 1
temp = temp.next
return count
# Creating linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Length (Iterative):", length_iterative(head))
Output
Length (Iterative): 3
APPROACH 2: RECURSIVE METHOD
Conceptual Understanding
The length of the list starting at head is:
1 + length of list starting at head->next
Until head becomes NULL.
Recursive Formula
Base Case:
If head == NULL → return 0
Recursive Case:
Return 1 + length(head->next)
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(n) (due to recursion stack)
C Implementation
#include
#include
struct Node {
int data;
struct Node* next;
};
int lengthRecursive(struct Node* head) {
if (head == NULL)
return 0;
return 1 + lengthRecursive(head->next);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 5;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 15;
head->next->next = NULL;
printf("Length (Recursive): %d\n", lengthRecursive(head));
return 0;
}
Output
Length (Recursive): 2
C++ Implementation
#include
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int lengthRecursive(Node* head) {
if (head == NULL)
return 0;
return 1 + lengthRecursive(head->next);
}
int main() {
Node* head = new Node(5);
head->next = new Node(15);
cout << "Length (Recursive): " << lengthRecursive(head) << endl;
return 0;
}
Output
Length (Recursive): 2
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static int lengthRecursive(Node head) {
if (head == null)
return 0;
return 1 + lengthRecursive(head.next);
}
public static void main(String[] args) {
Node head = new Node(5);
head.next = new Node(15);
System.out.println("Length (Recursive): " + lengthRecursive(head));
}
}
Output
Length (Recursive): 2
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def length_recursive(head):
if head is None:
return 0
return 1 + length_recursive(head.next)
head = Node(5)
head.next = Node(15)
print("Length (Recursive):", length_recursive(head))
Output
Length (Recursive): 2
Next problem in the series:
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
