✅ Searching in Doubly Linked List

---

✅ 1. Introduction

A Doubly Linked List (DLL) is a linear data structure in which each node contains:

• Data part
• Pointer to previous node (prev)
• Pointer to next node (next)

Searching in a doubly linked list means finding a given element by traversing the list node by node.

---

✅ 2. Definition of Searching

Searching in a doubly linked list is the process of locating a node that contains a specified key value.

Since a doubly linked list also does not support random access, searching is done by sequential traversal, but traversal can be done in both directions.

---

✅ 3. Concept of Searching in Doubly Linked List

Consider the following doubly linked list:

NULL ← 10 ↔ 20 ↔ 30 ↔ 40 → NULL

If we want to search 30, traversal can be:

👉 Forward direction:

10 → 20 → 30 (FOUND)

👉 Backward direction (if starting from last node):

40 → 30 (FOUND)

---

✅ 4. Methods of Searching in Doubly Linked List

Searching can be done in two ways:

1. Forward Searching (from HEAD)
2. Backward Searching (from LAST node)

---

✅ 5. Forward Searching in Doubly Linked List

✅ Steps Involved

1. Start from HEAD
2. Compare key with temp->data
3. If match found → stop
4. Else move to next node using next pointer
5. Repeat until NULL is reached

---

✅ Algorithm: Search_DLL_Forward(HEAD, KEY)

1. Start
2. If HEAD == NULL, print List is empty and Stop
3. Set temp = HEAD
4. Set pos = 1
5. While temp != NULL
   • If temp->data == KEY
     • Print Element found at position pos
     • Stop
   • Else
     • temp = temp->next
     • pos = pos + 1
6. Print Element not found
7. Stop

---

✅ 6. Backward Searching in Doubly Linked List

✅ Steps Involved

1. Move to the last node of the list
2. Compare key with temp->data
3. If match found → stop
4. Else move backward using prev pointer
5. Repeat until NULL is reached

---

✅ Algorithm: Search_DLL_Backward(HEAD, KEY)

1. Start
2. If HEAD == NULL, print List is empty and Stop
3. Set temp = HEAD
4. Move temp to last node using next pointer
5. While temp != NULL
   • If temp->data == KEY
     • Print Element found
     • Stop
   • Else
     • temp = temp->prev
6. Print Element not found
7. Stop

---

✅ 7. Example

Doubly Linked List:

NULL ← 10 ↔ 20 ↔ 30 ↔ 40 → NULL

Search for 20:

• Forward search: Found at position 2
• Backward search: Found after checking 40 → 30 → 20

---

✅ 8. Time Complexity

• Best Case: O(1) (found at start or end)
• Worst Case: O(n)
• Average Case: O(n)

📌 No binary search because DLL does not support indexing.

---

✅ 9. Advantages of Searching in Doubly Linked List

✅ Benefits:

• Traversal possible in both directions
• Useful when searching from either end
• Easy to implement linear search

---

❌ 10. Limitations

• Slower than array searching
• Extra memory required for prev pointer
• Still sequential (no random access)

---

✅ Conclusion

Searching in a doubly linked list is performed using linear traversal, either forward or backward. Though it offers more flexibility than a singly linked list, the time complexity remains O(n).

---