Data Structures & AlgorithmsCore Linked List Operations & Cost Model

Core Linked List Operations & Cost Model

LevelBeginner

Duration90 mins

TopicCore Linked List Operations & Cost Model

5 / 5

Deletion: O(1) if node is known, O(n) to find

The Two Faces of Deletion

Deletion in linked lists presents a fascinating duality. Consider these two scenarios:

Scenario A: "Here's a pointer to node X. Delete it."

Scenario B: "The list contains value 42. Find and delete it."

These might seem similar, but their complexities are fundamentally different:

Scenario A: O(1) — We have the node; just unlink it
Scenario B: O(n) — We must search through potentially all nodes

This distinction matters profoundly for system design. Understanding it helps you build data structures where deletion is efficient, rather than accidentally creating O(n) bottlenecks.

What You Will Learn

By the end of this page, you'll understand why deletion with a known reference is O(1), why finding a node to delete is O(n), the critical need to find the previous node, how to handle all edge cases in deletion, and design patterns that enable O(1) deletion in practice.

Deletion When Node Is Known — O(1)

Let's say you have a direct pointer to the node you want to delete. In a doubly linked list, this is truly O(1). In a singly linked list, there's a complication we'll address.

Doubly linked list deletion (true O(1)):

... ↔ [prev] ↔ [target] ↔ [next] ↔ ...

To delete target:

Set prev.next = target.next
Set next.prev = target.prev

Done. No traversal needed because we can access both neighbors directly.

doubly-linked-delete.ts
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
class DoublyListNode<T> {
    data: T;
    prev: DoublyListNode<T> | null = null;
    next: DoublyListNode<T> | null = null;
    
    constructor(data: T) {
        this.data = data;
    }
}
 
class DoublyLinkedList<T> {
    head: DoublyListNode<T> | null = null;
    tail: DoublyListNode<T> | null = null;
    
    // Delete a node when you have a reference to it — O(1)
    deleteNode(node: DoublyListNode<T>): void {
        // Update previous node's next pointer
        if (node.prev !== null) {
            node.prev.next = node.next;
        } else {
            // Node was head
            this.head = node.next;
        }
        
        // Update next node's prev pointer
        if (node.next !== null) {
            node.next.prev = node.prev;
        } else {
            // Node was tail
            this.tail = node.prev;
        }
        
        // Clean up the deleted node (optional but good practice)
        node.prev = null;
        node.next = null;
    }
}

Singly linked list deletion — the "previous node" problem:

In a singly linked list, we can't access the previous node directly. To unlink a node, we must modify prev.next — but we don't have prev!

... → [prev] → [target] → [next] → ...
              ↑
         We have this, but need to modify prev.next!

Solutions:

Store parent reference externally — Many algorithms pass both prev and current
Copy-and-delete trick — Copy next node's data to target, delete next node
Use doubly linked list — The proper solution when deletion is common

singly-linked-tricks.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Trick: Delete node without access to previous (singly linked)
// Only works if node is NOT the tail!
function deleteNodeTrick<T>(node: ListNode<T>): void {
    if (node.next === null) {
        throw new Error("Cannot delete tail node with this trick");
    }
    
    // Copy next node's data to this node
    node.data = node.next.data;
    
    // Delete next node (which we can do)
    node.next = node.next.next;
    
    // It looks like we deleted 'node', but actually we deleted node.next
    // The data has been copied, so the effect is the same
}
 
// Before: [A] → [B] → [C] → [D]
//              ↑ delete this
// Copy C's data to B's position, delete C
// After:  [A] → [C] → [D]
// Effectively deleted "B"

The Trick Has Limitations

The copy-and-delete trick fails for the tail node (no next to copy from). It also fails if other parts of your system hold references to the deleted node — they now point to different data! Use with caution.

Deletion by Value — O(n)

The more common case: you know the value to delete but not its location. This requires a search.

Algorithm:

Traverse the list to find the node containing the value
Keep track of the previous node during traversal
Unlink the target node via prev.next = target.next

delete-by-value.ts
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
class LinkedList<T> {
    head: ListNode<T> | null = null;
    
    // Delete first occurrence of value — O(n)
    deleteValue(value: T): boolean {
        // Edge case: empty list
        if (this.head === null) {
            return false;
        }
        
        // Edge case: head contains the value
        if (this.head.data === value) {
            this.head = this.head.next;
            return true;
        }
        
        // Search for node, tracking previous
        let prev = this.head;
        let current = this.head.next;
        
        while (current !== null) {
            if (current.data === value) {
                // Found it! Unlink current
                prev.next = current.next;
                return true;
            }
            prev = current;
            current = current.next;
        }
        
        // Value not found
        return false;
    }
    
