Arrays vs Linked Lists: The O(1) Insertion Myth

You read "linked lists give O(1) insertion" and reach for one the next time a problem says "insert." Forty minutes later, your solution is technically O(n) and you're not sure where the advantage went.

The complexity table told you something true. It just left out the qualifier that decides whether the truth applies to your problem.

Key takeaways

• The "O(1) insertion" claim about linked lists comes with a hidden prerequisite: you must already hold a pointer to the position where you're inserting.

• If your algorithm has to find the position first, you pay an O(n) traversal before the O(1) insertion. Total cost is O(n), same as an array shift.

• Memory layout (contiguous vs scattered) is the single fact that explains every entry in the complexity table.

• Linked list insertion isn't constant time. It's constant time once you've paid the traversal cost.

• The right question on any problem isn't "what's the Big-O?" It's "does my algorithm already hold the pointer it needs?"

The qualifier the table omits

The standard table tells you arrays are O(1) for index access and O(n) for arbitrary insertion. Linked lists are the inverse: O(n) for index access and O(1) for insertion. Both halves are correct as written.

The half about linked list insertion is a partial truth.

The full claim is: a linked list inserts a new node in O(1) given a pointer to the node before the insertion point. The qualifier matters because most algorithms don't start with that pointer. Most algorithms start with an index, a value, or a key. Reaching the position from any of those starting points means walking the list, which is O(n).

Once you internalise the qualifier, you stop reaching for linked lists on every problem that mentions "insert." You start asking a different question first:

Do I already hold a pointer?

What insertion actually costs in a linked list

Let me walk through the mechanics so the qualifier feels concrete.

A linked list node holds a value and a pointer to the next node. Inserting a new node at a known position is three operations:

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def insert_after(prev_node, value):
    """Insert a new node after prev_node. O(1) if you already have prev_node."""
    new_node = Node(value)
    new_node.next = prev_node.next
    prev_node.next = new_node

Three lines. No loop. Constant time.

This is the claim the table is referencing.

The catch sits in the function signature. insert_after requires prev_node, which is a pointer to a specific node already inside the list. If your caller doesn't have that pointer, the caller has to find the node first:

def insert_at_index(head, index, value):
    """Insert a new node at the given index. O(n) total."""
    if index == 0:
        return Node(value, next=head)

    prev = head
    for _ in range(index - 1):
        prev = prev.next     # O(n) traversal to reach the position

    insert_after(prev, value)  # O(1) insertion, but only the last step
    return head

The for loop is the part the table doesn't mention. It runs in O(n).

The O(1) insertion at the end is real, but it's the last 1% of the work.

Total cost is O(n).

Same complexity class as shifting an array, with worse constants because the traversal bounces between scattered memory addresses and an array shift rides on the CPU cache.

This is the part of the table that most engineers skip past on the first read and then run into during a real problem.

A worked example: insert at index k

Imagine an interview problem: maintain a sorted sequence of integers and insert new values in order. You're given an integer stream, one at a time, and the structure has to stay sorted after each insertion.

Reach for a linked list because "insertion is O(1)" and the per insert cost looks like this:

1. Start at the head.

2. Walk forward while the current node's value is less than the new value. This is O(n) in the worst case.

3. Stop at the position where the new value belongs.

4. Splice the new node in. This is O(1).

Total per insert: O(n)

Reach for a sorted array (or a dynamic array kept sorted) and the per insert cost looks like this:

1. Binary search for the insertion index. This is O(log n).

2. Shift every element from that index onward one position right. This is O(n) in the worst case.

Total per insert: O(n)

Same Big-O. Different constants.

The array version often wins in practice because the binary search and the shift are both cache friendly: contiguous memory, predictable access pattern, prefetcher does meaningful work.

The linked list version pays a cache miss per pointer chase across the entire traversal.

The "right" answer for streaming sorted insertion in a real interview is usually neither. It's a balanced binary search tree (which is O(log n) per insert) or a heap if order doesn't matter.

The point of the example isn't that one beats the other.

It's that the linked list looked like a free lunch when read off the table and it wasn't.

When pointer based mutation actually pays off

There are real cases where the qualifier holds and the linked list earns its keep.

What's different is the algorithm design.

When linked lists win	Why the qualifier holds
LRU Cache	A hash map maps keys to nodes, so every operation already has the pointer in O(1). The doubly linked list reorders without traversal.
Reverse a segment	The algorithm starts with pointers to the segment's endpoints and only does pointer reassignments. No data movement.
Merge two sorted lists	Both lists supply head pointers, the merge walks them with two pointers and splices. No element copying.
Split a list at a node	The split point is a known pointer. You cut the next link and you have two lists.

What these cases share is that the algorithm itself gives you the pointer for free.

You're not searching for the position.

The structure of the problem hands it to you.

That's the only situation where the linked list's O(1) insertion is the actual cost you pay.

The most frequent mistake I watch is the inverse: someone reads "linked list = O(1) insert" and assumes that means insertion is fast in any context, including ones where they have to find the insertion point first.

The table didn't lie.

The reader skipped the prerequisite.

Picking from first principles

Once you stop trusting the table and start trusting the underlying memory layout, picking between an array and a linked list collapses into a small protocol you can run on any problem:

1. Identify the dominant operation. Is the algorithm mostly accessing by index, mostly mutating at known positions, mostly scanning, or some mix?

2. Check whether your algorithm holds direct pointers to its mutation points. If yes, a linked list is on the table. If no, the linked list's insertion advantage doesn't apply and you should default to an array.

3. Account for cache locality on full scans. Two O(n)s aren't equal. An array scan rides the CPU cache. A linked list scan pays a cache miss per node. On algorithms that scan the whole structure repeatedly, the array's constant factor dominates.

4. Consider whether you need both random access and pointer based mutation. That combo is what LRU Cache solves with a hash map plus doubly linked list. Neither structure alone is enough.

5. Default to an array if you're uncertain. Most interview problems involving a sequence land on an array, a hash map, or a hash map plus linked list combo. Pure linked list problems are rarer than the table makes them feel.

The same memory level reasoning extends to stacks (array backed vs linked list backed), queues (circular array vs linked list), trees (array representation vs node based), and graphs (adjacency matrix vs adjacency list).

Each of those choices is the same tradeoff with a different shape on top.

Originally posted on my blog, with cache locality benchmarks and a deeper walkthrough of when linked lists actually outperform arrays.

If you want a deeper walkthrough of pointer-based mutation patterns, the singly linked list course on codeintuition covers seven of them with worked examples.

What's a problem where you reached for a linked list because the Big-O looked good, and only realised mid implementation that you'd skipped the qualifier?