- 1Singly Linked List Introduction
- 2Singly Linked List – Create Operation
- 3Singly Linked List – Insert Operation
- 4Singly Linked List – Delete Operation
- 5Singly Linked List – Traversal Operation
- 6Singly Linked List – Search Operation
- 7Singly Linked List – Get Length Operation
- 8Singly Linked List – Reverse Operation
- 9Doubly Linked List Introduction
- 10Doubly Linked List – Create Operation
- 11Doubly Linked List – Insert Operation
- 12Doubly Linked List – Delete Operation
- 13Doubly Linked List – Traversal Operation
- 14Doubly Linked List – Search Operation
- 15Doubly Linked List – Get Length Operation
- 16Doubly Linked List – Reverse Operation
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 thehead
of the list. This meanscurrent
now points to the first node which has value5
. - Step 1:
current
points to node with value5
.- Visit this node (e.g., print the value).
- Move to the next node:
current = current.next
.
- Step 2:
current
points to node with value15
.- Process the data — e.g., print
15
. - Move to next:
current = current.next
.
- Step 3:
current
points to node with value25
.- Process the data — e.g., print
25
. - Move to next:
current = current.next
.
- Step 4:
current
points to node with value35
.- Process the data — e.g., print
35
. - Move to next:
current = current.next
→null
.
- End of traversal:
current
is nownull
, 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 pseudocode demonstrates how to traverse a doubly linked list in both forward and backward directions.
function traverseForward(head):
curr = head
while curr is not null:
print(curr.value)
curr = curr.next
function traverseBackward(tail):
curr = tail
while curr is not null:
print(curr.value)
curr = curr.prev
Let’s walk through each function step by step to understand how a doubly linked list is navigated in both directions.
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
.
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
andprev
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, wheren
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.
Comments
Loading comments...