    // Delete ALL occurrences of value — O(n)
    deleteAllValues(value: T): number {
        let deletedCount = 0;
        
        // Handle head(s) with value
        while (this.head !== null && this.head.data === value) {
            this.head = this.head.next;
            deletedCount++;
        }
        
        if (this.head === null) return deletedCount;
        
        // Scan rest of list
        let prev = this.head;
        let current = this.head.next;
        
        while (current !== null) {
            if (current.data === value) {
                prev.next = current.next;
                deletedCount++;
                // Don't advance prev — might be more consecutive matches
                current = prev.next;
            } else {
                prev = current;
                current = current.next;
            }
        }
        
        return deletedCount;
    }
}

Complexity analysis:

Best case: O(1) — Value is at head, no traversal needed

Average case: O(n/2) = O(n) — Value is somewhere in the middle

Worst case: O(n) — Value is at tail or not present

Why we need prev:

To unlink current, we must modify prev.next. Without tracking prev, we'd need to traverse again! This is why linked list algorithms often maintain two pointers: prev and current.

Deletion of Known Node

•Already have reference to node
•O(1) for doubly linked
•O(1) with trick for singly (not tail)
•No search required
•Used in LRU cache, schedulers

Deletion by Value

•Must search to find node
•O(n) regardless of list type
•Need to track previous node
•Linear scan unavoidable
•Common in simple list APIs

The Search Dominates

In 'delete by value', the O(n) cost comes from the search, not the unlinking. Even with a doubly linked list (O(1) unlink), delete by value is still O(n) due to the search.

Deleting from Different Positions

Let's examine deletion complexity at every position:

Delete from head — O(1):

delete-head.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    // Delete from head — O(1)
    deleteFromHead(): T | null {
        if (this.head === null) return null;
        
        const value = this.head.data;
        this.head = this.head.next;
        
        // Update tail if list became empty
        if (this.head === null) {
            this.tail = null;
        }
        
        return value;
    }
}
 
// Why O(1):
// - Direct access to head
// - Only update one pointer (head, and maybe tail)
// - No traversal needed

Delete from tail — O(n) for singly linked, O(1) for doubly linked:

delete-tail.ts
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
// SINGLY LINKED: O(n) — must find previous node
class SinglyLinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    deleteFromTail(): T | null {
        if (this.head === null) return null;
        
        // Single element case
        if (this.head === this.tail) {
            const value = this.head.data;
            this.head = null;
            this.tail = null;
            return value;
        }
        
        // Must find second-to-last node — O(n) traversal
        let current = this.head;
        while (current.next !== this.tail) {
            current = current.next!;
        }
        
        const value = this.tail!.data;
        current.next = null;
        this.tail = current;
        return value;
    }
}
 
// DOUBLY LINKED: O(1) — direct access to previous
class DoublyLinkedListWithTail<T> {
    head: DoublyListNode<T> | null = null;
    tail: DoublyListNode<T> | null = null;
    
    deleteFromTail(): T | null {
        if (this.tail === null) return null;
        
        const value = this.tail.data;
        
        if (this.head === this.tail) {
            // Single element
            this.head = null;
            this.tail = null;
        } else {
            // Move tail to previous
            this.tail = this.tail.prev;
            this.tail!.next = null;
        }
        
        return value;
    }
}

Deletion Complexity by Position
Position	Singly Linked	Doubly Linked	Notes
Head	O(1)	O(1)	Direct access
Tail	O(n)	O(1)	Need previous node
Known node (middle)	O(1)*	O(1)	*With copy trick
By index k	O(k)	O(min(k, n-k))	Must traverse
By value	O(n)	O(n)	Search dominates

Choose Based on Operations

If you need O(1) deletion from both ends (like a deque), use a doubly linked list. The extra memory for prev pointers is worth the O(n)→O(1) improvement for tail deletion.

Edge Cases in Deletion

Deletion involves more edge cases than insertion because we must handle the before-and-after state carefully. Let's examine each:

Edge Case 1: Empty list

edge-empty.ts
1
2
3
4
5
6
7
function deleteFromHead(head: ListNode<T> | null): ListNode<T> | null {
    if (head === null) {
        // Nothing to delete — return null or throw
        return null;
    }
    return head.next;
}

Edge Case 2: Single element list

edge-single.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    deleteOnly(): T | null {
        if (this.head === null) return null;
        if (this.head !== this.tail) {
            throw new Error("List has more than one element");
        }
        
        const value = this.head.data;
        // Must update BOTH head and tail
        this.head = null;
        this.tail = null;
        return value;
    }
}

Edge Case 3: Deleting head when it's also tail (same as single element)

