Traversal & Operations - Learning Module

Loading content...

0/276

Deleting from Beginning, Middle, and End

Breaking the Chain: The Art of Deletion

If insertion is about adding links to the chain, deletion is about removing them while keeping the rest intact. It's a delicate operation that requires precision—remove the wrong link or break it incorrectly, and you can lose access to entire sections of your data.

Deletion in a linked list involves two conceptual steps:

Bypassing the node: Redirecting pointers so the node is no longer part of the chain
Cleaning up: Handling memory (in unmanaged languages) or allowing garbage collection (in managed languages)

The key insight is that deletion is really about modifying the predecessor's pointer. To remove node X, you must find the node that points TO X and update it to point to X's successor instead.

In this page, we'll master all three deletion scenarios: removing from the head, from the tail, and from any arbitrary position in the middle.

Learning Objectives

By the end of this page, you will: • Master deletion at the head with O(1) efficiency • Understand the challenges of tail deletion in singly linked lists • Learn to delete from any position by finding the predecessor • Handle memory management and garbage collection considerations • Avoid common deletion bugs that cause memory leaks or crashes

The Deletion Mental Model

Before writing any code, let's build a solid mental model for linked list deletion.

The Bypass Pattern

Deletion is fundamentally about bypassing a node—removing it from the chain by making the node before it point directly to the node after it.

Visual:

Before: [A] → [B] → [C] → [D] → null
              ↑
              node to delete

After:  [A] → [C] → [D] → null
              ↑
              [B] is bypassed (orphaned)

The bypassed node ([B]) becomes orphaned—no other node points to it. What happens next depends on the language:

Garbage-collected languages (Python, JavaScript, Java): The node will be automatically cleaned up when no references remain.
Manual memory languages (C, C++): You must explicitly free the memory, or it leaks.

The Predecessor Requirement

Here's the critical challenge of deletion in a singly linked list: to delete a node, you need access to the node before it, because that's the node whose .next pointer must be updated.

Scenario	Do You Have Predecessor?	Difficulty
Delete head	Not needed (update `head` directly)	Easy
Delete after given node	Yes	Easy
Delete node by value	Must traverse to find it	Medium
Delete last node	Need to find second-to-last	Hard
Delete given node (not head)	No predecessor reference!	Tricky

Singly vs Doubly Linked Lists

In a doubly linked list, each node has both next and prev pointers. This makes deletion easier because given any node, you can access its predecessor via node.prev. In a singly linked list, you only have the forward reference, making deletion more nuanced.

Deletion at the Head

Deleting the head node is the simplest deletion operation. We simply move the head pointer forward to the second node.

Step-by-Step Mechanics

Initial State:

head → [A] → [B] → [C] → null

Goal: Delete the head node ([A])

Step 1: Save reference to the current head (optional, for returning its value)

node_to_delete = head  # [A]

Step 2: Move head to the next node

head = head.next

head → [B] → [C] → null
       
[A] → ???  (still points to [B], but nothing points to [A])

Step 3: Clean up (in manual memory languages)

delete node_to_delete  # Free memory in C/C++
# In Python/JS/Java, garbage collector handles this

Final State:

head → [B] → [C] → null

delete-at-head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def delete_head(head):
    """
    Delete the first node from the linked list.
    
    Parameters:
    - head: The current head of the list
    
    Returns:
    - Tuple of (new head, deleted node's data)
    - If list is empty, returns (None, None)
    
    Time Complexity: O(1) - no traversal needed
    Space Complexity: O(1)
    """
    # Handle empty list
    if head is None:
        return None, None
    
    # Save the data (optional, useful for returning what was deleted)
    deleted_data = head.data
    
    # Move head to the next node
    # This automatically handles the single-node case:
    # If head.next is None, new head becomes None (empty list)
    new_head = head.next
    
    # In Python, the old head node will be garbage collected
    # once no references to it remain
    
    return new_head, deleted_data
 
 
# Usage:
# head = create_list(['A', 'B', 'C'])  # [A] → [B] → [C]
# head, deleted = delete_head(head)    # [B] → [C], deleted = 'A'
# head, deleted = delete_head(head)    # [C], deleted = 'B'
# head, deleted = delete_head(head)    # None, deleted = 'C'
# head, deleted = delete_head(head)    # None, deleted = None

Single-Node List Handling

When the list has only one node, head.next is null. Setting head = head.next correctly makes the list empty (head becomes null). No special case needed!

Deletion at the Tail

Deleting the last node is significantly harder than deleting the head in a singly linked list. Why? Because we need to update the second-to-last node's next pointer to null, and we can only reach that node by traversing the entire list.

The Challenge Explained

To delete the tail:

We must find the second-to-last node (the new tail)
Set its .next to null
Optionally update a tail pointer if we maintain one

Step-by-Step Mechanics

Initial State:

head → [A] → [B] → [C] → null
                    ↑
                    node to delete

Goal: Delete the tail node ([C])

Step 1: Traverse to find the second-to-last node

