CodeLudo 🔥 Daily Guides

Array or Linked List? Score the Workload, Not the Table

✓ numbers produced by the code on this page · Published 2026-08-19

Everyone learns the table. An array indexes in constant time and inserts at the front in linear time; a linked list is the other way round. It is correct, it is memorable, and it does not answer the question anyone actually has, which is which one should I use here.

The reason is that the table compares operations and real code runs a mixture of them. Whichever structure wins is a property of the workload, not of the structure. So rather than compare rows, score a program.

Two workloads, same data, opposite winners

Fire operations one at a time and watch both totals. The highlighted cells are the ones that structure had to touch to do the work.

Score a workload same operations, opposite costs

An array and a singly linked list can hold exactly the same 7 values — 10, 20, 30, 40, 50, 60, 70 — and charge wildly different prices for the same work. The array can jump straight to any position but has to shift every element to make room at the front. The list can splice a new item onto the front by moving one pointer, but has to walk from the head to reach position 5.

Two workloads, counted in element touches. Leaderboard — appending scores and reading positions — costs the array 8 steps and the list 27. Task queue — pushing and popping the front — costs the array 62 steps and the list 8. Neither structure is faster. The workload decides, which is why the textbook table can be memorised and still not answer the question.

One step = one element touched: a slot read, a slot written, or one node hop. Try each preset workload, then Reset and try the other.

Press Leaderboard and the array wins comfortably. Press Task queue and the linked list wins by more. Same seven starting values, same two structures, opposite conclusions — and nothing changed except which operations were asked for.

Why the costs move in opposite directions

An array is a single contiguous run of memory, so the address of item k is arithmetic: start plus k times element size. It never looks at the items in between. That is why reading position 6 costs one step no matter how long the array is.

The price is that “contiguous” is a promise the array has to keep. Inserting at the front means every existing element moves up one slot to open a gap, so the cost is the length of the array.

A linked list makes the opposite trade. Each node stores its value plus the address of the next node, so nothing is adjacent to anything and there is no arithmetic to exploit — reaching position 6 means starting at the head and following six pointers. But inserting at the front rewrites exactly one pointer, whatever the length.

Neither is a better structure. They are two different answers to what should be cheap.

The same scoring, as a program

This is the cost model the widget uses, written out. The numbers below are the same ones the two preset buttons produce.

python 
def costs(n, op):
    """Element touches for one operation on a list of length n.

    Array: has spare capacity, so append is one write. Indexing is address arithmetic.
    Linked list: singly linked, with a head AND a tail pointer.
    """
    kind, arg = op
    if kind == "read":
        return 1, arg + 1          # array jumps; list walks from the head
    if kind == "append":
        return 1, 1                # spare capacity vs a tail pointer
    if kind == "prepend":
        return n + 1, 1            # shift everything vs move one pointer
    if kind == "remove_first":
        return max(n - 1, 0), min(n, 1)
    raise ValueError(kind)


def apply(n, op):
    kind, _ = op
    if kind == "append" or kind == "prepend":
        return n + 1
    if kind == "remove_first":
        return max(n - 1, 0)
    return n


def run(start_len, ops):
    n, array, linked = start_len, 0, 0
    for op in ops:
        a, l = costs(n, op)
        array += a
        linked += l
        n = apply(n, op)
    return array, linked


LEADERBOARD = [("read", 2), ("read", 5), ("append", 90), ("read", 1),
               ("read", 5), ("append", 95), ("read", 6), ("read", 0)]

TASK_QUEUE = [("prepend", 71), ("remove_first", None), ("prepend", 72), ("prepend", 73),
              ("remove_first", None), ("remove_first", None), ("prepend", 74), ("remove_first", None)]

print(f"{'workload':<12} {'array':>6} {'list':>6}   winner")
for name, ops in [("Leaderboard", LEADERBOARD), ("Task queue", TASK_QUEUE)]:
    array, linked = run(7, ops)
    winner = "array" if array < linked else "list"
    ratio = max(array, linked) / min(array, linked)
    print(f"{name:<12} {array:>6} {linked:>6}   {winner}, {ratio:.1f}x cheaper")
Output 
workload      array   list   winner
Leaderboard       8     27   array, 3.4x cheaper
Task queue       62      8   list, 7.8x cheaper

Change the workloads and run it again. That is the exercise — not learning which structure is faster, but learning to look at what the code does before deciding.

What the model leaves out, and why it matters

The step counts above are honest about work done and silent about time taken, and the gap between those two is larger than beginners are usually told.

Arrays are much faster in practice than their step counts suggest, because a contiguous run of memory is exactly what CPU caches are built for. Walking an array pulls neighbouring elements into cache for free; walking a linked list chases pointers to addresses that may be anywhere, and each hop can be a cache miss costing far more than the “one step” this page charges it.

That is why the practical advice in most languages leans harder toward arrays than the table does. Python’s list, JavaScript’s Array, Java’s ArrayList, C++‘s vector and Go’s slices are all array-backed, and a linked list is the specialised choice you reach for deliberately.

What this page simplifies