edge-head-tail.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
deleteFromHead(): T | null {
    if (this.head === null) return null;
    
    const value = this.head.data;
    this.head = this.head.next;
    
    // Critical: check if list is now empty
    if (this.head === null) {
        this.tail = null;  // Don't leave stale tail pointer!
    }
    
    return value;
}

Edge Case 4: Deleting tail in multi-element list

edge-tail-multi.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// In a singly linked list with tail pointer
deleteFromTail(): T | null {
    if (this.tail === null) return null;
    
    // Single element
    if (this.head === this.tail) {
        const value = this.head.data;
        this.head = null;
        this.tail = null;
        return value;
    }
    
    // Multi-element: find second-to-last
    let current = this.head!;
    while (current.next !== this.tail) {
        current = current.next!;
    }
    
    const value = this.tail.data;
    current.next = null;
    this.tail = current;  // Update tail to new last node
    return value;
}

Edge Case 5: Deleting a node that doesn't exist (value not found)

edge-not-found.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
deleteValue(value: T): boolean {
    // ... traversal code ...
    
    while (current !== null) {
        if (current.data === value) {
            prev.next = current.next;
            // Handle tail pointer if current was tail
            if (current === this.tail) {
                this.tail = prev;
            }
            return true;
        }
        prev = current;
        current = current.next;
    }
    
    // Value not found — return false, not an error
    return false;
}

Test Every Edge Case

Production bugs often hide in edge cases. Create test cases for: empty list, single element, delete head, delete tail, delete middle, delete non-existent value. If you miss one, your users will find it.

Design Patterns for O(1) Deletion

If O(1) deletion is critical for your use case, you can design your system to make it possible. Here are proven patterns:

Pattern 1: Store node references externally

Keep a separate hash map from keys to node references:

node-reference-map.ts
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
// LRU Cache pattern: O(1) access AND O(1) deletion
class LRUCache<K, V> {
    private map: Map<K, DoublyListNode<{key: K, value: V}>> = new Map();
    private list: DoublyLinkedList<{key: K, value: V}>;
    private capacity: number;
    
    constructor(capacity: number) {
        this.capacity = capacity;
        this.list = new DoublyLinkedList();
    }
    
    get(key: K): V | undefined {
        const node = this.map.get(key);
        if (!node) return undefined;
        
        // Move to front (most recently used) — O(1)
        this.list.moveToFront(node);
        return node.data.value;
    }
    
    put(key: K, value: V): void {
        const existing = this.map.get(key);
        
        if (existing) {
            existing.data.value = value;
            this.list.moveToFront(existing);
            return;
        }
        
        // Evict if at capacity
        if (this.map.size >= this.capacity) {
            const lru = this.list.removeTail();  // O(1)
            if (lru) this.map.delete(lru.key);
        }
        
        // Add new node
        const node = this.list.addToFront({key, value});  // O(1)
        this.map.set(key, node);
    }
}

Pattern 2: Return node reference on insertion

Let callers keep references for later deletion:

return-reference.ts
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
class TaskQueue<T> {
    private list = new DoublyLinkedList<T>();
    
    // Return the node so caller can cancel later
    enqueue(task: T): DoublyListNode<T> {
        return this.list.addToTail(task);
    }
    
    dequeue(): T | null {
        return this.list.removeFromHead()?.data ?? null;
    }
    
    // Cancel a task by its reference — O(1)
    cancel(taskNode: DoublyListNode<T>): void {
        this.list.deleteNode(taskNode);
    }
}
 
// Usage
const queue = new TaskQueue<string>();
const handle1 = queue.enqueue("task1");
const handle2 = queue.enqueue("task2");
const handle3 = queue.enqueue("task3");
 
queue.cancel(handle2);  // O(1) — we have the reference

Pattern 3: Sentinel nodes for simpler edge cases

Dummy head and tail nodes eliminate null checks:

sentinel-deletion.ts
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
class SentinelDoublyLinkedList<T> {
    private sentinel: DoublyListNode<null>;
    
    constructor() {
        // Circular sentinel: points to itself when empty
        this.sentinel = new DoublyListNode(null);
        this.sentinel.prev = this.sentinel;
        this.sentinel.next = this.sentinel;
    }
    
    // Delete any node — O(1), no edge cases!
    deleteNode(node: DoublyListNode<T>): void {
        // Works even if node is first or last
        // Sentinel guaranteed to exist on both sides
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }
    
    isEmpty(): boolean {
        return this.sentinel.next === this.sentinel;
    }
    
    getFirst(): DoublyListNode<T> | null {
        if (this.isEmpty()) return null;
        return this.sentinel.next as DoublyListNode<T>;
    }
    
    getLast(): DoublyListNode<T> | null {
        if (this.isEmpty()) return null;
        return this.sentinel.prev as DoublyListNode<T>;
    }
}

Choose the Right Pattern

