Insertion / Deletion

Overview

Insertion and deletion in linked lists are fundamentally different from arrays. Instead of shifting elements, you update pointers to connect or disconnect nodes. This makes these operations efficient in many cases.

Insertion at the Beginning

To insert at the head, create a new node, set its next pointer to the current head, and update the head to point to the new node. This operation is O(1) and very fast, unlike arrays which require shifting.

Insertion at a Specific Position

To insert after a given node, create a new node, set its next pointer to the target's next node, then update the target's next pointer to point to the new node. You must traverse to find the insertion point first.

Deletion at the Beginning

To delete the head node, simply update the head pointer to point to the second node. The original first node can then be garbage collected. This is an O(1) operation.

Deletion at a Specific Position

To delete a node, you need access to the previous node. Update the previous node's next pointer to skip over the node being deleted. In doubly linked lists, this is easier since each node knows its previous node.

Why Linked Lists Excel

Linked lists shine when you need frequent insertions and deletions, especially at the beginning or when you already have a reference to the insertion or deletion point. They avoid the expensive shifting operations required in arrays.