Arrays vs Linked Lists: The Real Difference Most Interview Prep Misses

Question

It took an LRU Cache interview for me to realise the complexity table wasn't answering the real question.

I'd been picking between arrays and linked lists for years before realising the table wasn't the answer to the question.

Then LRU Cache came up in an interview, and the table didn't help: both structures were on the page, neither alone solved the problem, and the silence ran nine minutes before the interviewer gave a hint.

What I figured out

• Arrays and linked lists differ for one reason: contiguous memory vs scattered memory. Every entry on the complexity table follows from that single fact.
• Two O(n) operations aren't equal in practice. An array scan of a million integers runs roughly an order of magnitude faster than the equivalent linked list traversal because of CPU cache locality.
• The "O(1) insertion" claim about linked lists comes with a hidden prerequisite: the algorithm has to already hold a pointer to the position. Find it first, and you've paid O(n) before the insertion runs.
• Many interesting interview problems combine both structures rather than picking one. LRU Cache is the canonical case.

Where the table stopped working

For a long time the table was the decision tree.

The problem mentioned "insert" or "delete," reach for a linked list. The problem mentioned "access by index," reach for an array.

That worked on simple problems.

It fell apart on anything that needed both behaviours.

The specific moment was sitting in front of LRU Cache.

The problem wants get(key) and put(key, value) both in O(1) average time, with eviction of the least recently used entry when the cache is full.

A hash map handles the lookup half, since get has to be O(1) and a hash map is the obvious answer.

Then comes the recency tracking, which means some kind of ordering on the entries.

An array of (key, timestamp) pairs would mean updating timestamps on access, and the eviction step turns into a linear scan for the smallest timestamp.

That breaks the O(1) requirement.

Switch to a linked list and inserting at the front on every access is O(1) given a pointer to the node.

To find the node from a key, the algorithm walks the list, which is O(n).

The hash map gives O(1) lookups but no reordering.

The linked list gives O(1) reordering but no fast lookup.

The problem wasn't picking the wrong structure.

The problem was thinking the question had only two answers.

The realisation that broke the table

The fix sounds obvious in retrospect:

Keep both.

A hash map mapping keys to linked list nodes, and a doubly linked list whose nodes store the values and recency order.

The hash map gives O(1) access to the exact node.

Once the algorithm has the node, the linked list reorders without traversing in O(1).

Eviction becomes removing the tail node, which is also O(1) because a tail pointer is maintained.

The two structures aren't competing.

They're solving different sub-problems.

The hash map handles constant-time access.

The linked list handles pointer reassignment at known positions.

The qualifier on linked list insertion:

"O(1) only if you already hold the pointer"

finally has a structure feeding it those pointers for free.

That's the same property powering a handful of linked list patterns that previously read like tricks: reversal, splitting, merging, fast and slow pointers.

That's the realisation that broke the table.

The table had been answering:

“If you pick exactly one structure, which one wins?”

The interesting problems were asking a different question:

“Which combination of memory layouts gives every operation in the algorithm the access pattern it needs?”

What it looks like in code

Here's the construction the technique walkthrough lands on:

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.lookup = {}                  # hash map: key -> Node
        self.head = Node(0, 0)           # sentinel
        self.tail = Node(0, 0)           # sentinel
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.lookup:
            return -1

        node = self.lookup[key]          # O(1) via hash map
        self._remove(node)               # O(1) via direct pointer
        self._add_front(node)            # O(1) splice at head

        return node.value

    def put(self, key, value):
        if key in self.lookup:
            self._remove(self.lookup[key])

        node = Node(key, value)
        self.lookup[key] = node
        self._add_front(node)

        if len(self.lookup) > self.capacity:
            lru = self.tail.prev         # O(1) via tail sentinel
            self._remove(lru)
            del self.lookup[lru.key]

Every operation is O(1).

The hash map carries the lookup load.

The doubly linked list carries the ordering load.

Each structure does the thing it's actually good at, and the combination handles a problem neither could solve alone.

What I'd tell my earlier self

The contrast between the old picking heuristic and the current one comes out cleanest side by side:

Then	Now
Match keywords in the prompt ("insert" → linked list) to the table.	Identify every operation the algorithm performs and check whether each one already has the pointer or index it needs.
Treat arrays and linked lists as competing answers.	Treat them as primitives that combine.
Quote O(1) insertion for linked lists without the qualifier.	Read "O(1) insertion" as "O(1) once you've paid for the pointer."
Trust two O(n) operations as equivalent in practice.	Account for cache locality. Array scans often beat linked list traversals in real hardware.

And three rules that would've shortened the loop:

1. Identify the dominant operation first. Before picking a structure, write down the access pattern the algorithm needs. "Lookup by key, then mutate at that position" is a different question than "lookup by key, then iterate from there."

2. Check the qualifier on every linked list insertion claim. Does the algorithm already hold the pointer, or does it have to walk to find it? If it has to walk, the advantage is gone.

3. When two structures each solve half the problem, try combining them. That's the move that handles LRU Cache, caching problems, and most eviction-style systems.

I wrote a longer version on Codeintuition that walks the same memory-layout reasoning through stacks, queues, and graph adjacency representations.

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 was the moment a data structure choice finally clicked for you, where the textbook framing had been hiding the actual question?