current = head  # [A]

# Move until current.next.next is null
while current.next.next is not None:
    current = current.next

current → [B] (now points to second-to-last)

Step 2: Save reference to node being deleted (optional)

node_to_delete = current.next  # [C]

Step 3: Set current.next to null

current.next = null

head → [A] → [B] → null
       
[C] (orphaned)

Final State:

head → [A] → [B] → null

delete-at-tail
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def delete_tail(head):
    """
    Delete the last node from the linked list.
    
    Parameters:
    - head: The current head of the list
    
    Returns:
    - Tuple of (new head, deleted node's data)
    - Head changes only if the list had one element
    
    Time Complexity: O(n) - must traverse to find second-to-last
    Space Complexity: O(1)
    """
    # Case 1: Empty list
    if head is None:
        return None, None
    
    # Case 2: Single node list
    if head.next is None:
        deleted_data = head.data
        return None, deleted_data  # List becomes empty
    
    # Case 3: Multiple nodes - traverse to second-to-last
    current = head
    
    # Loop until current.next is the last node
    while current.next.next is not None:
        current = current.next
    
    # current now points to the second-to-last node
    deleted_data = current.next.data
    
    # Remove the last node
    current.next = None
    
    return head, deleted_data
 
 
# Usage:
# head = create_list([1, 2, 3, 4])  # [1] → [2] → [3] → [4]
# head, deleted = delete_tail(head) # [1] → [2] → [3], deleted = 4
# head, deleted = delete_tail(head) # [1] → [2], deleted = 3

With a Tail Pointer

Even with a tail pointer, deletion is still O(n) because we need the second-to-last node, not the last node:

delete-tail-with-pointer
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def delete_tail(self):
        """
        Delete the last node. 
        
        Even with a tail pointer, this is O(n) because
        we need to find the second-to-last node.
        
        Time Complexity: O(n) - unavoidable in singly linked list
        Space Complexity: O(1)
        """
        if self.head is None:
            return None
        
        if self.head == self.tail:  # Single node
            deleted_data = self.head.data
            self.head = None
            self.tail = None
            return deleted_data
        
        # Find second-to-last node
        current = self.head
        while current.next != self.tail:
            current = current.next
        
        # Delete the tail
        deleted_data = self.tail.data
        current.next = None
        self.tail = current  # Update tail pointer
        
        return deleted_data

Tail Deletion Remains O(n)

This is a fundamental limitation of singly linked lists. Even with a tail pointer, deleting the last node requires finding the second-to-last node, which means traversing from the head. For O(1) tail deletion, you need a doubly linked list where each node has a prev pointer.

Deletion in the Middle

Deleting from the middle requires finding the node to delete and its predecessor. There are several approaches depending on what information you have.

Approach 1: Delete by Value

Given a value, find and delete the first node containing that value:

delete-by-value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def delete_by_value(head, target):
    """
    Delete the first node containing the target value.
    
    Parameters:
    - head: The head of the list
    - target: The value to find and delete
    
    Returns:
    - The new head (may change if target is at head)
    - Raises ValueError if target not found
    
    Time Complexity: O(n) - must search for the value
    Space Complexity: O(1)
    """
    # Case 1: Empty list
    if head is None:
        raise ValueError(f"Value {target} not found in list")
    
    # Case 2: Target is at the head
    if head.data == target:
        return head.next  # New head
    
    # Case 3: Search for target in the rest of the list
    # We need to find the node BEFORE the target
    current = head
    
    while current.next is not None:
        if current.next.data == target:
            # Found! current.next is the node to delete
            # Bypass it by pointing current to current.next.next
            current.next = current.next.next
            return head  # Head unchanged
        current = current.next
    
    # Target not found
    raise ValueError(f"Value {target} not found in list")
 
 
# Example:
# head = create_list([1, 2, 3, 4, 5])
# head = delete_by_value(head, 3)  # [1] → [2] → [4] → [5]
# head = delete_by_value(head, 1)  # [2] → [4] → [5]
# head = delete_by_value(head, 5)  # [2] → [4]

Approach 2: Delete by Index

Given an index, delete the node at that position:

delete-by-index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def delete_at_index(head, index):
    """
    Delete the node at the given index (0-indexed).
    
    Parameters:
    - head: The head of the list
    - index: The position to delete (0 = head)
    
    Returns:
    - The new head (changes if index is 0)
    
    Time Complexity: O(n) - may need to traverse to index
    Space Complexity: O(1)
    """
    if head is None:
        raise IndexError(f"Index {index} out of range")
    
    # Case: Delete head
    if index == 0:
        return head.next
    
    # Find the node at index-1 (predecessor)
    current = head
    position = 0
    
    while current is not None and position < index - 1:
        current = current.next
        position += 1
    
    # Check if we found a valid position
    if current is None or current.next is None:
        raise IndexError(f"Index {index} out of range")
    
    # Delete: bypass current.next
    current.next = current.next.next
    
    return head
 
 
