We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Find length of Doubly Linked List
Last updated:
In this article, we will learn how to find the length of a doubly linked list. Actually finding length means we will count the total number of nodes present in a doubly linked list.
To count the node, we will traverse the doubly linked list till the end node.
For Example:
As given in the diagram, there are a total 3 nodes, so we can say that the length of a doubly linked is 3.
Algorithm:
Initialize the variable count = 0
Continue to the next node until the doubly linked list nodes are exhausted.
As we move to the next node, continue to increase the count variable by 1.
Once the nodes are exhausted, return the count variable.
Example: Find the length of Doubly Linked List in Java
FindLengthOfDDL.java
// Class representing a node in a doubly linked list
class Node {
public int data; // Data stored in the node
public Node prev; // Reference to the next node in the list
public Node next; // Reference to the previous node in the list
// Constructor to initialize a new node with data
public Node(int new_data) {
data = new_data;
prev = null;
next = null;
}
}
// Java Program to calculate the length of a Doubly Linked List
public class FindLengthOfDDL {
// Function to find and print the length of Doubly Linked List
static void findLength(Node node) {
int length = 0;
while (node != null) {
length++;
node = node.next;
}
System.out.println("The Length of Doubly Linked List is: " + length);
}
public static void main(String[] args) {
// Create a doubly linked list
Node head = new Node(10);
head.next = new Node(20);
head.next.prev = head;
head.next.next = new Node(30);
head.next.next.prev = head.next;
head.next.next.next = new Node(40);
head.next.next.next.prev = head.next.next;
// Find and print the length of a Doubly Linked List
findLength(head);
}
}
Output
The Length of Doubly Linked List is: 4
Time Complexity: O(n), here n represent the total number of nodes in a doubly linked list.
Auxiliary Space: O(1)
Frequently Asked Questions (FAQ)
Q1. How do you find the length of a doubly linked list iteratively?
LengthIterative.java
static int length(Node head) {
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
It takes O(n) time and O(1) space.
Q2. How do you find the length recursively?
LengthRecursive.java
static int length(Node node) {
if (node == null) {
return 0;
}
return 1 + length(node.next);
}
This uses O(n) stack space, so it can overflow for very long lists.
Q3. How can you get the length in O(1)?
Keep a size field in the list class and update it on every insert and delete:
SizedList.java
public class SizedList {
static class Node {
int data;
Node prev, next;
Node(int data) { this.data = data; }
}
private Node head, tail;
private int size;
void addLast(int value) {
Node node = new Node(value);
if (tail == null) {
head = tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}
int size() {
return size; // O(1)
}
}
java.util.LinkedList.size() works this way.
Q4. Can you count from the tail instead of the head?
Yes. Following prev from the tail visits the same nodes and gives the same count. It is useful when you only hold a tail reference.
Q5. Write a Java method to find the middle node of a doubly linked list.
Q6. How do you check whether a doubly linked list has an even or odd length without counting?
IsEvenLength.java
static boolean isEvenLength(Node head) {
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
}
return fast == null; // null after jumping two at a time means even
}
Q7. What is the time complexity of finding the length?
Counting takes O(n) because every node is visited once. Keeping a size counter makes size()O(1) at the cost of updating the counter in every operation.
Q8. What is a common mistake when counting nodes?
Writing while (current.next != null) instead of while (current != null). That stops one node early, so the result is one less than the real length, and it throws a NullPointerException for an empty list.
Q9. Write a Java method that returns the k-th node from the end using the length.
KthFromEnd.java
static Node kthFromEnd(Node head, int k) {
int length = 0;
for (Node n = head; n != null; n = n.next) {
length++;
}
if (k < 1 || k > length) {
return null;
}
Node current = head;
for (int i = 0; i < length - k; i++) {
current = current.next;
}
return current;
}
With a tail reference, you can instead walk k - 1 steps back from the tail.
Q10. Does the length change the time complexity of other operations?
Knowing the length lets you choose the shorter direction when accessing index i: walk forward from the head if i < size / 2, otherwise walk backward from the tail. This halves the number of steps on average, but the operation is still O(n).
