.png)
Size of Doubly Linked List
Understanding how to calculate the size of a Doubly Linked List is a foundational operation in data structures. Many higher-level operations such as insertion at position, deletion by index, validation of bounds, and traversal optimizations depend on knowing the total number of nodes present in the list.
This article explains the problem in depth, discusses multiple approaches, analyzes edge cases, and provides complete implementations in C, C++, Java, and Python with outputs included.
What Is a Doubly Linked List
A Doubly Linked List is a linear data structure in which each node contains:
- Data
- A pointer to the next node
- A pointer to the previous node
Structure of a node:
prev <-> data <-> next
Unlike a Singly Linked List, traversal can happen in both forward and backward directions.
Problem Statement
Given the head of a Doubly Linked List, determine the total number of nodes present in the list.
Return 0 if the list is empty.
Understanding the Size Operation
The size of a Doubly Linked List refers to the total count of nodes starting from the head node until the last node where next = NULL.
Important clarification:
Even though the list has two pointers per node (prev and next), counting is typically done using forward traversal from head to tail.
Edge Cases to Consider
Empty list
Single node list
Multiple nodes
Very large list
If head is NULL, size must be 0.
Approach 1: Iterative Forward Traversal
Idea
Traverse from head to the last node using the next pointer and increment a counter for each node visited.
Algorithm
If head is NULL
Return 0
Initialize count = 0
Set temp = head
While temp is not NULL
Increment count
Move temp = temp->next
Return count
Time Complexity
O(n)
Space Complexity
O(1)
Dry Run Example
List:
NULL <- 10 <-> 20 <-> 30 -> NULL
Traversal:
| Step | temp->data | count |
|---|---|---|
| 1 | 10 | 1 |
| 2 | 20 | 2 |
| 3 | 30 | 3 |
Final Answer: 3
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
int size(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));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->prev = NULL;
head->next = second;
second->data = 20;
second->prev = head;
second->next = third;
third->data = 30;
third->prev = second;
third->next = NULL;
printf("Size of Doubly Linked List: %d\n", size(head));
return 0;
}
Output
Size of Doubly Linked List: 3
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) {
data = val;
prev = NULL;
next = NULL;
}
};
int size(Node* head) {
int count = 0;
Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
int main() {
Node* head = new Node(10);
Node* second = new Node(20);
Node* third = new Node(30);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
cout << "Size of Doubly Linked List: " << size(head) << endl;
return 0;
}Output
Size of Doubly Linked List: 3
Java Implementation
class Node {
int data;
Node prev;
Node next;
Node(int d) {
data = d;
prev = null;
next = null;
}
}
public class Main {
static int size(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);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
System.out.println("Size of Doubly Linked List: " + size(head));
}
}
Output
Size of Doubly Linked List: 3
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def size(head):
count = 0
temp = head
while temp is not None:
count += 1
temp = temp.next
return count
head = Node(10)
second = Node(20)
third = Node(30)
head.next = second
second.prev = head
second.next = third
third.prev = second
print("Size of Doubly Linked List:", size(head))
Output
Size of Doubly Linked List: 3
Approach 2: Recursive Traversal
Idea
Count current node and recursively count the rest of the list using next pointer.
Algorithm
If head is NULL
Return 0
Return 1 + size(head->next)
Time Complexity
O(n)
Space Complexity
O(n) due to recursion stack
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
int sizeRecursive(struct Node* head) {
if (head == NULL)
return 0;
return 1 + sizeRecursive(head->next);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->prev = NULL;
head->next = second;
second->data = 20;
second->prev = head;
second->next = third;
third->data = 30;
third->prev = second;
third->next = NULL;
printf("Size of Doubly Linked List (Recursive): %d\n", sizeRecursive(head));
return 0;
}Output
Size of Doubly Linked List (Recursive): 3
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) {
data = val;
prev = NULL;
next = NULL;
}
};
int sizeRecursive(Node* head) {
if (head == NULL)
return 0;
return 1 + sizeRecursive(head->next);
}
int main() {
Node* head = new Node(10);
Node* second = new Node(20);
Node* third = new Node(30);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
cout << "Size of Doubly Linked List (Recursive): "
<< sizeRecursive(head) << endl;
return 0;
}Output
Size of Doubly Linked List (Recursive): 3
Java Implementation
static int sizeRecursive(Node head) {
if (head == null)
return 0;
return 1 + sizeRecursive(head.next);
}
public static void main(String[] args) {
Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
System.out.println("Size of Doubly Linked List (Recursive): "
+ sizeRecursive(head));
}
Output
Size of Doubly Linked List (Recursive): 3
Python Implementation
def size_recursive(head):
if head is None:
return 0
return 1 + size_recursive(head.next)
print("Size of Doubly Linked List (Recursive):",
size_recursive(head))
Output
Size of Doubly Linked List (Recursive): 3
Iterative vs Recursive Comparison
| Feature | Iterative | Recursive |
|---|---|---|
| Time Complexity | O(n) | O(n) |
| Extra Space | O(1) | O(n) |
| Stack Usage | No | Yes |
| Recommended | Yes | For learning recursion |
Important Observations
Even though it is a Doubly Linked List, we do not need to use the prev pointer for counting. Forward traversal is sufficient.
If maintaining size is required frequently, some implementations store size as a variable inside the list class to make retrieval O(1).
This completes the detailed explanation of Size of Doubly Linked List.
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)