# Example:
# head = create_list(['A', 'B', 'C', 'D', 'E'])
# head = delete_at_index(head, 2)  # Delete 'C': [A, B, D, E]
# head = delete_at_index(head, 0)  # Delete 'A': [B, D, E]
# head = delete_at_index(head, 2)  # Delete 'E': [B, D]

Approach 3: Delete After a Given Node

If you have a reference to the predecessor, deletion is O(1):

delete-after-node
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def delete_after(prev_node):
    """
    Delete the node that comes after prev_node.
    
    Parameters:
    - prev_node: The node before the one to delete
    
    Returns:
    - The data of the deleted node
    
    Time Complexity: O(1) - direct pointer manipulation
    Space Complexity: O(1)
    """
    if prev_node is None:
        raise ValueError("Previous node cannot be None")
    
    if prev_node.next is None:
        raise ValueError("No node to delete after the given node")
    
    # Save the data of node to delete
    deleted_data = prev_node.next.data
    
    # Bypass the node
    # Before: prev_node → [X] → [Y]
    # After:  prev_node → [Y]
    prev_node.next = prev_node.next.next
    
    return deleted_data
 
 
# Example:
# List: [A] → [B] → [C] → [D]
#        ↑
#   node_B = find_node(head, 'B')
#   
# delete_after(node_B)  # Deletes 'C'
# Result: [A] → [B] → [D]

The Power of Having the Predecessor

Notice how delete_after is O(1)? If you have a reference to the predecessor, deletion is immediate. The O(n) cost of other deletion methods comes entirely from finding the predecessor. This is why algorithms often track the "previous" pointer during traversal—it enables O(1) deletion when needed.

The Tricky Case: Delete a Given Node

What if you're given a reference to the node you want to delete, but not its predecessor? In a singly linked list, you can't access the predecessor directly. Is deletion possible?

The Problem

List: [A] → [B] → [C] → [D]
              ↑
          given_node

We want to delete [B], but we don't have access to [A].
We can't update A.next because we don't have A!

The Copy-and-Delete Trick

There's a clever workaround: copy the data from the next node into the given node, then delete the next node. This has the same effect as deleting the given node.

delete-given-node-trick
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def delete_node(node):
    """
    Delete the given node from the list (without access to head).
    
    This uses the "copy and delete next" trick.
    
    IMPORTANT LIMITATION: This does NOT work for the last node!
    If node.next is None, we cannot use this approach.
    
    Parameters:
    - node: The node to delete (must not be the last node)
    
    Time Complexity: O(1)
    Space Complexity: O(1)
    """
    if node is None:
        raise ValueError("Node cannot be None")
    
    if node.next is None:
        raise ValueError("Cannot delete the last node with this method")
    
    # Step 1: Copy data from the next node
    node.data = node.next.data
    
    # Step 2: Delete the next node (which we've now "duplicated")
    node.next = node.next.next
    
 
# Visual explanation:
#
# Given: [A] → [B] → [C] → [D]
#               ↑
#              node (we want to delete "B")
#
# After Step 1 (copy C's data to B's position):
#        [A] → [C'] → [C] → [D]
#               ↑
#              node (now contains 'C')
#
# After Step 2 (delete the original C):
#        [A] → [C'] → [D]
#               ↑
#              node
#
# Result: [A] → [C] → [D]  (B is effectively deleted!)

Critical Limitations

The copy-and-delete trick has important limitations:

Cannot delete the last node: There's no next node to copy from.
References become invalid: If other code holds references to the next node, those references now point to a deleted node.
Object identity changes: The node that remains has the same memory address but different data.

Use this technique only when you understand these trade-offs.

Memory Management in Deletion

Understanding what happens to deleted nodes is crucial, especially if you work with languages that require manual memory management.

Garbage-Collected Languages (Python, JavaScript, Java)

In these languages, once no references point to a node, it becomes eligible for garbage collection:

# After: current.next = current.next.next
#
# The old current.next is now "floating" in memory
# with no references pointing to it.
#
# Python's garbage collector will eventually:
# 1. Detect that the object has no references
# 2. Reclaim its memory
# 3. Make that memory available for new allocations

Manual Memory Languages (C, C++)

In C and C++, you must explicitly free memory:

memory-management-cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void deleteValue(Node*& head, int target) {
    /**
     * Delete the first node with the given value.
     * CRITICAL: We must free the deleted node's memory!
     */
    if (head == nullptr) return;
    
    // Target at head
    if (head->data == target) {
        Node* toDelete = head;  // Save pointer to delete
        head = head->next;
        delete toDelete;        // FREE THE MEMORY!
        return;
    }
    
    // Search for target
    Node* current = head;
    while (current->next != nullptr) {
        if (current->next->data == target) {
            Node* toDelete = current->next;  // Save pointer
            current->next = current->next->next;
            delete toDelete;                 // FREE THE MEMORY!
            return;
        }
        current = current->next;
    }
}
 
 
// WHAT HAPPENS IF WE FORGET TO delete?
// 
// void BUGGYdelete(Node*& head, int target) {
//     if (head->data == target) {
//         head = head->next;  // ❌ Memory leak!
//         // The old head node is still allocated
//         // but we've lost our only reference to it.
//         // This memory can NEVER be reclaimed.
//     }
// }
//
// Over time, memory leaks cause your program to
// consume more and more memory until it crashes.

