Program to find the size of Doubly Linked List

Introduction

The linked list data structure is one of the most essential concepts to learn while preparing for interviews. Proper understanding of concepts based on Linked Lists can give you an edge in a coding interview.

Problem Statement

In this problem, we are given a doubly linked list, and we are required to find its size.

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

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

  • 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


Code Implementation

#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: 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 finding out the size of a doubly linked list. This problem is interesting as well as important from the interview’s point of view. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Python Program to find the middle of a linked list using only one traversal
Next post Advantages and Disadvantages of Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *