Linked Lists vs Arrays — When to Use Which

In the previous page, we explored when linked lists excel. Now we turn to their complement: the scenarios where arrays are not just adequate but definitively superior.

Arrays are the default data structure in nearly every programming language for good reason. Their design aligns naturally with how modern hardware works — contiguous memory, sequential access, and direct addressing. When you understand the criteria that make arrays shine, you'll recognize that they're the right choice for the vast majority of real-world scenarios.

This page will systematically examine when to choose arrays, providing concrete criteria and real-world examples.

This is the defining advantage of arrays: O(1) access by index. If your algorithm requires accessing elements at arbitrary positions, arrays are the only sensible choice.

Why random access is O(1) in arrays:

Arrays store elements contiguously with uniform size. To find element at index i:

address = base_address + (i × element_size)

This calculation requires exactly three machine operations:

1. One multiplication
2. One addition
3. One memory load

The time is constant regardless of array size. Whether you have 10 elements or 10 million, accessing index 7 takes the same time.

Why random access is O(n) in linked lists:

Linked lists have no address formula. To reach index i, you must:

1. Start at head
2. Follow the next pointer
3. Repeat step 2, i times

Each step is a memory access with potential cache miss. Accessing index 7 requires 7 memory accesses. Accessing index 1,000,000 requires 1,000,000 memory accesses.

Example: Binary Search

Binary search is the canonical algorithm that requires random access:

The performance difference:

Searching a sorted collection of 1,000,000 elements:

• Array with binary search: ~20 comparisons, ~20 memory accesses
• Linked list with binary search: ~20 comparisons, but ~10,000,000 aggregate traversal steps
• Linked list with linear search: 500,000 average comparisons and accesses

The linked list "binary search" is worse than linear search! This demonstrates why the combination of binary search and linked lists is fundamentally incompatible.

Algorithms requiring random access:

Counter-intuitively, arrays are also faster for sequential access — the one pattern where linked lists should theoretically be competitive. The reason is cache behavior.

The cache hierarchy advantage:

When you access one array element, the CPU loads an entire cache line (typically 64 bytes) from memory. If your next access is to an adjacent element, it's already in cache — a cache hit that's ~100x faster than a main memory access.

For sequential iteration:

• Array: First element triggers cache line load. Next 7-15 elements (depending on element size) are already cached. Effective memory accesses: ~N/8 to N/16.

• Linked List: Each node triggers a cache line load. Even if the node is small, it's unlikely the next node is in the same cache line (nodes are scattered). Effective memory accesses: ~N.

The result: array iteration can be 8-16x faster than linked list iteration purely due to cache efficiency.

Benchmark reality:

Iterating and summing 1 million 64-bit integers:

• Array: ~0.5-1ms (memory bandwidth limited)
• Linked List (fresh allocation): ~10-50ms (cache friendly initially)
• Linked List (after fragmentation): ~100-500ms (scattered nodes)

The 100-500x slowdown for fragmented linked lists is not theoretical — it's regularly observed in production systems with long-lived linked lists.

When iteration speed matters:

Arrays are dramatically more memory-efficient than linked lists for small to medium-sized elements. This matters for large datasets and memory-constrained environments.

The overhead calculation:

For elements of size S bytes:

• Array: S bytes per element (plus ~16-24 bytes fixed overhead for the array object)
• Singly Linked List: S + 8 bytes per element (next pointer) + ~16 bytes allocator overhead per node
• Doubly Linked List: S + 16 bytes per element (next + prev) + ~16 bytes allocator overhead per node

Memory comparison for common element types:

The crossover point:

As element size increases, the relative overhead decreases. For elements larger than ~200-300 bytes, the overhead becomes negligible. But for primitive types and small structures — which represent the majority of programming scenarios — the overhead is substantial.

When memory efficiency matters critically:

Example: Processing Sensor Data

An IoT system collects temperature readings from thousands of sensors:

• 10,000 sensors reporting every second
• Each reading: timestamp (8 bytes) + sensor_id (4 bytes) + value (4 bytes) = 16 bytes
• 5-minute buffer: 10,000 × 300 seconds × 16 bytes = 48 MB in array
• Same data in singly linked list: 10,000 × 300 × (16 + 8 + 16) = 120 MB

The linked list uses 2.5x more memory — potentially the difference between fitting in RAM and requiring swapping or external storage.

Additional memory considerations:

• Allocator overhead: Linked lists make many small allocations, which stress memory allocators and may cause fragmentation.
• Garbage collection: In GC languages, more objects mean more GC work and longer pause times.
• Virtual memory: Scattered allocations touch more memory pages, increasing working set size.

If your data needs to be sorted — either maintaining sorted order or performing the sorting operation — arrays typically offer significant advantages.

Sorting algorithm efficiency:

The most efficient comparison-based sorting algorithms are designed for arrays:

• Quicksort: Requires random access for partition — O(n log n) average, in-place
• Heapsort: Requires index-based parent/child navigation — O(n log n) worst-case, in-place
• Introsort: Hybrid of the above — used by most standard library sort implementations

Linked lists can be sorted with merge sort in O(n log n), but:

• Merge sort requires O(log n) extra stack space for recursion
• Merge sort cannot take advantage of cache-friendly iteration
• No in-place partitioning scheme exists for linked lists

Maintaining sorted order:

If you need to maintain a sorted collection with frequent insertions:

Despite the same O(n) complexity, sorted array insertion is typically faster in practice because:

1. Binary search to find position is fast (good cache behavior)
2. The shift operation is sequential (cache-friendly)
3. Modern CPUs optimize sequential memory moves

When sorting is critical:

• Databases: Index maintenance requires efficient sorted operations
• Priority systems: Tasks must be processed in priority order
• Leaderboards: Scores must be ranked for display
• Merge operations: Combining sorted data from multiple sources
• Range queries: Finding all elements between bounds

The binary search advantage compounds:

Once data is sorted in an array, many operations become dramatically faster:

• Find element: O(log n)
• Find lower/upper bound: O(log n)
• Count elements in range: O(log n)
• Find k-th smallest: O(1) direct access

None of these optimizations are possible with linked lists, even if sorted.

Arrays are universally supported across programming languages and receive extensive optimization. This practical consideration often tips the scales toward arrays.

Universal array support:

Linked list support varies:

Linked lists exist in standard libraries (std::list in C++, LinkedList in Java), but with caveats:

• Often less optimized than array-based alternatives
• Sometimes explicitly discouraged (C++ Core Guidelines suggest avoiding std::list)
• May lack convenience methods available for arrays
• Generic linked list often less efficient than custom implementation

Example: Standard Library Recommendations

The C++ Core Guidelines state:

"Don't use std::list unless you really need the specific properties of a doubly-linked list. Typically, std::vector is a better choice even when you plan to insert into the middle."

This isn't anti-linked-list bias — it reflects measured performance on modern hardware. The cache efficiency of vectors overwhelms the theoretical insertion advantage of lists for most workloads.

Serialization and storage:

Arrays are naturally serializable:

• Write directly to files or network buffers
• Memory-map files as arrays
• Share between processes via shared memory

Linked lists require pointer translation — each node's pointers are process-specific virtual addresses that become meaningless across process boundaries or storage.

Array performance is more predictable and easier to analyze than linked list performance. This matters for capacity planning, performance optimization, and meeting service level objectives.

Why array performance is predictable:

Why linked list performance is variable:

• Memory layout depends on allocation history: Node positions are determined by allocator decisions over time
• Cache behavior degrades with fragmentation: Fresh lists have reasonable locality; old lists may not
• Allocator latency varies: Each node allocation may have different cost depending on heap state
• Garbage collection impact: Many small objects increase GC overhead unpredictably

Example: Production Service Analysis

Consider analyzing why a service's P99 latency is high:

Array-based service:

• Profile shows time spent in array operations
• Performance is consistent across invocations
• Adding more elements scales linearly with element count
• Optimization path is clear: reduce element count, optimize per-element processing

Linked list-based service:

• Profile shows variable time in "memory access"
• Some invocations are 10x slower than others
• Performance varies based on when data was created
• Investigation reveals cache miss rate varies by list age
• Optimization may require restructuring data lifetimes

The linked list debugging path is more difficult because performance depends on hidden state (memory layout) rather than visible state (data content).

Here is a practical checklist for determining whether arrays are appropriate for your use case. If you can answer "yes" to most of these questions, an array is likely the right choice.

This page has identified the specific scenarios where arrays provide genuine advantages over linked lists. Let's consolidate these criteria:

The mental model:

Arrays are optimized for how modern computers actually work — contiguous memory, cache hierarchies, and sequential access patterns. When your access patterns align with these hardware realities, arrays provide unbeatable performance.

What's next:

We've now examined criteria for both linked lists and arrays. The final page brings everything together with hybrid approaches — data structures that combine the best of both worlds for specialized scenarios.