Pattern 1 (external map) is best when you need key-based lookup. Pattern 2 (return references) works when creators need to cancel their own items. Pattern 3 (sentinels) simplifies all operations but adds two dummy nodes of overhead.

Deletion vs Array Element Removal

Let's compare deletion semantics between linked lists and arrays to understand when each is preferable.

Array deletion (remove element at index k):

array-delete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Array deletion: O(n) due to shifting
function arrayDeleteAt<T>(arr: T[], index: number): T | undefined {
    if (index < 0 || index >= arr.length) return undefined;
    
    const value = arr[index];
    
    // Shift all elements after index left by one
    for (let i = index; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    arr.length--;  // Shrink array
    return value;
}
 
// Or using built-in (still O(n) internally):
arr.splice(index, 1);

Deletion Comparison: Linked List vs Array
Scenario	Linked List	Array	Winner
Delete from front	O(1)	O(n)	Linked List
Delete from back	O(n) singly / O(1) doubly	O(1)	Tie or Array
Delete at index k	O(k) + O(1) = O(k)	O(1) + O(n-k) = O(n-k)	Depends on k
Delete known element	O(1) with reference	O(n) to find + O(n) to shift	Linked List
Delete by value	O(n)	O(n) find + O(n) shift	Linked List

Key insight — No shifting in linked lists:

When you delete from a linked list, only pointers change. The remaining nodes stay in their memory locations. When you delete from an array, all subsequent elements must physically move to fill the gap.

For a 1-million-element array, deleting the first element requires copying 999,999 elements. For a linked list, it's just head = head.next.

When arrays win:

Arrays win when deletion is at the end (pop) or when you're doing bulk operations that can be optimized (e.g., filtering into a new array, which is O(n) once rather than O(n) per deletion).

Amortized Array Deletion

Some array implementations use 'lazy deletion' — mark elements as deleted without shifting, then compact periodically. This trades space for time. Linked lists don't need this trick because deletion is efficient naturally.

Memory Management and Deletion

In garbage-collected languages (JavaScript, Python, Java), unlinking a node makes it eligible for automatic memory reclamation. In languages with manual memory management (C, C++), deletion requires explicit deallocation.

Garbage-collected languages:

gc-deletion.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// JavaScript/TypeScript: Just unlink, GC handles the rest
function deleteFromHead(head: ListNode<T> | null): ListNode<T> | null {
    if (head === null) return null;
    
    const oldHead = head;
    head = head.next;
    
    // Optional: clear references to help GC
    oldHead.next = null;
    
    // oldHead is now unreachable (assuming no other references)
    // GC will eventually reclaim its memory
    
    return head;
}

Manual memory management (C++):

manual-deletion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
// C++: Must explicitly free memory
template<typename T>
void deleteFromHead(Node<T>*& head) {
    if (head == nullptr) return;
    
    Node<T>* oldHead = head;
    head = head->next;
    
    delete oldHead;  // CRITICAL: must free memory
    
    // Memory leak if you forget delete!
    // Use-after-free if you access oldHead after deletion!
}

Memory safety concerns:

Dangling pointers: If external code holds a reference to a deleted node, accessing it is undefined behavior (crash or corruption)
Memory leaks: In manual memory languages, forgetting to free deleted nodes leaks memory
Double free: Freeing the same node twice corrupts memory allocation

Best practices:

Safe Deletion Practices

•Encapsulate deletion — Make deletion a method of the list class, not external code
•Clear pointers — Set deleted node's pointers to null to fail fast on accidental access
•Use smart pointers — In C++, use unique_ptr or shared_ptr for automatic cleanup
•Document ownership — Clearly define who is responsible for node lifetime
•Avoid raw references — Don't let external code hold references to nodes

The Copy-Delete Trick Violates These Rules

The 'copy next data and delete next node' trick (for singly linked lists) breaks if external code holds a reference to the next node. After the trick, their reference points to garbage. Use carefully!

Summary: Mastering Linked List Deletion

We've thoroughly explored deletion in linked lists, revealing the crucial distinction between knowing what to delete and finding it. This knowledge is essential for designing efficient systems.

Key Takeaways

•Deletion with known reference: O(1) — For doubly linked lists, just update neighbor pointers. For singly linked, use the copy trick (with limitations).
•Deletion by value: O(n) — The search dominates. Even with O(1) unlinking, finding the node is linear.
•Previous node problem — Singly linked lists can't access the previous node, complicating middle deletion. Doubly linked lists solve this.
•Head deletion: Always O(1) — Direct access makes this trivial for any list type.
•Tail deletion: O(n) vs O(1) — Singly linked requires traversal; doubly linked uses prev pointer.
•Design for O(1) — Use external maps, return node references, or sentinels to enable constant-time deletion when needed.

Module Complete!

You've now mastered the core operations of linked lists and their cost models:

Traversal: O(n) — must visit each node
Access by index: O(n) — no random access
Insert at head: O(1) — pointer update only
Insert at tail: O(1) with tail pointer, O(n) without
Deletion: O(1) with reference, O(n) to find

This cost model comparison with arrays is fundamental to data structure selection. In the next module, we'll explore traversal, insertion, and deletion patterns in more detail.

Module Complete

Congratulations! You now have a comprehensive understanding of linked list operation costs. This knowledge enables you to predict performance, choose appropriate data structures, and design systems that avoid O(n) bottlenecks. You can confidently compare linked lists and arrays for any use case.

5 / 5

Loading learning content...

Data Structures & AlgorithmsCore Linked List Operations & Cost Model

Core Linked List Operations & Cost Model

LevelBeginner

Duration90 mins

TopicCore Linked List Operations & Cost Model

5 / 5

Deletion: O(1) if node is known, O(n) to find

The Two Faces of Deletion

Deletion in linked lists presents a fascinating duality. Consider these two scenarios:

Scenario A: "Here's a pointer to node X. Delete it."

Scenario B: "The list contains value 42. Find and delete it."

These might seem similar, but their complexities are fundamentally different:

Scenario A: O(1) — We have the node; just unlink it
Scenario B: O(n) — We must search through potentially all nodes

This distinction matters profoundly for system design. Understanding it helps you build data structures where deletion is efficient, rather than accidentally creating O(n) bottlenecks.

What You Will Learn

Deletion When Node Is Known — O(1)

Let's say you have a direct pointer to the node you want to delete. In a doubly linked list, this is truly O(1). In a singly linked list, there's a complication we'll address.

Doubly linked list deletion (true O(1)):

... ↔ [prev] ↔ [target] ↔ [next] ↔ ...

To delete target:

Set prev.next = target.next
Set next.prev = target.prev

Done. No traversal needed because we can access both neighbors directly.

doubly-linked-delete.ts
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
class DoublyListNode<T> {
    data: T;
    prev: DoublyListNode<T> | null = null;
    next: DoublyListNode<T> | null = null;
    
    constructor(data: T) {
        this.data = data;
    }
}
 
class DoublyLinkedList<T> {
    head: DoublyListNode<T> | null = null;
    tail: DoublyListNode<T> | null = null;
    
    // Delete a node when you have a reference to it — O(1)
    deleteNode(node: DoublyListNode<T>): void {
        // Update previous node's next pointer
        if (node.prev !== null) {
            node.prev.next = node.next;
        } else {
            // Node was head
            this.head = node.next;
        }
        
        // Update next node's prev pointer
        if (node.next !== null) {
            node.next.prev = node.prev;
        } else {
            // Node was tail
            this.tail = node.prev;
        }
        
        // Clean up the deleted node (optional but good practice)
        node.prev = null;
        node.next = null;
    }
}

Singly linked list deletion — the "previous node" problem:

In a singly linked list, we can't access the previous node directly. To unlink a node, we must modify prev.next — but we don't have prev!

... → [prev] → [target] → [next] → ...
              ↑
         We have this, but need to modify prev.next!

Solutions:

Store parent reference externally — Many algorithms pass both prev and current
Copy-and-delete trick — Copy next node's data to target, delete next node
Use doubly linked list — The proper solution when deletion is common

singly-linked-tricks.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Trick: Delete node without access to previous (singly linked)
// Only works if node is NOT the tail!
function deleteNodeTrick<T>(node: ListNode<T>): void {
    if (node.next === null) {
        throw new Error("Cannot delete tail node with this trick");
    }
    
    // Copy next node's data to this node
    node.data = node.next.data;
    
    // Delete next node (which we can do)
    node.next = node.next.next;
    
    // It looks like we deleted 'node', but actually we deleted node.next
    // The data has been copied, so the effect is the same
}
 
// Before: [A] → [B] → [C] → [D]
//              ↑ delete this
// Copy C's data to B's position, delete C
// After:  [A] → [C] → [D]
// Effectively deleted "B"

The Trick Has Limitations

Deletion by Value — O(n)

The more common case: you know the value to delete but not its location. This requires a search.

Algorithm:

Traverse the list to find the node containing the value
Keep track of the previous node during traversal
Unlink the target node via prev.next = target.next

delete-by-value.ts
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
class LinkedList<T> {
    head: ListNode<T> | null = null;
    
    // Delete first occurrence of value — O(n)
    deleteValue(value: T): boolean {
        // Edge case: empty list
        if (this.head === null) {
            return false;
        }
        
        // Edge case: head contains the value
        if (this.head.data === value) {
            this.head = this.head.next;
            return true;
        }
        
        // Search for node, tracking previous
        let prev = this.head;
        let current = this.head.next;
        
        while (current !== null) {
            if (current.data === value) {
                // Found it! Unlink current
                prev.next = current.next;
                return true;
            }
            prev = current;
            current = current.next;
        }
        
        // Value not found
        return false;
    }
    
    // Delete ALL occurrences of value — O(n)
    deleteAllValues(value: T): number {
        let deletedCount = 0;
        
        // Handle head(s) with value
        while (this.head !== null && this.head.data === value) {
            this.head = this.head.next;
            deletedCount++;
        }
        
        if (this.head === null) return deletedCount;
        
        // Scan rest of list
        let prev = this.head;
        let current = this.head.next;
        
        while (current !== null) {
            if (current.data === value) {
                prev.next = current.next;
                deletedCount++;
                // Don't advance prev — might be more consecutive matches
                current = prev.next;
            } else {
                prev = current;
                current = current.next;
            }
        }
        
        return deletedCount;
    }
}

Complexity analysis:

Best case: O(1) — Value is at head, no traversal needed

Average case: O(n/2) = O(n) — Value is somewhere in the middle

Worst case: O(n) — Value is at tail or not present

Why we need prev:

To unlink current, we must modify prev.next. Without tracking prev, we'd need to traverse again! This is why linked list algorithms often maintain two pointers: prev and current.

Deletion of Known Node

•Already have reference to node
•O(1) for doubly linked
•O(1) with trick for singly (not tail)
•No search required
•Used in LRU cache, schedulers

Deletion by Value

•Must search to find node
•O(n) regardless of list type
•Need to track previous node
•Linear scan unavoidable
•Common in simple list APIs

The Search Dominates

In 'delete by value', the O(n) cost comes from the search, not the unlinking. Even with a doubly linked list (O(1) unlink), delete by value is still O(n) due to the search.

Deleting from Different Positions

Let's examine deletion complexity at every position:

Delete from head — O(1):

delete-head.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    // Delete from head — O(1)
    deleteFromHead(): T | null {
        if (this.head === null) return null;
        
        const value = this.head.data;
        this.head = this.head.next;
        
        // Update tail if list became empty
        if (this.head === null) {
            this.tail = null;
        }
        
        return value;
    }
}
 
