Experiments and implementations · Intermediate

Measuring array and linked-list traversal

Sum equal data in a packed array and a node chain, separating measured traversal from Python-specific implementation costs.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Traverse equal data in equal order
  2. Do not equate a Python list with packed integers
  3. Time after constructing both representations
  4. Vary size without changing the question silently
  5. Add separate observations for cache claims
  6. Report the complete scope
  7. Ask Logeia about this articleCheck your understanding

Traverse equal data in equal order

Both an array traversal and a linked traversal require linear work to read every one of n elements. That does not imply identical elapsed time. Store the integers zero through 9,999 in a packed array and in a chain of nodes with next references. Both functions compute the same sum in the same order and compare it with n times n minus one divided by two. Establish equal answers before timing, then exclude construction from the traversal measurement. The experiment is intended to separate asymptotic work, representation and language-runtime operations, not to infer a universal speed ratio from one pair of timings.

Do not equate a Python list with packed integers

An ordinary Python list generally stores references to Python objects rather than a packed sequence of machine integers. This example chooses array for the packed representation, but reading values in a Python loop still involves interpreter work. Each linked node is a small custom object containing a value and next reference. The program does not control the allocator’s physical placement of those nodes. A timing difference therefore cannot be attributed entirely to cache misses. A low-level-language comparison of contiguous machine integers and pointer-linked nodes would have different conditions, even when the high-level traversal description looks the same.

Time after constructing both representations

The program builds both structures, checks correctness and then records five traversal samples for each function using perf_counter differences. Keep the variation rather than selecting a convenient single result. Result assertions occur inside the measured interval; a stricter benchmark would need a consistent decision about that validation overhead. Construction and destruction are outside the displayed traversal samples and must not later be described as included. Both timed functions execute Python-level loops with different operations. Record those implementation differences when interpreting the measurements, because a clean timing boundary does not by itself make all other aspects of two workloads identical.

Python 3
from array import array
from time import perf_counter
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next_node=None):
        self.value, self.next = value, next_node
n = 10000
packed = array("q", range(n))
head = None
for value in reversed(range(n)):
    head = Node(value, head)
def packed_sum():
    total = 0
    for value in packed:
        total += value
    return total
def linked_sum():
    total, node = 0, head
    while node is not None:
        total += node.value
        node = node.next
    return total
expected = n * (n - 1) // 2
for fn in (packed_sum, linked_sum):
    assert fn() == expected
    samples = []
    for _ in range(5):
        start = perf_counter()
        assert fn() == expected
        samples.append(perf_counter() - start)
    print(fn.__name__, samples)

Vary size without changing the question silently

Try one thousand, ten thousand and one hundred thousand elements while checking the expected sum each time. Very small samples can emphasize timer and call overhead, while larger ones may encounter different cache and bandwidth behavior. If allocation order or link order is changed, record it as another experimental condition. Efficient insertion at an already known position and the cost of traversing from the head are separate properties. A traversal result alone does not rank the structures for every workload. Choose sizes that fit the machine and retain correctness assertions so an accidental partial traversal cannot appear as a performance improvement.

Add separate observations for cache claims

Contiguous elements can make spatial locality useful, whereas a linked traversal depends on reading a reference before finding the following node. These mechanisms motivate further investigation, but elapsed time alone does not measure cache misses or CPU stall cycles. A lower-level explanation may require supported performance counters and carefully matched low-level implementations. The current program changes loop operations, integer representation and object management as well as layout. Describe it as a comparison of these two complete Python representations. Do not claim that cache behavior was isolated while all other work was held constant, because the code does not establish that condition.

Report the complete scope

A report should state Python version, element count, five samples, exclusion of construction and equality of the sums. Even if one representation is faster locally, do not turn the ratio into a universal constant. Workloads with frequent updates, insertion at known nodes or indexed access require different combinations of operations. Choose a representation by considering reading, mutation, search and memory demand together. This experiment contributes an observation about full traversal in two specific Python implementations. It is useful precisely because its scope is explicit, rather than because it supplies a context-free verdict that arrays or linked structures are always preferable.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 8

Prepare for AI systems · STEP 5

Choose a learning path