Deletion
Deleting from a linked list means removing a node and re-linking the nodes around it so the chain stays intact. That's the big advantage over arrays: nothing has to shift, you just point around the node you're removing.
How fast that deletion is depends entirely on where the node sits. Removing the head is a constant-time O(1) fix, but reaching an arbitrary node or the tail (if you don't keep a tail pointer) means walking the list first, which costs O(n).
The tricky part isn't the removal itself, it's getting the pointer rewiring right so you don't accidentally orphan part of the list or leave a dangling reference behind.
Key Consideration: Proper deletion requires maintaining list connectivity and handling memory appropriately to prevent leaks (in manual memory management environments).
Deletion Types
Deletion at Head
Complexity: O(1)
Removes the first node, making the next node the new head
function deleteHead() {
if (!head) return; // Empty list
const temp = head;
head = head.next;
// In languages without GC:
// temp.next = null; // Isolate node
// free(temp); // Free memory
// Special case: If list becomes empty
if (!head) tail = null;
}Deletion at Tail
Complexity: O(n) without tail pointer, O(1) with doubly linked list
Removes the last node, requiring traversal to find new tail
function deleteTail() {
if (!head) return; // Empty list
// Single node case
if (!head.next) {
head = null;
tail = null;
return;
}
// Traverse to find node before tail
let current = head;
while (current.next && current.next.next) {
current = current.next;
}
// Now current is the new tail
current.next = null;
tail = current;
}Deletion by Value
Complexity: O(n)
Finds and removes first node containing matching value
function deleteValue(value) {
if (!head) return; // Empty list
// Special case: head contains value
if (head.data === value) {
deleteHead();
return;
}
let current = head;
while (current.next && current.next.data !== value) {
current = current.next;
}
if (current.next) {
const toDelete = current.next;
current.next = toDelete.next;
// Update tail if deleting last node
if (!current.next) tail = current;
// In languages without GC:
// toDelete.next = null;
// free(toDelete);
}
}Deletion at Position
Complexity: O(n)
Removes node at specific index (0-based)
function deleteAt(position) {
if (!head || position < 0) return;
if (position === 0) {
deleteHead();
return;
}
let current = head;
for (let i = 0; current && i < position-1; i++) {
current = current.next;
}
if (!current || !current.next) return; // Out of bounds
const toDelete = current.next;
current.next = toDelete.next;
// Update tail if deleting last node
if (!current.next) tail = current;
// Memory cleanup in non-GC languages
// toDelete.next = null;
// free(toDelete);
}Deletion Processes
Head Deletion
- Check if list is empty (head is null)
- Store reference to current head node
- Update head pointer to head.next
- Handle memory cleanup (if needed)
- Special case: If list becomes empty, update tail pointer
Tail Deletion
- Check for empty list
- Handle single node case separately
- Traverse to find node before tail (penultimate node)
- Set penultimate node's next to null
- Update tail pointer to penultimate node
Middle Deletion
- Traverse to find node before target node
- Update previous node's next pointer to skip target
- Handle special case when deleting last node
- Perform memory cleanup (if needed)
Operation Visualization
| Operation | List State |
|---|---|
| Initial State | head → [A] → [B] → [C] → [D] → null |
| deleteHead() | head → [B] → [C] → [D] → null |
| deleteTail() | head → [B] → [C] → null |
| deleteValue('C') | head → [B] → null |
| deleteAt(0) | head → null |
Edge Cases to Consider
Empty list (head = null)
Single node list (head = tail)
Deleting head node
Deleting tail node
Deleting non-existent value
Deleting at invalid position (negative or out of bounds)
Memory management in non-GC languages
Best Practices
Always check for empty list before deletion
Maintain proper head/tail pointers after deletion
Handle single node case separately
In non-GC languages, properly free deleted node memory
Consider using dummy nodes to simplify edge cases
Document position/indexing scheme (0-based vs 1-based)
Validate position bounds before deletion attempts
Comparison with Array Deletion
| Feature | Array | Linked List |
|---|---|---|
| Time Complexity | O(n) (requires shifting) | O(1) head, O(n) arbitrary/tail |
| Space Complexity | O(1) | O(1) |
| Memory Usage | Fixed size unless resized | Dynamic, no unused capacity |
| Implementation | Simple indexing | Pointer manipulation |
| Best For | Frequent random access | Frequent deletions at head |
When to Choose: Prefer linked lists when you need frequent deletions, especially at the head. Use arrays when you need index-based access and memory efficiency for small, fixed-size collections.
Implementation Notes
- Memory Management: In languages without garbage collection, ensure proper memory deallocation when deleting nodes
- Error Handling: Implement robust checks for edge cases to prevent null pointer exceptions
- Testing: Thoroughly test all deletion scenarios including empty list, single-node list, head/tail deletions
- Optimizations: For frequent tail deletions, consider using a doubly linked list for O(1) performance
- Documentation: Clearly document whether your deletion methods return the deleted value or just remove it