Skip to content
Home » Deleting

Deleting

✅ Deletion in Linked List

✅ 1. Introduction

Deletion in a linked list means removing an existing node from the list.
Unlike arrays, deletion in a linked list does not require shifting of elements; only pointer adjustments are needed.

✅ 2. Types of Deletion in Linked List

Deletion in a Singly Linked List can be performed at:

  1. Deletion at Beginning
  2. Deletion at End
  3. Deletion at a Specific Position (Middle)

✅ 3. Deletion at Beginning

✅ Definition

Deletion at beginning means removing the first node of the linked list.

✅ Steps Involved

  1. Check if HEAD == NULL (list empty)
  2. Store address of first node in temp
  3. Move HEAD to the next node
  4. Free the memory of temp

✅ Diagram

Before deletion:

HEAD → 10 → 20 → 30 → NULL

After deleting first node:

HEAD → 20 → 30 → NULL

✅ Algorithm: Delete_Begin(HEAD)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. Set temp = HEAD
  4. Set HEAD = HEAD->next
  5. Free temp
  6. Stop

✅ Time Complexity

✅ O(1)

✅ 4. Deletion at End

✅ Definition

Deletion at end means removing the last node of the linked list.

✅ Steps Involved

  1. Check if list is empty
  2. Traverse to the second last node
  3. Set second last node’s next = NULL
  4. Free the last node

✅ Diagram

Before deletion:

HEAD → 10 → 20 → 30 → NULL

After deleting last node:

HEAD → 10 → 20 → NULL

✅ Algorithm: Delete_End(HEAD)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. If HEAD->next == NULL (only one node):
    • Free HEAD
    • Set HEAD = NULL
    • Stop
  4. Set temp = HEAD
  5. While temp->next->next != NULL
    • temp = temp->next
  6. Free temp->next
  7. Set temp->next = NULL
  8. Stop

✅ Time Complexity

✅ O(n)

✅ 5. Deletion at a Specific Position (Middle)

✅ Definition

Deletion at a specific position means removing a node from a given position in the linked list.

✅ Steps Involved

  1. Check if list is empty
  2. If position is 1, perform deletion at beginning
  3. Traverse to the node just before the position
  4. Store address of node to be deleted
  5. Adjust pointer to skip the deleted node
  6. Free the deleted node

✅ Diagram

Delete node at position 3:

Before:

HEAD → 10 → 20 → 30 → 40 → NULL

After:

HEAD → 10 → 20 → 40 → NULL

✅ Algorithm: Delete_Position(HEAD, POS)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. If POS == 1, perform Delete_Begin and Stop
  4. Set temp = HEAD
  5. Repeat POS-2 times:
    • temp = temp->next
  6. Set del = temp->next
  7. Set temp->next = del->next
  8. Free del
  9. Stop

✅ Time Complexity

✅ O(n)

✅ 6. Special Case: Deletion in Circular Linked List (Brief)

  • Need to update last node’s next pointer.
  • No NULL pointer, so careful traversal required.

✅ 7. Advantages of Deletion in Linked List

✅ Benefits:

  • No shifting of elements
  • Efficient compared to arrays
  • Dynamic memory handling

✅ Conclusion

Deletion in a linked list involves removing a node by adjusting pointers. Deletion at the beginning is the fastest (O(1)), while deletion at the end and at a specific position requires traversal (O(n)). Linked lists are efficient when frequent deletions are required.