// Why O(1):
// - Direct access to head
// - Only update one pointer (head, and maybe tail)
// - No traversal needed

Delete from tail — O(n) for singly linked, O(1) for doubly linked:

delete-tail.ts
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
// SINGLY LINKED: O(n) — must find previous node
class SinglyLinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    deleteFromTail(): T | null {
        if (this.head === null) return null;
        
        // Single element case
        if (this.head === this.tail) {
            const value = this.head.data;
            this.head = null;
            this.tail = null;
            return value;
        }
        
        // Must find second-to-last node — O(n) traversal
        let current = this.head;
        while (current.next !== this.tail) {
            current = current.next!;
        }
        
        const value = this.tail!.data;
        current.next = null;
        this.tail = current;
        return value;
    }
}
 
// DOUBLY LINKED: O(1) — direct access to previous
class DoublyLinkedListWithTail<T> {
    head: DoublyListNode<T> | null = null;
    tail: DoublyListNode<T> | null = null;
    
    deleteFromTail(): T | null {
        if (this.tail === null) return null;
        
        const value = this.tail.data;
        
        if (this.head === this.tail) {
            // Single element
            this.head = null;
            this.tail = null;
        } else {
            // Move tail to previous
            this.tail = this.tail.prev;
            this.tail!.next = null;
        }
        
        return value;
    }
}

