Deletion in Linked List (DSA) – Delete Node at Beginning, End & Position

🚀 Introduction

Deletion in a Linked List means removing a node from the list by adjusting pointers.

👉 Unlike arrays, no shifting is required — only pointer updates.

---

🔹 Structure Reminder

[Data | Next] → [Data | Next] → NULL

---

🔹 Types of Deletion

1. Delete from Beginning
2. Delete from End
3. Delete from Specific Position

---

🔹 1. Delete from Beginning

💡 Concept

• Move head to next node
• Delete old head

---

🧾 Example

Before:

10 → 20 → 30 → NULL

After deletion:

20 → 30 → NULL

---

⚙️ Algorithm

1. Check if list is empty
2. Store current head
3. Move head to next
4. Delete old node

---

⚡ Complexity

👉 O(1)

---

🔹 2. Delete from End

💡 Concept

• Traverse to second last node
• Set its next to NULL

---

🧾 Example

Before:

10 → 20 → 30 → NULL

After deletion:

10 → 20 → NULL

---

⚙️ Algorithm

1. Traverse till second last node
2. Set temp.next = NULL

---

⚡ Complexity

👉 O(n)

---

🔹 3. Delete from Specific Position

💡 Concept

• Traverse to previous node
• Skip the node to delete

---

🧾 Example

Before:

10 → 20 → 30 → 40 → NULL

Delete position 3:

After:

10 → 20 → 40 → NULL

---

⚙️ Algorithm

1. Traverse to position – 1
2. Store node to delete
3. Link previous node to next node

---

⚡ Complexity

👉 O(n)

---

🧑‍💻 PHP Implementation

<?phpclass Node {
    public $data;
    public $next;    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}class LinkedList {
    public $head;    // Delete from beginning
    public function deleteFromBeginning() {
        if ($this->head == null) return;        $this->head = $this->head->next;
    }    // 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->next != null) {
            $temp = $temp->next;
        }        $temp->next = null;
    }    // Delete from position
    public function deleteAtPosition($position) {
        if ($this->head == null) return;        if ($position == 1) {
            $this->head = $this->head->next;
            return;
        }        $temp = $this->head;
        for ($i = 1; $i < $position - 1 && $temp->next != null; $i++) {
            $temp = $temp->next;
        }        if ($temp->next == null) return;        $temp->next = $temp->next->next;
    }
}?>

---

⚡ Time Complexity Summary

Operation	Complexity
Delete Beginning	O(1)
Delete End	O(n)
Delete Position	O(n)

---

🎯 Key Points

✅ No shifting like arrays
✅ Only pointer manipulation
✅ Efficient deletion