- 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 – Search Operation
Search Operation in Doubly Linked List
Searching for the node with value 35 in a doubly linked list.
Searching in a doubly linked list involves traversing the list from either the head or tail, checking each node’s value until the target is found or the traversal ends.
Unlike singly linked lists, doubly linked lists support traversal in both directions using next and prev pointers, allowing more flexible and potentially faster searches depending on the position of the target.
Visual Example
Suppose we have the following doubly linked list:
We want to search for the value 35. The search begins from the head and traverses forward through each node until the value is found or the end is reached.
Step-by-Step Forward Search for 35
- Start at the head node (value
5). - Compare:
5 ≠ 35, move to the next node. - Compare:
15 ≠ 35, move to the next. - Compare:
25 ≠ 35, move to the next. - Compare:
35 == 35, target value found!
If the value is not found after reaching the end of the list, the operation returns null or an appropriate message indicating the value was not found.
Complete Pseudocode: Search Value in Doubly Linked List
This pseudocode shows how to search for a specific value in a doubly linked list by traversing from the head and returning its index if found.
curr is notnull.", "Ifcurr.valequals thetarget, returnindeximmediately.", "Else, movecurrtocurr.nextand incrementindex.", "Repeat until either a match is found or the end of the list is reached.", "Repeat until either a match is found or the end of the list is reached.", "If the loop ends and no match is found, return-1." ]'>function search(head, target): curr = head index = 0 while curr != null: if curr.val == target: return index curr = curr.next index += 1 return -1
Let’s understand each part of the code step by step.
function search(head, target):
curr = head
index = 0Explanation: We start by defining the function. curr is initialized to point to the first node, and index is used to track each node’s position as we move forward.
while curr != null:
if curr.val == target:
return indexExplanation: We traverse the list node by node. If the current node’s value matches the target, we return its position.
curr = curr.next
index += 1Explanation: If the current node is not a match, we move forward using the next pointer and increment the index.
return -1Explanation: If we reach the end of the list without finding the target value, we return -1 to indicate that it was not found.
Doubly Linked List Search Operation Examples
The following examples demonstrate how to search for a value in a doubly linked list using forward traversal (from head to tail).
| Initial List | Search Value | Result | Explanation |
|---|---|---|---|
| [10, 20, 30, 40, 50] | 30 | Found at index 2 | Traverse from head. Match found at node with value 30 (index 2). |
| [5, 15, 25, 35] | 35 | Found at index 3 | Value found at the tail node. Traversed entire list to locate it. |
| [1, 2, 3] | 10 | Not Found | Value not present. Traversed all nodes and reached tail without a match. |
| [] | 10 | Not Found | Empty list. Search operation returns immediately with no match. |
Time Complexity of Doubly Linked List Search Operation
| Search Case | Time Complexity | Explanation |
|---|---|---|
| Search for Head Node | O(1) | The value is at the head, so we return it immediately without any traversal. |
| Search for Middle Node | O(n) | We may need to traverse approximately half the list. A doubly linked list does not improve search time complexity over a singly linked list. |
| Search from Tail (Optional) | O(n) | If the list supports backward traversal, we can start from the tail if we expect the value is near the end. Still linear in time. |
| Search for Missing Node | O(n) | We traverse the entire list and conclude the value doesn't exist only after full traversal. |
Space Complexity of Doubly Linked List Search Operation
| Search Case | Space Complexity | Explanation |
|---|---|---|
| Any Search Operation (Forward or Backward) | O(1) | The search uses only a constant number of pointers (e.g., current node pointer). No additional memory is allocated based on list size. |
Key Takeaways
- Searching in a doubly linked list can be done in either direction — forward from the head or backward from the tail.
- The search operation checks each node's data one by one until the target value is found or the list ends.
- Unlike arrays, doubly linked lists do not support direct indexing, so searching is a linear-time operation.
- Using backward traversal can improve performance if the target is closer to the end of the list.
- The operation uses constant space regardless of the list size, as it only requires a pointer to traverse.
Sign in with Google
Comments
Loading comments...