Core Operations & Cost - Learning Module

Loading content...

0/276

Insertion at Head: O(1)

Where Linked Lists Shine

After learning about the O(n) costs of traversal and indexed access, you might wonder: Why would anyone use linked lists?

The answer begins here. Inserting a new element at the head of a linked list costs O(1)—constant time, regardless of list size. Whether the list has 10 elements or 10 million, inserting at the front takes the same handful of operations.

Compare this to arrays, where inserting at the front requires shifting every existing element one position to the right—an O(n) operation that becomes painfully slow at scale.

This constant-time insertion is the fundamental advantage of linked lists, and understanding it deeply reveals when linked lists are the right choice.

What You Will Learn

By the end of this page, you'll understand exactly how head insertion works, why it's O(1), how to implement it correctly avoiding common bugs, how this compares to array insertion, and when this advantage makes linked lists the optimal choice.

The Mechanics of Head Insertion

Inserting at the head of a linked list is remarkably simple. Let's visualize it step by step.

Starting state: A linked list with elements [A, B, C]

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

Goal: Insert a new node [X] at the front

Step 1: Create the new node

newNode = [X] → null
head → [A] → [B] → [C] → null

Step 2: Point new node's next to current head

newNode = [X] → [A] → [B] → [C] → null
                 ↑
                head (still pointing here)

Step 3: Update head to point to new node

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

That's it. Three conceptual steps, regardless of list size.

insert-at-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
25
26
27
28
29
30
class ListNode<T> {
    data: T;
    next: ListNode<T> | null;
    
    constructor(data: T) {
        this.data = data;
        this.next = null;
    }
}
 
function insertAtHead<T>(
    head: ListNode<T> | null, 
    value: T
): ListNode<T> {
    // Step 1: Create new node
    const newNode = new ListNode(value);
    
    // Step 2: Point new node's next to current head
    newNode.next = head;
    
    // Step 3: Return new node as the new head
    return newNode;
}
 
// Usage:
let list: ListNode<string> | null = null;
 
list = insertAtHead(list, "C");  // list: [C]
list = insertAtHead(list, "B");  // list: [B, C]
list = insertAtHead(list, "A");  // list: [A, B, C]

Operation count analysis:

Memory allocation: Allocate one new node — O(1)
Assignment: Set newNode.next = head — O(1)
Update head: head = newNode — O(1)

Total: 3 constant-time operations = O(1)

The existing nodes remain exactly where they are in memory. We don't touch them, copy them, or move them. We only adjust pointers.

The Order of Operations Matters

Always set newNode.next = head BEFORE updating head = newNode. If you update head first, you lose access to the rest of the list! This is a classic bug that causes data loss.

Why This Is O(1) — Deeper Analysis

Let's be rigorous about why head insertion is constant time.

What makes an operation O(1)?

An operation is O(1) when the number of elementary steps doesn't depend on the input size. For head insertion:

We allocate exactly one node
We write exactly two pointer values (newNode.next and head)
We access exactly one existing pointer (the current head)

None of these counts depend on n (the list length). Whether n = 5 or n = 5,000,000, we perform the same operations.

What we DON'T do:

We don't traverse the list
We don't look at any nodes besides head
We don't move or copy any existing data
We don't allocate space proportional to n

Memory visualization:

Before insertion, the list occupies certain memory addresses:

Address 1000: Node{data: A, next: 2000}
Address 2000: Node{data: B, next: 3000}
Address 3000: Node{data: C, next: null}
head = 1000

After inserting X at head:

Address 1000: Node{data: A, next: 2000}  ← UNCHANGED
Address 2000: Node{data: B, next: 3000}  ← UNCHANGED
Address 3000: Node{data: C, next: null}  ← UNCHANGED
Address 4000: Node{data: X, next: 1000}  ← NEW NODE
head = 4000  ← UPDATED

Only the new node and head pointer changed. All existing nodes are in their original locations with their original data.

Head Insertion Cost Breakdown
Operation	Cost	Depends on n?
Allocate new node	O(1)	No
Write newNode.data	O(1)	No
Write newNode.next	O(1)	No
Read current head value	O(1)	No
Write new head value	O(1)	No
TOTAL	O(1)	No

The Key Insight

Head insertion is O(1) because pointers provide indirection. Instead of physically placing the new element first (which would require moving everything), we change what 'first' points to. The chain adapts instantly through pointer manipulation.

