Doubly Linked List in DSA – Structure, Operations & Examples

🚀 Introduction

A Doubly Linked List (DLL) is a type of linked list where each node contains:

• Pointer to the previous node
• Data
• Pointer to the next node

👉 This allows traversal in both directions (forward and backward).

---

🔹 Structure

NULL ← [Prev | Data | Next] → [Prev | Data | Next] → NULL

---

🔹 Node Representation

Each node has:

• prev → points to previous node
• data → stores value
• next → points to next node

---

🔹 Operations in Doubly Linked List

1. Traversal
2. Insertion
3. Deletion

---

🔹 1. Traversal

💡 Concept

• Forward traversal → using next
• Backward traversal → using prev

---

🧑‍💻 Example (Forward Traversal)

public function traverseForward() {
    $temp = $this->head;    while ($temp != null) {
        echo $temp->data . " ↔ ";
        $temp = $temp->next;
    }    echo "NULL";
}

---

🔹 2. Insertion

✅ Insert at Beginning

💡 Concept

• Create node
• Update next and prev pointers

---

public function insertAtBeginning($data) {
    $newNode = new Node($data);    if ($this->head != null) {
        $this->head->prev = $newNode;
        $newNode->next = $this->head;
    }    $this->head = $newNode;
}

---

✅ Insert at End

public function insertAtEnd($data) {
    $newNode = new Node($data);    if ($this->head == null) {
        $this->head = $newNode;
        return;
    }    $temp = $this->head;    while ($temp->next != null) {
        $temp = $temp->next;
    }    $temp->next = $newNode;
    $newNode->prev = $temp;
}

---

🔹 3. Deletion

✅ Delete from Beginning

public function deleteFromBeginning() {
    if ($this->head == null) return;    $this->head = $this->head->next;    if ($this->head != null) {
        $this->head->prev = null;
    }
}

---

✅ Delete from End

public function deleteFromEnd() {
    if ($this->head == null) return;    if ($this->head->next == null) {
        $this->head = null;
        return;
    }    $temp = $this->head;    while ($temp->next != null) {
        $temp = $temp->next;
    }    $temp->prev->next = null;
}

---

⚡ Time Complexity

Operation	Complexity
Traversal	O(n)
Insertion	O(1) / O(n)
Deletion	O(1) / O(n)

---

🎯 Advantages

✅ Traversal in both directions
✅ Easier deletion (no need to track previous manually)
✅ More flexible than singly linked list

---

❌ Disadvantages

❌ Extra memory for prev pointer
❌ More complex pointer handling

---

🧠 Real-World Use Cases

• Browser history (back & forward navigation)
• Undo/Redo operations
• Navigation systems

---

🧠 Interview Tips

👉 Common questions:

• Reverse a doubly linked list
• Delete a given node
• Find pairs with given sum

👉 Important:
👉 Always update both prev and next pointers

---

🏁 Conclusion

Doubly Linked Lists provide more flexibility than singly linked lists due to bidirectional traversal.

👉 They are widely used in applications requiring forward and backward navigation.