Deletion

Linked List deletion involves removing nodes from the linked data structure at various positions. Unlike arrays, linked lists allow efficient deletion at any point without requiring shifting of remaining elements.

Deletion is a fundamental operation that enables dynamic modification of the list. The efficiency varies based on deletion position, from O(1) for head to O(n) for arbitrary positions or tail (without tail pointer).

Proper deletion requires careful pointer manipulation to maintain list integrity and avoid memory leaks (in languages without garbage collection).

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

Linked List Deletion