Comparison with Array Front Insertion

To appreciate linked list head insertion, let's examine what arrays must do for the same operation.

Array front insertion:

Starting with array [A, B, C, _, _] (5 slots, 3 used):

Index:    0   1   2   3   4
Values: [ A | B | C | _ | _ ]

To insert X at front:

Step 1: Shift all elements right

Index:    0   1   2   3   4
Values: [ A | A | B | C | _ ]  ← copy index 2 to 3
Values: [ A | A | B | C | _ ]  ← copy index 1 to 2
Values: [ A | A | B | C | _ ]  ← copy index 0 to 1

Step 2: Write new element at index 0

Index:    0   1   2   3   4
Values: [ X | A | B | C | _ ]

We touched every single element. For an array of n elements, we perform n copies.

array-insert-front.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Array front insertion: O(n)
function arrayInsertAtFront<T>(arr: T[], value: T): T[] {
    // Option 1: Using unshift (still O(n) internally)
    arr.unshift(value);
    return arr;
    
    // Option 2: Manual implementation showing the work
    // const result = new Array(arr.length + 1);
    // result[0] = value;
    // for (let i = 0; i < arr.length; i++) {
    //     result[i + 1] = arr[i];  // Copy each element
    // }
    // return result;
}
 
// Time: O(n) — must shift/copy all n elements
// Space: O(1) for in-place, O(n) if creating new array

Linked List: O(1)

•Create one new node
•Update two pointers
•Existing nodes untouched
•Same cost for n=10 or n=10M
•No data movement at all

Array: O(n)

•Shift all n elements right
•n copy operations required
•Every element moves in memory
•10M elements = 10M copies
•Cache lines invalidated

Practical impact:

For an array of 1 million integers (4 MB of data), inserting at the front requires copying 4 MB. On a modern system writing ~10 GB/s, that's ~0.4 ms per insertion. 10 front insertions = 4 ms. 1000 front insertions = 400 ms.

For a linked list, 1000 front insertions take ~1000 × (a few nanoseconds) ≈ microseconds total.

The difference can be 1000x or more!

Language Abstractions Hide Costs

In JavaScript, arr.unshift(x) looks as simple as linked list insertion. But internally, it's O(n). Always understand the time complexity behind convenient methods.

Implementation Patterns and Variations

Let's explore different ways to implement and organize head insertion, each with its trade-offs.

Pattern 1: Function returning new head

The functional approach—the function doesn't modify state, just returns the new structure:

functional-insert.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Pure function: returns new head, caller updates their reference
function insertAtHead<T>(
    head: ListNode<T> | null, 
    value: T
): ListNode<T> {
    const newNode = new ListNode(value);
    newNode.next = head;
    return newNode;
}
 
// Usage
let list = null;
list = insertAtHead(list, 1);  // Caller must reassign
list = insertAtHead(list, 2);

Pattern 2: Class-based with encapsulated head

The object-oriented approach—the class manages the head internally:

class-based-insert.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 LinkedList<T> {
    private head: ListNode<T> | null = null;
    private _size: number = 0;
    
    insertAtHead(value: T): void {
        const newNode = new ListNode(value);
        newNode.next = this.head;
        this.head = newNode;
        this._size++;
    }
    
    get size(): number {
        return this._size;
    }
    
    getHead(): ListNode<T> | null {
        return this.head;
    }
}
 
// Usage
const list = new LinkedList<number>();
list.insertAtHead(1);
list.insertAtHead(2);
console.log(list.size);  // 2

Pattern 3: With size tracking

Maintaining a size counter adds O(1) overhead but enables O(1) size queries:

insert-with-size.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class SizedLinkedList<T> {
    head: ListNode<T> | null = null;
    size: number = 0;
    
    insertAtHead(value: T): void {
        const newNode = new ListNode(value);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;  // O(1) increment
    }
    
    removeFromHead(): T | null {
        if (this.head === null) return null;
        
        const value = this.head.data;
        this.head = this.head.next;
        this.size--;  // Maintain invariant
        return value;
    }
}
 
// Without size tracking, getting length requires O(n) traversal

Pattern 4: Sentinel/Dummy node

A sentinel (dummy head) eliminates edge cases for empty list handling:

sentinel-insert.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 SentinelLinkedList<T> {
    // Dummy node that's always present
    // Real data starts at sentinel.next
    private sentinel: ListNode<T>;
    
    constructor() {
        this.sentinel = new ListNode(null as T);  // Dummy value
    }
    
    insertAtFront(value: T): void {
        const newNode = new ListNode(value);
        newNode.next = this.sentinel.next;
        this.sentinel.next = newNode;
        // No special case for empty list!
    }
    
    isEmpty(): boolean {
        return this.sentinel.next === null;
    }
    
    getFirstNode(): ListNode<T> | null {
        return this.sentinel.next;
    }
}

Choose Based on Use Case

Functional style is cleanest for immutable designs. Class-based is better for mutable structures with multiple operations. Sentinel nodes simplify code when you frequently insert/delete. Track size only if you frequently query it; otherwise it's unnecessary overhead.

Common Bugs and Edge Cases

Head insertion seems trivial, but subtle bugs can cause serious problems. Let's examine the most common mistakes.

Bug 1: Forgetting to update head

bug-no-update.ts
1
2
3
4
5
6
7
8
9
10
// ❌ BUG: Head never updated
function insertAtHeadBroken<T>(head: ListNode<T> | null, value: T): void {
    const newNode = new ListNode(value);
    newNode.next = head;
    // Forgot to return or update head!
    // The new node is created but becomes garbage
}
 
// The caller's 'head' still points to old first node
// New node is unreachable

Bug 2: Wrong order of operations

bug-wrong-order.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ❌ BUG: Update head before linking
function insertAtHeadBroken2<T>(
    list: { head: ListNode<T> | null }, 
    value: T
): void {
    const newNode = new ListNode(value);
    list.head = newNode;        // Updated head first!
    newNode.next = list.head;   // Now newNode.next points to itself!
    // Infinite loop: newNode → newNode → newNode → ...
    // Rest of list is lost!
}
 
// ✅ CORRECT: Link before updating head
function insertAtHeadCorrect<T>(
    list: { head: ListNode<T> | null }, 
    value: T
): void {
    const newNode = new ListNode(value);
    newNode.next = list.head;   // Save link to rest of list first
    list.head = newNode;        // Now safe to update head
}

Bug 3: Not handling the return value

bug-ignored-return.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertAtHead<T>(
    head: ListNode<T> | null, 
    value: T
): ListNode<T> {
    const newNode = new ListNode(value);
    newNode.next = head;
    return newNode;
}
 
// ❌ BUG: Ignoring return value
let myList: ListNode<number> | null = null;
insertAtHead(myList, 1);  // Return value ignored!
insertAtHead(myList, 2);  // myList is still null
 
// ✅ CORRECT: Capture return value
myList = insertAtHead(myList, 1);
myList = insertAtHead(myList, 2);

Edge case: Empty list insertion

empty-list-insert.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Empty list case works naturally
function insertAtHead<T>(
    head: ListNode<T> | null, 
    value: T
): ListNode<T> {
    const newNode = new ListNode(value);
    newNode.next = head;  // head is null → newNode.next is null
    return newNode;       // Return single-node list
}
 
// The same code handles:
// - Empty list: null → [X]
// - Single element: [A] → [X, A]
// - Multiple elements: [A, B, C] → [X, A, B, C]

These Bugs Cause Silent Data Loss

Unlike crashes that are immediately obvious, pointer bugs can cause silent data corruption. The list appears to work, but data is slowly being lost. Always test insertions thoroughly, especially at boundaries (empty list, single element).

Head Insertion in Stack Implementation

The most natural use of O(1) head insertion is implementing a stack. A stack's push operation adds to the top—exactly what head insertion does.

Stack using linked list:

linked-stack.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
class Stack<T> {
    private head: ListNode<T> | null = null;
    private _size: number = 0;
    
    // Push = insert at head → O(1)
    push(value: T): void {
        const newNode = new ListNode(value);
        newNode.next = this.head;
        this.head = newNode;
        this._size++;
    }
    
    // Pop = remove from head → O(1)
    pop(): T | undefined {
        if (this.head === null) return undefined;
        
        const value = this.head.data;
        this.head = this.head.next;
        this._size--;
        return value;
    }
    
    // Peek = read head → O(1)
    peek(): T | undefined {
        return this.head?.data;
    }
    
    isEmpty(): boolean {
        return this.head === null;
    }
    
    get size(): number {
        return this._size;
    }
}
 
// Usage
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());   // 3
console.log(stack.peek());  // 2
console.log(stack.size);    // 2

All core stack operations are O(1):