The Pattern for Safe C++ Deletion

The safe pattern in C++ is always:

Save a pointer to the node you're about to bypass
Perform the bypass (update next pointer)
Delete the saved pointer

This ensures you don't lose the reference before freeing the memory.

Time and Space Complexity Summary

Let's consolidate the complexity analysis for all deletion operations:

Deletion Operation Complexities
Operation	Time Complexity	Space Complexity	Notes
Delete head	O(1)	O(1)	Direct access, no traversal
Delete tail (singly linked)	O(n)	O(1)	Must find second-to-last node
Delete by value	O(n)	O(1)	Must search for value
Delete at index k	O(k)	O(1)	Must traverse to position k-1
Delete after given node	O(1)	O(1)	Direct pointer manipulation
Delete given node (trick)	O(1)	O(1)	Copy-delete, can't delete last

Comparison with Arrays

Position	Linked List	Dynamic Array
Delete head (index 0)	O(1) ✓	O(n) - shift all elements
Delete middle (index k)	O(k) to find + O(1) to delete	O(n-k) to shift
Delete tail (end)	O(n) ✗	O(1) ✓

Key Insight: Linked lists excel at head deletion. Arrays excel at tail deletion. For middle positions, it depends on whether you already have a reference to the predecessor.

Choosing the Right Structure

If your application frequently deletes from the beginning (like processing a queue), linked lists are ideal. If you frequently delete from the end (like a stack), arrays are better. For arbitrary deletions, consider a doubly linked list which offers O(1) deletion at any known position.

Complete Linked List with All Deletion Methods

Let's consolidate all deletion methods into a complete implementation:

