Doubly Linked List – Get Length Operation

Linked Lists

Contents

IntroExamplePseudocodeExamplesTimeSpace

Get Length Operation in Doubly Linked List

Calculating the number of nodes in a doubly linked list using forward traversal.

To get the length of a doubly linked list, we start from the head node and traverse forward using the next pointers, counting each node until we reach null.

Although a doubly linked list supports backward traversal as well, the length is typically calculated by moving forward through the list just like in singly linked lists.

Visual Example

Suppose we have a doubly linked list with the following values:

We want to calculate the length of the doubly linked list by traversing it node by node from head to tail and counting the number of nodes.

Step-by-Step Length Calculation

  1. Start at the head node (value 5), count = 1.
  2. Move to node with value 15, count = 2.
  3. Move to node with value 25, count = 3.
  4. Move to node with value 35, count = 4.
  5. Move to node with value 45, count = 5.

We reach the end of the list. Total count = 5. This is the length of the doubly linked list.

Complete Pseudocode: Get Length of Doubly Linked List

This pseudocode shows how to calculate the length of a doubly linked list by traversing it from head to tail and counting each node.

function getLength(head):
    curr = head
    length = 0

    while curr != null:
        length += 1
        curr = curr.next

    return length

Let’s break down the logic step by step for better understanding.

function getLength(head):
    curr = head
    length = 0

Explanation: We define the function and initialize two variables — curr to traverse the list, and length to keep count of the nodes.

    while curr != null:
        length += 1
        curr = curr.next

Explanation: We walk through the list node by node, incrementing length each time, and moving curr forward using curr.next.

    return length

Explanation: After the traversal is complete, we return the total count which represents the length of the doubly linked list.

Doubly Linked List – Get Length Operation Examples

The following examples demonstrate how to calculate the length of a doubly linked list by traversing from head to tail.

Initial List Length Explanation
[10, 20, 30, 40, 50] 5 Start from the head and follow the next pointers, counting nodes until reaching null.
[5, 15, 25] 3 Traverse forward using next. There are three nodes in total.
[1] 1 Only one node exists. Count is 1.
[] 0 Empty list. Head is null, so the length is 0.

Time Complexity of Doubly Linked List Get Length Operation

Length Calculation Case Time Complexity Explanation
Empty List O(1) We check if the head pointer is null and return 0 without traversal.
Non-Empty List O(n) We traverse the list starting from head, following next pointers, and increment a counter until we reach null.

Space Complexity of Doubly Linked List Get Length Operation

Length Calculation Space Complexity Explanation
Get Length O(1) Only a single counter and a pointer are used to traverse from head to tail. No extra space is needed, regardless of the number of nodes.

Key Takeaways

  • The length of a doubly linked list is determined by traversing from the head node to the tail.
  • We maintain a simple count variable to keep track of the number of nodes visited.
  • Each node is visited exactly once, resulting in a time complexity of O(n).
  • No extra memory is needed apart from a pointer and counter, so the space complexity is O(1).
  • Traversing from tail to head can also be done, but it doesn't affect the length calculation.
  • This operation is read-only — the structure of the list remains unchanged.

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...