Operation	Implementation	Complexity
push	Insert at head	O(1)
pop	Remove from head	O(1)
peek	Read head.data	O(1)
isEmpty	Check head === null	O(1)

This is why linked lists are often the preferred stack implementation when maximum size is unknown. Unlike array-based stacks that occasionally resize (amortized O(1) but with occasional O(n) spikes), linked list stacks are truly O(1) per operation.

Stack Analogy: The Plate Stack

Think of stacking plates: you always add to the top (push = head insert) and take from the top (pop = head remove). You never need to access plates in the middle. This is exactly the linked list head operations.

Building Lists Efficiently with Head Insertion

When constructing a linked list from a sequence of values, head insertion is O(1) per element, making it O(n) total to build n elements. However, there's a catch: the resulting order is reversed.

Forward iteration + head insertion = reversed list:

build-reversed.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Build list from array [1, 2, 3, 4, 5]
function buildFromArrayReversed(arr: number[]): ListNode<number> | null {
    let head: ListNode<number> | null = null;
    
    for (const value of arr) {
        head = insertAtHead(head, value);
    }
    
    return head;
}
 
const result = buildFromArrayReversed([1, 2, 3, 4, 5]);
// Result: 5 → 4 → 3 → 2 → 1 → null
// The list is REVERSED because we kept adding to front

Three strategies for correct order:

Strategy 1: Iterate in reverse

build-strategy-1.ts
1
2
3
4
5
6
7
8
9
10
11
12
function buildFromArrayCorrect1(arr: number[]): ListNode<number> | null {
    let head: ListNode<number> | null = null;
    
    // Iterate backwards
    for (let i = arr.length - 1; i >= 0; i--) {
        head = insertAtHead(head, arr[i]);
    }
    
    return head;
}
 
// [1, 2, 3, 4, 5] → insert 5, 4, 3, 2, 1 → list: 1 → 2 → 3 → 4 → 5

Strategy 2: Use tail insertion (requires tail pointer)

build-strategy-2.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function buildFromArrayWithTail(arr: number[]): ListNode<number> | null {
    if (arr.length === 0) return null;
    
    const head = new ListNode(arr[0]);
    let tail = head;
    
    for (let i = 1; i < arr.length; i++) {
        tail.next = new ListNode(arr[i]);
        tail = tail.next;
    }
    
    return head;
}
 
// Insert at tail = O(1) if we track tail pointer
// Total: O(n), correct order

Strategy 3: Build reversed, then reverse the result

build-strategy-3.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
function reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
    let prev: ListNode<T> | null = null;
    let current = head;
    
    while (current !== null) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}
 
function buildFromArrayCorrect3(arr: number[]): ListNode<number> | null {
    // Build reversed: O(n)
    let head: ListNode<number> | null = null;
    for (const value of arr) {
        head = insertAtHead(head, value);
    }
    
    // Reverse: O(n)
    return reverse(head);
    // Total: O(2n) = O(n)
}

Choose the Right Strategy

Strategy 2 (tail pointer) is usually best—single pass, correct order. Strategy 1 works when you can iterate backward. Strategy 3 is useful when you're building the list as data arrives (can't iterate backward) and don't want to track a tail.

Summary: Mastering Head Insertion

We've thoroughly explored head insertion—the operation that demonstrates linked lists' key advantage. Let's consolidate the essential insights:

Key Takeaways

•Head insertion is O(1) — Create node, set next to current head, update head. Three constant-time operations regardless of list size.
•Array front insertion is O(n) — Every element must shift. Linked lists are dramatically faster for front insertions.
•Order of operations is critical — Always link the new node to the rest of the list BEFORE updating head. Violating this loses data.
•Perfect for stacks — Push and pop map directly to head insert and remove. All O(1), no amortized costs.
•Building preserves reverse — Iterating forward with head insertion produces reversed order. Plan accordingly.
•Sentinel nodes simplify code — A dummy head eliminates special cases for empty lists.

What's next:

Head insertion is O(1), but what about tail insertion? The story is more nuanced: it depends on whether we maintain a tail pointer. Next page: Insertion at Tail: O(1) with tail pointer, O(n) without.

Page Complete

You've mastered head insertion—the operation that makes linked lists shine for certain use cases. This O(1) insertion capability is why linked lists power stacks, undo systems, and append-heavy workloads. Next, we'll see how tail insertion introduces interesting trade-offs.