complete-deletion-implementation
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    """
    A singly linked list with comprehensive deletion methods.
    """
    
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self.head is None
    
    def delete_head(self):
        """Delete and return the first element. O(1)"""
        if self.is_empty():
            raise IndexError("Cannot delete from empty list")
        
        deleted_data = self.head.data
        self.head = self.head.next
        
        # If list is now empty, update tail
        if self.head is None:
            self.tail = None
        
        self._size -= 1
        return deleted_data
    
    def delete_tail(self):
        """Delete and return the last element. O(n)"""
        if self.is_empty():
            raise IndexError("Cannot delete from empty list")
        
        if self.head == self.tail:  # Single element
            deleted_data = self.head.data
            self.head = None
            self.tail = None
            self._size -= 1
            return deleted_data
        
        # Find second-to-last node
        current = self.head
        while current.next != self.tail:
            current = current.next
        
        deleted_data = self.tail.data
        current.next = None
        self.tail = current
        self._size -= 1
        
        return deleted_data
    
    def delete_at_index(self, index):
        """Delete and return element at given index. O(n)"""
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range")
        
        if index == 0:
            return self.delete_head()
        
        if index == self._size - 1:
            return self.delete_tail()
        
        # Find predecessor
        current = self.head
        for _ in range(index - 1):
            current = current.next
        
        deleted_data = current.next.data
        current.next = current.next.next
        self._size -= 1
        
        return deleted_data
    
    def delete_by_value(self, value):
        """Delete first occurrence of value. O(n)"""
        if self.is_empty():
            raise ValueError(f"Value {value} not found")
        
        if self.head.data == value:
            return self.delete_head()
        
        current = self.head
        while current.next is not None:
            if current.next.data == value:
                # Check if we're deleting the tail
                if current.next == self.tail:
                    self.tail = current
                current.next = current.next.next
                self._size -= 1
                return value
            current = current.next
        
        raise ValueError(f"Value {value} not found")
    
    def display(self):
        """Return string representation of the list."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return " → ".join(elements) + " → None"
 
 
# Demonstration
if __name__ == "__main__":
    lst = LinkedList()
    
    # Build list
    for i in range(1, 6):
        lst.insert_at_tail(i)  # Assuming this method exists
    
    print(f"Initial: {lst.display()}")    # 1 → 2 → 3 → 4 → 5 → None
    
    print(f"Deleted head: {lst.delete_head()}")  # 1
    print(f"After: {lst.display()}")              # 2 → 3 → 4 → 5 → None
    
    print(f"Deleted tail: {lst.delete_tail()}")  # 5
    print(f"After: {lst.display()}")              # 2 → 3 → 4 → None
    
    print(f"Deleted index 1: {lst.delete_at_index(1)}")  # 3
    print(f"After: {lst.display()}")                      # 2 → 4 → None

Summary: Mastering Deletion

Deletion completes our toolkit for modifying linked list structure. Combined with traversal and insertion, you now have the fundamental operations needed for any linked list manipulation.

Key Takeaways

•Deletion is about bypassing: Update predecessor's next to skip over the deleted node
•Head deletion is O(1): Just move head to head.next
•Tail deletion is O(n): Must find second-to-last node (singly linked limitation)
•Middle deletion needs predecessor: Either traverse to find it or use the copy trick
•Memory management matters: In C/C++, always free deleted nodes
•The copy-delete trick: Useful but can't delete the last node
•Linked lists excel at front deletion: O(1) vs O(n) for arrays

Looking Ahead:

With traversal, insertion, and deletion mastered, we've covered the core operations. In the next page, we'll focus on edge cases—the subtle situations that trip up even experienced developers: empty lists, single-element lists, and operations on the last element. Handling these correctly is what separates robust code from buggy code.

Page Complete

You now understand all deletion patterns for linked lists. The bypass concept, the predecessor requirement, memory management, and the clever tricks for edge cases are now part of your toolkit. Next, we'll ensure you can handle every edge case with confidence.

Deleting from Beginning, Middle, and End

Breaking the Chain: The Art of Deletion

Deletion in a linked list involves two conceptual steps:

Bypassing the node: Redirecting pointers so the node is no longer part of the chain
Cleaning up: Handling memory (in unmanaged languages) or allowing garbage collection (in managed languages)

The key insight is that deletion is really about modifying the predecessor's pointer. To remove node X, you must find the node that points TO X and update it to point to X's successor instead.

In this page, we'll master all three deletion scenarios: removing from the head, from the tail, and from any arbitrary position in the middle.

Learning Objectives

The Deletion Mental Model

Before writing any code, let's build a solid mental model for linked list deletion.

The Bypass Pattern

Deletion is fundamentally about bypassing a node—removing it from the chain by making the node before it point directly to the node after it.

Visual:

Before: [A] → [B] → [C] → [D] → null
              ↑
              node to delete

After:  [A] → [C] → [D] → null
              ↑
              [B] is bypassed (orphaned)

The bypassed node ([B]) becomes orphaned—no other node points to it. What happens next depends on the language:

Garbage-collected languages (Python, JavaScript, Java): The node will be automatically cleaned up when no references remain.
Manual memory languages (C, C++): You must explicitly free the memory, or it leaks.

The Predecessor Requirement

Here's the critical challenge of deletion in a singly linked list: to delete a node, you need access to the node before it, because that's the node whose .next pointer must be updated.

Scenario	Do You Have Predecessor?	Difficulty
Delete head	Not needed (update `head` directly)	Easy
Delete after given node	Yes	Easy
Delete node by value	Must traverse to find it	Medium
Delete last node	Need to find second-to-last	Hard
Delete given node (not head)	No predecessor reference!	Tricky

Singly vs Doubly Linked Lists

Deletion at the Head

Deleting the head node is the simplest deletion operation. We simply move the head pointer forward to the second node.

Step-by-Step Mechanics

Initial State:

head → [A] → [B] → [C] → null

Goal: Delete the head node ([A])

Step 1: Save reference to the current head (optional, for returning its value)

node_to_delete = head  # [A]

Step 2: Move head to the next node

head = head.next

head → [B] → [C] → null
       
[A] → ???  (still points to [B], but nothing points to [A])

Step 3: Clean up (in manual memory languages)

delete node_to_delete  # Free memory in C/C++
# In Python/JS/Java, garbage collector handles this

Final State:

head → [B] → [C] → null

delete-at-head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def delete_head(head):
    """
    Delete the first node from the linked list.
    
    Parameters:
    - head: The current head of the list
    
    Returns:
    - Tuple of (new head, deleted node's data)
    - If list is empty, returns (None, None)
    
    Time Complexity: O(1) - no traversal needed
    Space Complexity: O(1)
    """
    # Handle empty list
    if head is None:
        return None, None
    
    # Save the data (optional, useful for returning what was deleted)
    deleted_data = head.data
    
    # Move head to the next node
    # This automatically handles the single-node case:
    # If head.next is None, new head becomes None (empty list)
    new_head = head.next
    
    # In Python, the old head node will be garbage collected
    # once no references to it remain
    
    return new_head, deleted_data
 
 
# Usage:
# head = create_list(['A', 'B', 'C'])  # [A] → [B] → [C]
# head, deleted = delete_head(head)    # [B] → [C], deleted = 'A'
# head, deleted = delete_head(head)    # [C], deleted = 'B'
# head, deleted = delete_head(head)    # None, deleted = 'C'
# head, deleted = delete_head(head)    # None, deleted = None

Single-Node List Handling

When the list has only one node, head.next is null. Setting head = head.next correctly makes the list empty (head becomes null). No special case needed!

Deletion at the Tail

The Challenge Explained

To delete the tail:

We must find the second-to-last node (the new tail)
Set its .next to null
Optionally update a tail pointer if we maintain one

Step-by-Step Mechanics

Initial State:

head → [A] → [B] → [C] → null
                    ↑
                    node to delete

Goal: Delete the tail node ([C])

Step 1: Traverse to find the second-to-last node

current = head  # [A]

# Move until current.next.next is null
while current.next.next is not None:
    current = current.next

current → [B] (now points to second-to-last)

Step 2: Save reference to node being deleted (optional)

node_to_delete = current.next  # [C]

Step 3: Set current.next to null

current.next = null

head → [A] → [B] → null
       
[C] (orphaned)

Final State:

head → [A] → [B] → null

delete-at-tail
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def delete_tail(head):
    """
    Delete the last node from the linked list.
    
    Parameters:
    - head: The current head of the list
    
    Returns:
    - Tuple of (new head, deleted node's data)
    - Head changes only if the list had one element
    
    Time Complexity: O(n) - must traverse to find second-to-last
    Space Complexity: O(1)
    """
    # Case 1: Empty list
    if head is None:
        return None, None
    
    # Case 2: Single node list
    if head.next is None:
        deleted_data = head.data
        return None, deleted_data  # List becomes empty
    
    # Case 3: Multiple nodes - traverse to second-to-last
    current = head
    
    # Loop until current.next is the last node
    while current.next.next is not None:
        current = current.next
    
    # current now points to the second-to-last node
    deleted_data = current.next.data
    
    # Remove the last node
    current.next = None
    
    return head, deleted_data
 
 
# Usage:
# head = create_list([1, 2, 3, 4])  # [1] → [2] → [3] → [4]
# head, deleted = delete_tail(head) # [1] → [2] → [3], deleted = 4
# head, deleted = delete_tail(head) # [1] → [2], deleted = 3

With a Tail Pointer

Even with a tail pointer, deletion is still O(n) because we need the second-to-last node, not the last node:

delete-tail-with-pointer
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def delete_tail(self):
        """
        Delete the last node. 
        
        Even with a tail pointer, this is O(n) because
        we need to find the second-to-last node.
        
        Time Complexity: O(n) - unavoidable in singly linked list
        Space Complexity: O(1)
        """
        if self.head is None:
            return None
        
        if self.head == self.tail:  # Single node
            deleted_data = self.head.data
            self.head = None
            self.tail = None
            return deleted_data
        
        # Find second-to-last node
        current = self.head
        while current.next != self.tail:
            current = current.next
        
        # Delete the tail
        deleted_data = self.tail.data
        current.next = None
        self.tail = current  # Update tail pointer
        
        return deleted_data

Tail Deletion Remains O(n)

Deletion in the Middle

Deleting from the middle requires finding the node to delete and its predecessor. There are several approaches depending on what information you have.

Approach 1: Delete by Value

Given a value, find and delete the first node containing that value:

delete-by-value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def delete_by_value(head, target):
    """
    Delete the first node containing the target value.
    
    Parameters:
    - head: The head of the list
    - target: The value to find and delete
    
    Returns:
    - The new head (may change if target is at head)
    - Raises ValueError if target not found
    
    Time Complexity: O(n) - must search for the value
    Space Complexity: O(1)
    """
    # Case 1: Empty list
    if head is None:
        raise ValueError(f"Value {target} not found in list")
    
    # Case 2: Target is at the head
    if head.data == target:
        return head.next  # New head
    
    # Case 3: Search for target in the rest of the list
    # We need to find the node BEFORE the target
    current = head
    
    while current.next is not None:
        if current.next.data == target:
            # Found! current.next is the node to delete
            # Bypass it by pointing current to current.next.next
            current.next = current.next.next
            return head  # Head unchanged
        current = current.next
    
    # Target not found
    raise ValueError(f"Value {target} not found in list")
 
 
# Example:
# head = create_list([1, 2, 3, 4, 5])
# head = delete_by_value(head, 3)  # [1] → [2] → [4] → [5]
# head = delete_by_value(head, 1)  # [2] → [4] → [5]
# head = delete_by_value(head, 5)  # [2] → [4]

Approach 2: Delete by Index

Given an index, delete the node at that position:

delete-by-index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def delete_at_index(head, index):
    """
    Delete the node at the given index (0-indexed).
    
    Parameters:
    - head: The head of the list
    - index: The position to delete (0 = head)
    
    Returns:
    - The new head (changes if index is 0)
    
    Time Complexity: O(n) - may need to traverse to index
    Space Complexity: O(1)
    """
    if head is None:
        raise IndexError(f"Index {index} out of range")
    
    # Case: Delete head
    if index == 0:
        return head.next
    
    # Find the node at index-1 (predecessor)
    current = head
    position = 0
    
    while current is not None and position < index - 1:
        current = current.next
        position += 1
    
    # Check if we found a valid position
    if current is None or current.next is None:
        raise IndexError(f"Index {index} out of range")
    
    # Delete: bypass current.next
    current.next = current.next.next
    
    return head
 
 
# Example:
# head = create_list(['A', 'B', 'C', 'D', 'E'])
# head = delete_at_index(head, 2)  # Delete 'C': [A, B, D, E]
# head = delete_at_index(head, 0)  # Delete 'A': [B, D, E]
# head = delete_at_index(head, 2)  # Delete 'E': [B, D]

Approach 3: Delete After a Given Node

If you have a reference to the predecessor, deletion is O(1):

delete-after-node
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def delete_after(prev_node):
    """
    Delete the node that comes after prev_node.
    
    Parameters:
    - prev_node: The node before the one to delete
    
    Returns:
    - The data of the deleted node
    
    Time Complexity: O(1) - direct pointer manipulation
    Space Complexity: O(1)
    """
    if prev_node is None:
        raise ValueError("Previous node cannot be None")
    
    if prev_node.next is None:
        raise ValueError("No node to delete after the given node")
    
    # Save the data of node to delete
    deleted_data = prev_node.next.data
    
    # Bypass the node
    # Before: prev_node → [X] → [Y]
    # After:  prev_node → [Y]
    prev_node.next = prev_node.next.next
    
    return deleted_data
 
 
# Example:
# List: [A] → [B] → [C] → [D]
#        ↑
#   node_B = find_node(head, 'B')
#   
# delete_after(node_B)  # Deletes 'C'
# Result: [A] → [B] → [D]

The Power of Having the Predecessor

The Tricky Case: Delete a Given Node

What if you're given a reference to the node you want to delete, but not its predecessor? In a singly linked list, you can't access the predecessor directly. Is deletion possible?

The Problem

List: [A] → [B] → [C] → [D]
              ↑
          given_node

We want to delete [B], but we don't have access to [A].
We can't update A.next because we don't have A!

The Copy-and-Delete Trick

There's a clever workaround: copy the data from the next node into the given node, then delete the next node. This has the same effect as deleting the given node.

delete-given-node-trick
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def delete_node(node):
    """
    Delete the given node from the list (without access to head).
    
    This uses the "copy and delete next" trick.
    
    IMPORTANT LIMITATION: This does NOT work for the last node!
    If node.next is None, we cannot use this approach.
    
    Parameters:
    - node: The node to delete (must not be the last node)
    
    Time Complexity: O(1)
    Space Complexity: O(1)
    """
    if node is None:
        raise ValueError("Node cannot be None")
    
    if node.next is None:
        raise ValueError("Cannot delete the last node with this method")
    
    # Step 1: Copy data from the next node
    node.data = node.next.data
    
    # Step 2: Delete the next node (which we've now "duplicated")
    node.next = node.next.next
    
 
# Visual explanation:
#
# Given: [A] → [B] → [C] → [D]
#               ↑
#              node (we want to delete "B")
#
# After Step 1 (copy C's data to B's position):
#        [A] → [C'] → [C] → [D]
#               ↑
#              node (now contains 'C')
#
# After Step 2 (delete the original C):
#        [A] → [C'] → [D]
#               ↑
#              node
#
# Result: [A] → [C] → [D]  (B is effectively deleted!)

Critical Limitations

The copy-and-delete trick has important limitations:

Cannot delete the last node: There's no next node to copy from.
References become invalid: If other code holds references to the next node, those references now point to a deleted node.
Object identity changes: The node that remains has the same memory address but different data.

Use this technique only when you understand these trade-offs.

Memory Management in Deletion

Understanding what happens to deleted nodes is crucial, especially if you work with languages that require manual memory management.

Garbage-Collected Languages (Python, JavaScript, Java)

In these languages, once no references point to a node, it becomes eligible for garbage collection:

# After: current.next = current.next.next
#
# The old current.next is now "floating" in memory
# with no references pointing to it.
#
# Python's garbage collector will eventually:
# 1. Detect that the object has no references
# 2. Reclaim its memory
# 3. Make that memory available for new allocations

Manual Memory Languages (C, C++)

In C and C++, you must explicitly free memory:

memory-management-cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void deleteValue(Node*& head, int target) {
    /**
     * Delete the first node with the given value.
     * CRITICAL: We must free the deleted node's memory!
     */
    if (head == nullptr) return;
    
    // Target at head
    if (head->data == target) {
        Node* toDelete = head;  // Save pointer to delete
        head = head->next;
        delete toDelete;        // FREE THE MEMORY!
        return;
    }
    
    // Search for target
    Node* current = head;
    while (current->next != nullptr) {
        if (current->next->data == target) {
            Node* toDelete = current->next;  // Save pointer
            current->next = current->next->next;
            delete toDelete;                 // FREE THE MEMORY!
            return;
        }
        current = current->next;
    }
}
 
 
// WHAT HAPPENS IF WE FORGET TO delete?
// 
// void BUGGYdelete(Node*& head, int target) {
//     if (head->data == target) {
//         head = head->next;  // ❌ Memory leak!
//         // The old head node is still allocated
//         // but we've lost our only reference to it.
//         // This memory can NEVER be reclaimed.
//     }
// }
//
// Over time, memory leaks cause your program to
// consume more and more memory until it crashes.

The Pattern for Safe C++ Deletion

The safe pattern in C++ is always:

Save a pointer to the node you're about to bypass
Perform the bypass (update next pointer)
Delete the saved pointer

This ensures you don't lose the reference before freeing the memory.

Time and Space Complexity Summary

Let's consolidate the complexity analysis for all deletion operations:

Deletion Operation Complexities
Operation	Time Complexity	Space Complexity	Notes
Delete head	O(1)	O(1)	Direct access, no traversal
Delete tail (singly linked)	O(n)	O(1)	Must find second-to-last node
Delete by value	O(n)	O(1)	Must search for value
Delete at index k	O(k)	O(1)	Must traverse to position k-1
Delete after given node	O(1)	O(1)	Direct pointer manipulation
Delete given node (trick)	O(1)	O(1)	Copy-delete, can't delete last

Comparison with Arrays

Position	Linked List	Dynamic Array
Delete head (index 0)	O(1) ✓	O(n) - shift all elements
Delete middle (index k)	O(k) to find + O(1) to delete	O(n-k) to shift
Delete tail (end)	O(n) ✗	O(1) ✓

Key Insight: Linked lists excel at head deletion. Arrays excel at tail deletion. For middle positions, it depends on whether you already have a reference to the predecessor.

Choosing the Right Structure

Complete Linked List with All Deletion Methods

Let's consolidate all deletion methods into a complete implementation:

complete-deletion-implementation
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    """
    A singly linked list with comprehensive deletion methods.
    """
    
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self.head is None
    
    def delete_head(self):
        """Delete and return the first element. O(1)"""
        if self.is_empty():
            raise IndexError("Cannot delete from empty list")
        
        deleted_data = self.head.data
        self.head = self.head.next
        
        # If list is now empty, update tail
        if self.head is None:
            self.tail = None
        
        self._size -= 1
        return deleted_data
    
    def delete_tail(self):
        """Delete and return the last element. O(n)"""
        if self.is_empty():
            raise IndexError("Cannot delete from empty list")
        
        if self.head == self.tail:  # Single element
            deleted_data = self.head.data
            self.head = None
            self.tail = None
            self._size -= 1
            return deleted_data
        
        # Find second-to-last node
        current = self.head
        while current.next != self.tail:
            current = current.next
        
        deleted_data = self.tail.data
        current.next = None
        self.tail = current
        self._size -= 1
        
        return deleted_data
    
    def delete_at_index(self, index):
        """Delete and return element at given index. O(n)"""
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range")
        
        if index == 0:
            return self.delete_head()
        
        if index == self._size - 1:
            return self.delete_tail()
        
        # Find predecessor
        current = self.head
        for _ in range(index - 1):
            current = current.next
        
        deleted_data = current.next.data
        current.next = current.next.next
        self._size -= 1
        
        return deleted_data
    
    def delete_by_value(self, value):
        """Delete first occurrence of value. O(n)"""
        if self.is_empty():
            raise ValueError(f"Value {value} not found")
        
        if self.head.data == value:
            return self.delete_head()
        
        current = self.head
        while current.next is not None:
            if current.next.data == value:
                # Check if we're deleting the tail
                if current.next == self.tail:
                    self.tail = current
                current.next = current.next.next
                self._size -= 1
                return value
            current = current.next
        
        raise ValueError(f"Value {value} not found")
    
    def display(self):
        """Return string representation of the list."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return " → ".join(elements) + " → None"
 
 
# Demonstration
if __name__ == "__main__":
    lst = LinkedList()
    
    # Build list
    for i in range(1, 6):
        lst.insert_at_tail(i)  # Assuming this method exists
    
    print(f"Initial: {lst.display()}")    # 1 → 2 → 3 → 4 → 5 → None
    
    print(f"Deleted head: {lst.delete_head()}")  # 1
    print(f"After: {lst.display()}")              # 2 → 3 → 4 → 5 → None
    
    print(f"Deleted tail: {lst.delete_tail()}")  # 5
    print(f"After: {lst.display()}")              # 2 → 3 → 4 → None
    
    print(f"Deleted index 1: {lst.delete_at_index(1)}")  # 3
    print(f"After: {lst.display()}")                      # 2 → 4 → None

Summary: Mastering Deletion

Deletion completes our toolkit for modifying linked list structure. Combined with traversal and insertion, you now have the fundamental operations needed for any linked list manipulation.

Key Takeaways

•Deletion is about bypassing: Update predecessor's next to skip over the deleted node
•Head deletion is O(1): Just move head to head.next
•Tail deletion is O(n): Must find second-to-last node (singly linked limitation)
•Middle deletion needs predecessor: Either traverse to find it or use the copy trick
•Memory management matters: In C/C++, always free deleted nodes
•The copy-delete trick: Useful but can't delete the last node
•Linked lists excel at front deletion: O(1) vs O(n) for arrays

Looking Ahead:

Page Complete