2.3 Choosing Between Arrays and Linked Lists
After reading Arrays and Linked Lists, use this decision sheet to verify position handles, movement costs, memory layout, and invalidation rules. It supports container choices; it is not a shortcut for memorizing complexities without their assumptions.
State the Comparison Assumptions
Array
Index slots allow direct access; when indices are contiguous, insertion and deletion require shifting suffixes.
Linked list
Nodes maintain order through links; changing a node's link is fast once you have the position handle, but accessing by index requires traversal."Array insertion O(n), linked list insertion O(1)" is only half-stated. The real choice depends on what kind of position the caller has, whether index-based access is needed, how elements are allocated, and which references will become invalid after modification.
Operation Cost Summary
Let the container hold n elements. A read uses 0 ≤ i < n; insertion uses 0 ≤ i ≤ n. The array grows by a fixed factor. Amortized append costs start from an empty array with fixed initial capacity.
| Operation | Dynamic Array | Singly Linked List | Doubly Linked List |
|---|---|---|---|
Read by index i | Θ(1) | Θ(i + 1) | Θ(min(i, n - 1 - i) + 1), requires head and tail handles |
| Unordered value search, worst case | Θ(n) | Θ(n) | Θ(n) |
| Insert at head | Shifts n slots, Θ(n) | With head or sentinel node, Θ(1) | With head or sentinel node, Θ(1) |
| Append to tail | Worst-case Θ(n), amortized Θ(1) | With tail pointer, Θ(1); otherwise Θ(n) | With tail pointer, Θ(1) |
Insert at index i | Θ(n-i+1) without growth; Θ(n) with growth | Locate from head and rewire: Θ(i+1) | Locate from nearer end and rewire: Θ(min(i,n-i)+1) |
| Insert after known predecessor | Arrays lack equivalent stable node handle | Θ(1) | Θ(1) |
| Delete known node | Shifts suffix, worst-case Θ(n) | Requires predecessor; typically cannot delete directly | Θ(1) |
| Delete from tail | No suffix shift; typically Θ(1) | Find predecessor Θ(n) | With tail pointer, Θ(1) |
| Full traversal | Θ(n) | Θ(n) | Θ(n) |
Tail deletion assumes no shrinking; otherwise, include the copy cost. The singly linked list’s indexed-insertion row walks from the head. An implementation with a tail pointer can use a constant-time append path for that endpoint.
This table omits the cost of element destruction, comparison, copying, and allocation itself, which may grow with data size. If element operations are not constant time, multiply the respective operation count by the cost of such operations.
Where Does the Insertion Position Come From?
Where does the insertion position come from?
The caller provides only an integer index
A linked list must traverse to that position. Reaching a position in the middle of a growing list costs Θ(n). Array lookup costs Θ(1), followed by shifting the suffix. Both approaches have asymptotic total costs that may reach Θ(n), actual performance depends on the distribution of insertion positions, the cost of element movement, allocation overhead, and cache behavior.
The caller retains a valid node or iterator for a long time
A linked list can directly modify the link at that position with a cost of Θ(1). In contrast, inserting into an array requires shifting elements and may trigger reallocation, invalidating existing references. This is the classic advantage of linked lists for in-place modifications.
After insertion, frequent indexed reads are still required
Accessing an interior index requires traversal; positions near a known head or tail may still be cheap. The savings from avoiding one move during insertion may be offset by a large number of subsequent reads. Total cost must be evaluated across the full workload, rather than a single operation alone.
Representation and Memory
| Dimension | Dynamic Array | Linked List |
|---|---|---|
| Order Source | Index position in slot | next / previous links |
| Reserved Space | May retain unused capacity | Each node allocated on demand |
| Per-Element Overhead | Typically no node links | Single link for a singly linked list, two for a doubly linked list |
| Allocation Strategy | Single growable buffer | Commonly implemented with node-by-node allocation; memory pooling is also possible |
| Locality | Adjacent slots enable sequential access | Pointer chasing introduces dependency-driven loading |
| Element Representation | May be inlined or stored as a reference | Node payload may be inlined or stored as a reference to an object |
A "demand-based" allocation in linked lists does not necessarily mean lower memory usage. The overhead of node links, object headers, allocator metadata, and alignment can exceed the unused capacity of a dynamic array. The exact byte count depends on the language, implementation, and the element type. There is no universal ratio.
References, Pointers, and Iterator Invalidations
Dynamic Arrays
Distinguish a reference to a slot from a reference to the object stored there. Reallocating a C++ vector invalidates element references, pointers, and iterators; insertion without reallocation still invalidates these handles at or after the insertion point. CPython list growth moves references, so an external Python reference to an object stays valid. An integer index can still be used, but may now identify a different element.
Linked Lists
An API with stable node handles, such as C++ list, preserves existing references and iterators on insertion and invalidates only erased elements’ handles on deletion. Other linked-list APIs differ. Java LinkedList iterators may fail fast after external structural modification. In the Python example, an external reference may keep a detached node alive, but that node can no longer serve as a position in its former list.
Stable handles are a strength of linked lists, but long-term external retention of nodes introduces complexity in lifecycle management. It must be clearly specified in the interface which container owns each node and who is responsible for ceasing usage after deletion.
Caching and Measurement
Array slot positions are adjacent, making sequential scanning naturally exploit spatial locality. In contrast, a linked list's next address depends on the content of the current node, making it difficult for the processor to pre-load entire chains. Node allocation can also introduce additional overhead for objects and the allocator.
This does not yield a fixed "10–100x faster" conclusion. Element size, processor architecture, cache configuration, allocator implementation, runtime environment, and access patterns all influence the outcome. Both traversal methods have the same asymptotic complexity (Θ(n)) so benchmarking is necessary to compare the constant factors in a specific runtime environment.
For deeper insights into hardware-level reasons, refer to Vol. 3: Caching and Memory Hierarchy and Performance Engineering.
Choose for the Workload
| Primary Requirement | Consider First | Still Need to Confirm |
|---|---|---|
| Frequent indexed reads | Dynamic array | Whether sorting must be maintained, and whether frequent head insertions are needed |
| Sequential batch processing | Dynamic array or compact numeric array | Whether elements are values or references, and whether layout is truly contiguous |
| Stack-like behavior (push/pop at end) | Dynamic array | Whether the API provides stable tail operations |
| Queue or double-ended queue | Dedicated deque | Avoid repeatedly shifting array heads; don’t hand-code linked lists |
| Holding node handles with frequent insertions or deletions at fixed positions | Linked list | Node ownership, allocation cost, and read patterns |
| Need stable element addresses or iterators | Linked list or another stable container | Check the specific language’s iterator invalidation rules |
| Fixed size, compact values | Fixed array | Whether size is known at compile time or at creation time |
| Primarily indexed updates with occasional insertions or deletions | Dynamic array | Use load measurements to evaluate performance; avoid structural changes due to single insertions |
"Use a dynamic array as a starting point" is a practical heuristic because tooling and APIs are typically mature. It's not a proof, however. When data scale, update patterns, or stable handle requirements emerge, revisit the choice.
Language Container Mapping
Python
| Task | Container | Description |
|---|---|---|
| General indexed sequence | list | A dynamic reference array in CPython |
| Operations at both ends | collections.deque | Designed for appending and popping at both ends |
| Homogeneous basic values | array.array | Compact, mutable sequence, not a fixed-size array |
| Teaching-node algorithms | Hand-written ListNode | Standard library lacks a general-purpose linked list type |
The official Python list/deque tutorial explicitly states that inserting or deleting at the head of a list requires shifting other elements, and recommends deque for queues.
Java 17+
| Task | Container | Description |
|---|---|---|
| Fixed length | T[] | Native array |
| General List | ArrayList<E> | Constant indexing, amortized constant-time append |
| Double-ended queue / stack | ArrayDeque<E> | Does not accept null |
| Doubly-linked List / Deque | LinkedList<E> | Fast at both ends, but intermediate indexing still requires location |
The fixed expansion factor for ArrayList is not publicly exposed. For LinkedList, add(0, e) is located at a known head end and should not be described as a full linear traversal; any intermediate index still requires explicit positioning.
C++
| Task | Container | Description |
|---|---|---|
| Fixed length | std::array<T, N> | Length is part of the type |
| General contiguous sequence | std::vector<T> | Contiguous elements when T is not bool; growable |
| Double-ended sequence | std::deque<T> | Segmented storage, does not guarantee overall contiguity |
| Single-linked | std::forward_list<T> | Forward iteration only |
| Doubly-linked | std::list<T> | Holds iterators for fixed-point insertion and deletion |
The C++ standard draft's vector modifier and list define conditions for reallocation, iterator invalidation, and fixed-point operations. reserve(n) prevents subsequent insertions from reallocating while their resulting size stays within capacity. It does not change size.
Decision Steps
- List the primary operations and their proportions, such as 90% index reads and 10% append operations at the end.
- Identify the caller’s access pattern: integer indices, node handles, iterators, or just values.
- Add the costs associated with element movement, comparisons, allocations, and output.
- Verify address or iterator stability and ownership constraints.
- First choose a semantically correct and simple container, then benchmark it with representative data.
Quick Corrections
| Statement | Correction |
|---|---|
Linked list insertion is always O(1) | It's only efficient when the predecessor or node is known; Θ(1) |
Inserting into the middle of an array always requires moving n elements | Moving n-i elements at index i |
| Linked lists always save more space than arrays | Node pointers and allocation overhead can actually consume more space |
Python array.array is a static array | It's a variable-length sequence of homogeneous numeric values |
| A Python 2D list is row-contiguous | It holds references to row objects; the whole matrix is not guaranteed contiguous |
| A circular linked list is the same as a ring buffer | Ring buffers are typically implemented with arrays and head/tail indices |
Java LinkedList.add(0, e) is linear | The front is known; only intermediate indices require traversal |
Two Θ(n) traversal methods perform at the same speed in practice | They have the same asymptotic complexity, but locality and allocation patterns affect constant factors |
Make a Choice with a Full Workload
Start by specifying the operation distribution, such as 90% index reads, 9% tail appends, and 1% mid-inserts. Then clarify what the caller holds: an integer index, a node handle, or an iterator. If an index lookup is needed before each insertion, the total cost of the linked list won’t automatically become constant just because the link modifications are Θ(1).
Next, account for element movement, node allocation, address or iterator invalidation, and cache locality. Begin with a semantically correct and simple container, then validate performance with representative data. Never assume that the same Θ(n) translates to the same actual runtime, nor assign a fixed multiplier to cache benefits.
Return Path
Continue Learning: Access Order Becomes the Interface
Arrays and linked lists address the question of "where data is stored." The next chapter uses stacks, queues, and deques to specify where the next item can be retrieved: LIFO, FIFO, or either end.