Doubly Linked List – Get Length Operation

Linked Lists

Contents

VisualizationIntroExamplePseudocodeExamplesTimeSpace

Visualization Player

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...

Linked Lists❯

  1. 1Singly Linked List Introduction
  2. 2Singly Linked List – Create Operation
  3. 3Singly Linked List – Insert Operation
  4. 4Singly Linked List – Delete Operation
  5. 5Singly Linked List – Traversal Operation
  6. 6Singly Linked List – Search Operation
  7. 7Singly Linked List – Get Length Operation
  8. 8Singly Linked List – Reverse Operation
  9. 9Doubly Linked List Introduction
  10. 10Doubly Linked List – Create Operation
  11. 11Doubly Linked List – Insert Operation
  12. 12Doubly Linked List – Delete Operation
  13. 13Doubly Linked List – Traversal Operation
  14. 14Doubly Linked List – Search Operation
  15. 15Doubly Linked List – Get Length Operation
  16. 16Doubly Linked List – Reverse Operation