Table of contents
1.
Introduction 
1.1.
Doubly Linked List
2.
Problem Statement
2.1.
Sample Examples 
3.
Solution Approach 
3.1.
Steps of Algorithm 
3.2.
Implementation in C++ 
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a doubly-linked list used for?
4.2.
What are the differences between a linked list and a doubly-linked list? 
4.3.
What is a memory-efficient doubly linked list?   
4.4.
What is a double-ended linked list? 
5.
Conclusion 
Last Updated: Mar 27, 2024
Easy

Find the size of Doubly Linked List

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

This article will discuss the problem of finding the length of a Doubly Linked List. Let's discuss in brief what is the doubly linked list. 

Doubly Linked List

In comparison to Single Linked List, Doubly Linked List is a version of Linked List in which navigation is available in forward and backward directions. The following are some key terms to know to grasp the notion of a doubly linked list.

  • A linked list's links can store a piece of data known as an element.
  • Each link in a linked list has a Next link that points to the next link.
  • Each link in a linked list has a Prev link that points to the previous link.
  • A Linked List comprises the connecting links to the first and last links, referred to as First and Last.

Problem Statement

The Problem states that we need to calculate the length of the doubly linked list

Sample Examples 

Input

 

Output

4 

 

Explanation

The length of the given linked list is 4. 

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Solution Approach 

The idea is very simple, we just keep on moving to the next node, and we will initialize a count variable to keep the number of nodes.     

Steps of Algorithm 

  • Initialize the variable count = 0.
  • Keep on moving to the next node until all the linked list nodes are exhausted. 
  • As we move to the next node, keep on increasing the count.  
  • Finally, the count variable contains the size, i.e., the number of nodes in the linked list. 

Implementation in C++ 

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val;
    node *next, *prev;
    node(int val)
    {
        this->val = val;
        this->next = NULL;
        this->prev = NULL;
    }
};
// inserting the node into the doubly linked list
void insert(int val, node *&head)
{
    node *newNode = new node(val);
    newNode->next = head;
    if (head != NULL)
        head->prev = newNode;
    head = newNode;
}
// function to get the length of the doubly linked list
int length(node *head)
{
    // initialising the count variable = 0
    int count = 0;
    while (head)
    {
        head = head->next;
        count++;
    }
    return count;
}
int main()
{
    // initialising the head as NULL
    node *head = NULL;
    // inserting the values into the linked list
    insert(1, head);
    insert(2, head);
    insert(3, head);
    insert(4, head);
    cout << length(head) << endl;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

 4

Complexity Analysis

Time Complexity: O(N)

We are traversing the doubly linked list only once, to calculate the number of nodes in the linked list. 

Space Complexity: O(1)

We are not using any temporary array, so therefore space complexity is O(1).  

Also read - Merge sort in linked list

Frequently Asked Questions

What is a doubly-linked list used for?

It is utilized in navigation systems that require both forward and backward navigation. It is a back and forward button that is utilized by the browser to implement backward and forward navigation of visited web pages. It's also used to depict a traditional card game deck.

What are the differences between a linked list and a doubly-linked list? 

The elements of a singly linked list can only be traversed in one direction. A doubly linked list provides for two-way traversal of elements. Because a singly linked list only stores the pointer to one node, it uses less memory. However, a doubly-linked list consumes extra memory per node (due to the two pointers).

What is a memory-efficient doubly linked list?   

When each node has only one pointer to traverse the list back and forth. 

What is a double-ended linked list? 

Each node in a double-ended linked list contains only one reference that leads to the next node. It differs from a single-ended linked list in that it has two pointers of this type ("first" and "last"), allowing someone to put elements into the list from both ends.

Conclusion 

In this article, we discussed the problem of finding the length of the doubly linked list.

We hope you understand the problem and solution properly. Now you can do more similar questions. 

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Live masterclass