Deletion Complexity by Position
Position	Singly Linked	Doubly Linked	Notes
Head	O(1)	O(1)	Direct access
Tail	O(n)	O(1)	Need previous node
Known node (middle)	O(1)*	O(1)	*With copy trick
By index k	O(k)	O(min(k, n-k))	Must traverse
By value	O(n)	O(n)	Search dominates

Choose Based on Operations

If you need O(1) deletion from both ends (like a deque), use a doubly linked list. The extra memory for prev pointers is worth the O(n)→O(1) improvement for tail deletion.

Edge Cases in Deletion

Deletion involves more edge cases than insertion because we must handle the before-and-after state carefully. Let's examine each:

Edge Case 1: Empty list

edge-empty.ts
1
2
3
4
5
6
7
function deleteFromHead(head: ListNode<T> | null): ListNode<T> | null {
    if (head === null) {
        // Nothing to delete — return null or throw
        return null;
    }
    return head.next;
}

Edge Case 2: Single element list

edge-single.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LinkedListWithTail<T> {
    head: ListNode<T> | null = null;
    tail: ListNode<T> | null = null;
    
    deleteOnly(): T | null {
        if (this.head === null) return null;
        if (this.head !== this.tail) {
            throw new Error("List has more than one element");
        }
        
        const value = this.head.data;
        // Must update BOTH head and tail
        this.head = null;
        this.tail = null;
        return value;
    }
}

