Doubly Linked List – Traversal Operation

Traversal Operation in Doubly Linked List

Traversal in a doubly linked list means visiting each node in the list, either in the forward direction using the next pointer or in the backward direction using the prev pointer.

This operation is useful when displaying list elements, performing calculations, or searching in either direction.

Visual Example

Suppose we have the following doubly linked list:

Detailed Step-by-Step Forward Traversal

• Initialize a pointer: Create a pointer variable named current and assign it to the head of the list. This means current now points to the first node which has value 5.
• Step 1:
  • current points to node with value 5.
  • Visit this node (e.g., print the value).
  • Move to the next node: current = current.next.
• Step 2:
  • current points to node with value 15.
  • Process the data — e.g., print 15.
  • Move to next: current = current.next.
• Step 3:
  • current points to node with value 25.
  • Process the data — e.g., print 25.
  • Move to next: current = current.next.
• Step 4:
  • current points to node with value 35.
  • Process the data — e.g., print 35.
  • Move to next: current = current.next → null.
• End of traversal:
  • current is now null, which means we’ve reached the end of the list.
  • Forward traversal complete.

This traversal walks through each node by following the next pointers until the end of the doubly linked list is reached.

Complete Pseudocode: Traverse a Doubly Linked List

This guide demonstrates how to traverse a doubly linked list in both directions using two separate functions.

Forward Traversal

We use the next pointer to move from the head to the tail.

function traverseForward(head):
  curr = head
  while curr is not null:
      print(curr.value)
      curr = curr.next

Step-by-step Explanation:

function traverseForward(head):
  curr = head

Explanation: We define a forward traversal function that starts from the head of the list and uses the next pointer to visit each node.

  while curr is not null:
      print(curr.value)
      curr = curr.next

Explanation: We print each node’s value as we move forward. The loop ends when curr becomes null.

---

Backward Traversal

We use the prev pointer to move from the tail to the head.

function traverseBackward(tail):
  curr = tail
  while curr is not null:
      print(curr.value)
      curr = curr.prev

Step-by-step Explanation:

function traverseBackward(tail):
  curr = tail

Explanation: For backward traversal, we start from the tail and move in reverse using the prev pointer.

  while curr is not null:
      print(curr.value)
      curr = curr.prev

Explanation: Just like forward traversal, but we now go backward. This highlights the bidirectional capability of doubly linked lists.

Doubly Linked List Traversal Operation Examples

The following examples demonstrate how to traverse a doubly linked list in both forward (using next) and backward (using prev) directions.

Linked List	Forward / Backward Traversal	Explanation
[10, 20, 30]	10 → 20 → 30 30 ← 20 ← 10	Start at the head (10) and follow next pointers to reach the end, then traverse back using prev pointers.
[5]	5 5	Only one node. Forward and backward traversal both point to the same node.
[]	(empty) (empty)	Empty list. No traversal possible in either direction.
[7, 14, 21, 28]	7 → 14 → 21 → 28 28 ← 21 ← 14 ← 7	Traverse forward through next pointers and then backward using prev pointers, maintaining correct node order.

Time Complexity of Doubly Linked List Traversal Operation

Traversal Case	Time Complexity	Explanation
Traverse Entire List (Forward)	O(n)	We start from the head and visit each node using the next pointer until we reach the end.
Traverse Entire List (Backward)	O(n)	We start from the tail and move backward using the prev pointer until we reach the head.
Access Node at Index i	O(i)	We traverse from head (or tail) and move i steps. There is no random access.
Search for Value	O(n)	In the worst case, we may need to scan all nodes either forward or backward to find the target value.

Space Complexity of Doubly Linked List Traversal Operation

Traversal Case	Space Complexity	Explanation
Forward Iterative Traversal	O(1)	Only one pointer is used to move through the list in the forward direction. No additional memory is required.
Backward Iterative Traversal	O(1)	Traversal starts from the tail and moves backward using prev pointers, still using constant space.
Recursive Traversal	O(n)	Each recursive call adds a new frame to the call stack. This grows linearly with the number of nodes.

Key Takeaways – Doubly Linked List Traversal

• Doubly linked lists support traversal in both forward and backward directions using next and prev pointers.
• Iterative traversal is space-efficient, requiring only a single pointer variable regardless of direction.
• Recursive traversal is elegant but uses O(n) space due to the call stack, where n is the number of nodes.
• Traversing from head to tail is useful for operations like printing or searching, while tail to head traversal is ideal for backtracking or reverse-order tasks.
• Always ensure to check for null pointers during traversal to avoid runtime errors.