Array vs Linked List: When O(1) Insert Is a Lie

Array vs linked list in one line: an array keeps items side by side, so reading index k is one step but inserting shifts the tail; a linked list chains nodes by pointers, so inserting is two pointer writes but only once you are standing at the right node. Most comparison charts print "linked list insert: O(1)" and stop there. That number is true for a narrow case and misleading for the one people usually mean, "insert at position k".

Operation	Array (Python list)	Singly linked list
Read index k	O(1), one address calculation	O(k), follow k links
Insert at index k	O(n - k) shifts	O(k) walk, then O(1) splice
Insert next to a node you hold	still O(n - k)	O(1), the honest case
Scan everything	O(n), contiguous, cache-friendly	O(n), one pointer chase per node

The problem it solves

"Array or linked list?" tests whether you know what each operation actually pays for. The trap is comparing the splice of one against the shift of the other. A fair comparison counts everything from the moment you are handed an index, including finding the spot.

The singly linked list article builds the structure, and linked list insertion and deletion covers the splice and its write order. Here the question is narrower: when does the cheap insert really beat the array?

The intuition

An array is a row of numbered lockers. Locker k is at base + k × size, so any locker is one step away. Inserting into locker k means every item from k onwards moves one locker to the right. The arrays article shows how a dynamic array keeps append cheap by doubling.

A linked list has no numbers on anything. Each node knows only where the next one lives. Splicing a new node in is two writes: point the new node at the successor, then point the predecessor at the new node. That part really is O(1), for any length.

The catch is the word predecessor. To insert at index k, you need node k - 1, and the only way to reach it is to start at the head and follow k - 1 links. So:

• Insert at index k: array pays n - k shifts, linked list pays k - 1 link-follows. Each is O(n) in the worst case; they are just expensive at opposite ends.
• Insert where you already hold a pointer: the head, a kept tail, or a node you found earlier for another reason. Only here is the linked list's insert O(1) and the array's still a shift.

That is the honest rule: the linked list wins when the position arrives as a pointer, not as a number. An LRU cache is the classic example: a hash map hands you the node directly, and moving it to the front is a splice with no walk.

The other half of the comparison is memory. An array's slots sit next to each other, so the CPU fetches several at once and the next read is usually already in cache. A linked list's nodes live wherever the allocator put them, and every next can be a trip to main memory. Same O(n) scan, very different constant.

Watch it run

The lesson's animation builds a chain one node at a time. Each node is a box with a value and the address of the next box, and the first link is set with head.next = Node(7). More nodes join at scattered spots, so screen position says nothing about order; only the arrows do. Then it asks for items by index: the head costs nothing, every step further adds one link to follow, and the last arrow points at None. That hop count is exactly the cost the "O(1) insert" claim leaves out.

The code

The Node from the singly linked list lesson and two inserts that count their work: link-follows to reach position k, and element shifts the way list.insert(k, x) does them inside, checked against the real list.insert on n = 10,000:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None                   # link to the next node

def build_chain(values):
    head = None
    for v in reversed(values):
        node = Node(v)
        node.next = head
        head = node
    return head

def insert_at(head, k, value):
    """Insert so that `value` ends up at index k. Returns (head, links followed)."""
    node = Node(value)
    if k == 0:
        node.next = head                   # the head is a pointer you already hold
        return node, 0
    prev, hops = head, 0
    for _ in range(k - 1):                 # walk to the node BEFORE position k
        prev = prev.next
        hops += 1
    node.next = prev.next                  # the O(1) part: two pointer writes
    prev.next = node
    return head, hops

def array_insert(arr, k, value):
    """What list.insert(k, x) does inside: shift the tail right by one slot."""
    arr.append(None)
    moves = 0
    for i in range(len(arr) - 1, k, -1):
        arr[i] = arr[i - 1]
        moves += 1
    arr[k] = value
    return moves

n = 10_000
same = True
print("k       follows  shifts")
for k in (0, 1, 2_500, 5_000, 9_999, 10_000):
    _, hops = insert_at(build_chain(list(range(n))), k, -1)
    arr, real = list(range(n)), list(range(n))
    moves = array_insert(arr, k, -1)
    real.insert(k, -1)
    same &= arr == real
    print(f"{k:<7} {hops:<8} {moves}")
print(same)
# k       follows  shifts
# 0       0        10000
# 1       0        9999
# 2500    2499     7500
# 5000    4999     5000
# 9999    9998     1
# 10000   9999     0
# True

At the front the chain does nothing and the array moves all 10,000 items. At the back it is the reverse. In the middle both do about 5,000 units of work. Every row adds up to roughly n: the work did not disappear, it moved.

Now the memory side, on one machine, roughly. A million values summed three ways: a list loop, a chain of nodes allocated one after another, and the same nodes relinked in shuffled order, so each next jumps elsewhere in memory:

import random
import time

def walk(head):
    total, node = 0, head
    while node:                            # one link-follow per element
        total += node.value
        node = node.next
    return total

def timed(f, *args):
    start = time.perf_counter()
    result = f(*args)
    return result, time.perf_counter() - start

def loop_list(values):
    total = 0
    for v in values:                       # contiguous array of references
        total += v
    return total

N = 1_000_000
values = list(range(N))
nodes = [Node(v) for v in values]          # allocated one after another
for a, b in zip(nodes, nodes[1:]):
    a.next = b
s0, t_list = timed(loop_list, values)
s1, t_chain = timed(walk, nodes[0])

random.seed(21)
order = list(range(N))
random.shuffle(order)                      # same nodes, relinked in shuffled order
for a, b in zip(order, order[1:]):
    nodes[a].next = nodes[b]
nodes[order[-1]].next = None
s2, t_scattered = timed(walk, nodes[order[0]])

print(s0 == s1 == s2)                      # True
print(f"list {t_list:.2f} s, chain {t_chain:.2f} s, scattered chain {t_scattered:.2f} s")
# list 0.02 s, chain 0.05 s, scattered chain 0.30 s     (one machine, roughly)

The in-order chain is already slower than the list: each step reads an attribute and follows a pointer. Shuffle the links and the identical walk over the identical nodes takes about six times longer again: same O(n), only the memory access pattern changed. A long-lived linked list looks like the shuffled one.

Finally, a brute-force check: 2,000 inserts at the front, the back and random indexes, run on a list, a collections.deque and the chain (appending through a kept tail). All three must hold the same sequence:

from collections import deque

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

random.seed(2110)
arr, dq = [], deque()
head = tail = None                         # tail: a pointer we keep on purpose
for x in range(2_000):
    kind = random.choice(["front", "back", "index"])
    k = 0 if kind == "front" else len(arr) if kind == "back" else random.randint(0, len(arr))
    arr.insert(k, x)                       # dynamic array: shifts len - k items
    dq.insert(k, x)                        # deque: O(1) at the ends, a walk inside
    if k == len(arr) - 1 and tail:         # appending through the kept tail: 0 follows
        tail.next = Node(x)
        tail = tail.next
    else:
        head, _ = insert_at(head, k, x)    # anywhere else: walk, then splice
        tail = tail or head
print(len(arr), to_list(head) == arr == list(dq))   # 2000 True

The complexity

• Index read: array O(1), linked list O(k).
• Insert or delete at index k: array O(n - k), linked list O(k). Both are O(n) worst case.
• Insert or delete at a held pointer: linked list O(1). For a singly linked list, "held" means the node before the spot; deleting a node you hold needs its predecessor too, which is why LRU caches use a doubly linked list.
• Append: dynamic array amortised O(1); linked list O(1) only with a tail pointer.
• Extra memory: a pointer and, in Python, an object header per node.

Where it goes wrong

• Quoting O(1) insert without the walk. If the position is an index, the walk is part of the cost.
• Forgetting the tail pointer. Without it, appending to a singly linked list is an O(n) walk every time.
• Using list.insert(0, x) as a queue. Every front insert or pop(0) shifts the whole list. collections.deque does both ends in O(1); it is the practical answer in Python.
• Expecting deque to be fast in the middle. Indexing or inserting in the middle of a deque is O(n) too; it is built for the ends.
• Ignoring the constant. Two O(n) scans can differ several times over because of cache locality.

When it shows up in interviews

Directly, as "array or linked list for this workload?". Indirectly, in the LRU cache, which pairs a hash map with a doubly linked list because the map supplies the pointer the list needs, and in queue questions, where the Python answer is deque.

How to say it in an interview

"An array gives O(1) indexing and cache-friendly scans, but inserting at index k shifts n - k elements. A linked list splices in O(1), but only if I already hold the node before the position; inserting at index k means walking k links first, so it is O(n) as well. I pick the linked list when positions arrive as pointers, like an LRU cache where a hash map hands me the node. Otherwise I use the array, and in Python I use deque when I need both ends."

Frequently asked questions

Is linked list insertion really O(1)?

Only the splice is. Once you hold the node before the insertion point, linking a new node is two pointer writes. If you are given an index instead, you first walk k links from the head, so inserting at position k costs O(k), which is O(n) in the worst case.

When should I use a linked list instead of an array?

When you insert or remove at positions you already have pointers to: the head, a kept tail, or nodes another structure hands you, as in an LRU cache. For indexing, scanning or appending, a dynamic array is usually faster because its memory is contiguous.

Is a Python list an array or a linked list?

A Python list is a dynamic array of references: O(1) indexing, amortised O(1) append, O(n) insert or delete at the front. For fast operations at both ends, use collections.deque. Python has no built-in singly linked list; you write the Node class yourself.