Edge Case 3: Deleting head when it's also tail (same as single element)

edge-head-tail.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
deleteFromHead(): T | null {
    if (this.head === null) return null;
    
    const value = this.head.data;
    this.head = this.head.next;
    
    // Critical: check if list is now empty
    if (this.head === null) {
        this.tail = null;  // Don't leave stale tail pointer!
    }
    
    return value;
}

Edge Case 4: Deleting tail in multi-element list

edge-tail-multi.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// In a singly linked list with tail pointer
deleteFromTail(): T | null {
    if (this.tail === null) return null;
    
    // Single element
    if (this.head === this.tail) {
        const value = this.head.data;
        this.head = null;
        this.tail = null;
        return value;
    }
    
    // Multi-element: find second-to-last
    let current = this.head!;
    while (current.next !== this.tail) {
        current = current.next!;
    }
    
    const value = this.tail.data;
    current.next = null;
    this.tail = current;  // Update tail to new last node
    return value;
}

Edge Case 5: Deleting a node that doesn't exist (value not found)

edge-not-found.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
deleteValue(value: T): boolean {
    // ... traversal code ...
    
    while (current !== null) {
        if (current.data === value) {
            prev.next = current.next;
            // Handle tail pointer if current was tail
            if (current === this.tail) {
                this.tail = prev;
            }
            return true;
        }
        prev = current;
        current = current.next;
    }
    
    // Value not found — return false, not an error
    return false;
}

Test Every Edge Case

Design Patterns for O(1) Deletion

If O(1) deletion is critical for your use case, you can design your system to make it possible. Here are proven patterns:

Pattern 1: Store node references externally

Keep a separate hash map from keys to node references:

node-reference-map.ts
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
// LRU Cache pattern: O(1) access AND O(1) deletion
class LRUCache<K, V> {
    private map: Map<K, DoublyListNode<{key: K, value: V}>> = new Map();
    private list: DoublyLinkedList<{key: K, value: V}>;
    private capacity: number;
    
    constructor(capacity: number) {
        this.capacity = capacity;
        this.list = new DoublyLinkedList();
    }
    
    get(key: K): V | undefined {
        const node = this.map.get(key);
        if (!node) return undefined;
        
        // Move to front (most recently used) — O(1)
        this.list.moveToFront(node);
        return node.data.value;
    }
    
    put(key: K, value: V): void {
        const existing = this.map.get(key);
        
        if (existing) {
            existing.data.value = value;
            this.list.moveToFront(existing);
            return;
        }
        
        // Evict if at capacity
        if (this.map.size >= this.capacity) {
            const lru = this.list.removeTail();  // O(1)
            if (lru) this.map.delete(lru.key);
        }
        
        // Add new node
        const node = this.list.addToFront({key, value});  // O(1)
        this.map.set(key, node);
    }
}

Pattern 2: Return node reference on insertion

Let callers keep references for later deletion:

return-reference.ts
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
class TaskQueue<T> {
    private list = new DoublyLinkedList<T>();
    
    // Return the node so caller can cancel later
    enqueue(task: T): DoublyListNode<T> {
        return this.list.addToTail(task);
    }
    
    dequeue(): T | null {
        return this.list.removeFromHead()?.data ?? null;
    }
    
    // Cancel a task by its reference — O(1)
    cancel(taskNode: DoublyListNode<T>): void {
        this.list.deleteNode(taskNode);
    }
}
 
// Usage
const queue = new TaskQueue<string>();
const handle1 = queue.enqueue("task1");
const handle2 = queue.enqueue("task2");
const handle3 = queue.enqueue("task3");
 
queue.cancel(handle2);  // O(1) — we have the reference

Pattern 3: Sentinel nodes for simpler edge cases

Dummy head and tail nodes eliminate null checks:

sentinel-deletion.ts
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
class SentinelDoublyLinkedList<T> {
    private sentinel: DoublyListNode<null>;
    
    constructor() {
        // Circular sentinel: points to itself when empty
        this.sentinel = new DoublyListNode(null);
        this.sentinel.prev = this.sentinel;
        this.sentinel.next = this.sentinel;
    }
    
    // Delete any node — O(1), no edge cases!
    deleteNode(node: DoublyListNode<T>): void {
        // Works even if node is first or last
        // Sentinel guaranteed to exist on both sides
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }
    
    isEmpty(): boolean {
        return this.sentinel.next === this.sentinel;
    }
    
