Program to find the size of Doubly Linked List

In this blog, we will study the problem in which we will find the size of a doubly linked list. A doubly linked list is a type of linked list in which we can traverse in both ends i.e. forward and backward as there is both pointer i.e. pointer of the previous node as well as the pointer of the next node.

Problem Statement

In this problem, we are given a doubly linked list, and we need to find the size of a doubly linked list.

Note: The linked list does not contain loop.

Problem Statement Understanding

Let’s first understand what a doubly linked list is.

In simple words, a doubly linked list can be defined as a linked data structure made up of nodes, which are sequentially linked records. Each node has three fields one data field and two link fields which are basically the pointers to the node before it and the node after it in the sequence. We can traverse through the doubly linked list in both ways as each of its node contains the address of previous as well as next node.

Now, let’s understand the problem statement with help of examples.

Suppose if we are given a doubly linked list:

and we have to output its size.

We can see that the linked list contains total of 4 nodes so our output will be 4, as the size of linked list is equal to the number of nodes in the linked list.

If the linked list is:

the size of the linked list is 6 equal to the number of the nodes.

Explanation The size of the linked list is equal to the number of nodes in the linked list.

Approach to find the size of a doubly linked list

The size of the linked list is equal to the count of the number of the nodes in the linked list.

To find the count of the nodes in the linked list:

• Initialize a counter variable to 0 and a temp pointer to the head of the linked list
• Using the temp pointer traverse the linked list until temp!=NULL and increment the counter variable by 1 for each node.

Finally when the temp==NULL the counter variable will have the size of the linked list.

Algorithm to find the size of a doubly linked list

• Initialize a variable ListSize to 0.
• Initialize a node pointer, temp = head.
• Do following while temp is not NULL
  a) temp = temp -> next
  b) ListSize++;
• Return ListSize.

Dry Run to find the size of a doubly linked list

Implementation to find the size of a doubly linked list

#include 
using namespace std;

struct llNode
{
    int data;
    struct llNode *next;
    struct llNode *prev;
};


void push(struct llNode** head_ref, int data)
{
    struct llNode* new_node = new llNode;
    new_node->data = data;
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL)
    (*head_ref)->prev = new_node ;
    (*head_ref) = new_node;
}


int SizeOfList(struct llNode *temp)
{
    int ListSize = 0;
    while(temp != NULL)
    {
        ListSize++;
        temp = temp->next;
    }
    return ListSize;
}

int main()
{
    struct llNode* head = NULL;
    push(&head, 9);
    push(&head, 7);
    push(&head, 5);
    push(&head, 3);
    cout <<"Size of the doubly linked list: "<< SizeOfList(head);
    return 0;
}

Output

Size of the doubly linked list: 5

Time Complexity of the size of a doubly linked list: O(n), where n is the number of nodes in the linked list.

In this article, we have tried to explain the most efficient algorithm for how to get the size of a doubly linked list. This problem is interesting as well as important from the interviewee’s point of view. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs

1. What is a doubly linked list used for?

A doubly linked list is used in navigation systems that require both forward and backward navigation.

2. What is the difference between singly linked lists and doubly linked lists?

A singly linked list is traversed in one direction only whereas a doubly linked list is traversed in two ways.

3. What is a memory-efficient doubly linked list?

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