    getFirst(): DoublyListNode<T> | null {
        if (this.isEmpty()) return null;
        return this.sentinel.next as DoublyListNode<T>;
    }
    
    getLast(): DoublyListNode<T> | null {
        if (this.isEmpty()) return null;
        return this.sentinel.prev as DoublyListNode<T>;
    }
}

Choose the Right Pattern

Deletion vs Array Element Removal

Let's compare deletion semantics between linked lists and arrays to understand when each is preferable.

Array deletion (remove element at index k):

array-delete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Array deletion: O(n) due to shifting
function arrayDeleteAt<T>(arr: T[], index: number): T | undefined {
    if (index < 0 || index >= arr.length) return undefined;
    
    const value = arr[index];
    
    // Shift all elements after index left by one
    for (let i = index; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    arr.length--;  // Shrink array
    return value;
}
 
// Or using built-in (still O(n) internally):
arr.splice(index, 1);

Deletion Comparison: Linked List vs Array
Scenario	Linked List	Array	Winner
Delete from front	O(1)	O(n)	Linked List
Delete from back	O(n) singly / O(1) doubly	O(1)	Tie or Array
Delete at index k	O(k) + O(1) = O(k)	O(1) + O(n-k) = O(n-k)	Depends on k
Delete known element	O(1) with reference	O(n) to find + O(n) to shift	Linked List
Delete by value	O(n)	O(n) find + O(n) shift	Linked List

Key insight — No shifting in linked lists:

For a 1-million-element array, deleting the first element requires copying 999,999 elements. For a linked list, it's just head = head.next.

When arrays win:

Arrays win when deletion is at the end (pop) or when you're doing bulk operations that can be optimized (e.g., filtering into a new array, which is O(n) once rather than O(n) per deletion).

Amortized Array Deletion

Memory Management and Deletion

Garbage-collected languages:

gc-deletion.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// JavaScript/TypeScript: Just unlink, GC handles the rest
function deleteFromHead(head: ListNode<T> | null): ListNode<T> | null {
    if (head === null) return null;
    
    const oldHead = head;
    head = head.next;
    
    // Optional: clear references to help GC
    oldHead.next = null;
    
    // oldHead is now unreachable (assuming no other references)
    // GC will eventually reclaim its memory
    
    return head;
}

Manual memory management (C++):

manual-deletion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
// C++: Must explicitly free memory
template<typename T>
void deleteFromHead(Node<T>*& head) {
    if (head == nullptr) return;
    
    Node<T>* oldHead = head;
    head = head->next;
    
    delete oldHead;  // CRITICAL: must free memory
    
    // Memory leak if you forget delete!
    // Use-after-free if you access oldHead after deletion!
}

Memory safety concerns:

Dangling pointers: If external code holds a reference to a deleted node, accessing it is undefined behavior (crash or corruption)
Memory leaks: In manual memory languages, forgetting to free deleted nodes leaks memory
Double free: Freeing the same node twice corrupts memory allocation

Best practices:

Safe Deletion Practices

•Encapsulate deletion — Make deletion a method of the list class, not external code
•Clear pointers — Set deleted node's pointers to null to fail fast on accidental access
•Use smart pointers — In C++, use unique_ptr or shared_ptr for automatic cleanup
•Document ownership — Clearly define who is responsible for node lifetime
•Avoid raw references — Don't let external code hold references to nodes

The Copy-Delete Trick Violates These Rules

Summary: Mastering Linked List Deletion

We've thoroughly explored deletion in linked lists, revealing the crucial distinction between knowing what to delete and finding it. This knowledge is essential for designing efficient systems.

Key Takeaways

•Deletion with known reference: O(1) — For doubly linked lists, just update neighbor pointers. For singly linked, use the copy trick (with limitations).
•Deletion by value: O(n) — The search dominates. Even with O(1) unlinking, finding the node is linear.
•Previous node problem — Singly linked lists can't access the previous node, complicating middle deletion. Doubly linked lists solve this.
•Head deletion: Always O(1) — Direct access makes this trivial for any list type.
•Tail deletion: O(n) vs O(1) — Singly linked requires traversal; doubly linked uses prev pointer.
•Design for O(1) — Use external maps, return node references, or sentinels to enable constant-time deletion when needed.

Module Complete!

You've now mastered the core operations of linked lists and their cost models:

Traversal: O(n) — must visit each node
Access by index: O(n) — no random access
Insert at head: O(1) — pointer update only
Insert at tail: O(1) with tail pointer, O(n) without
Deletion: O(1) with reference, O(n) to find

This cost model comparison with arrays is fundamental to data structure selection. In the next module, we'll explore traversal, insertion, and deletion patterns in more detail.

Module Complete

5 / 5