Arrays and linked lists both store sequences, but they make opposite trade-offs about memory layout, and that choice decides which operations are cheap.
Arrays: fast access by position
An array keeps its elements side by side in memory. Finding element number k is simple address arithmetic, so indexing is O(1). The cost appears when you insert or delete in the middle: every later element must shift, which takes O(n). Contiguous storage also works well with CPU caches, which helps in practice.
Linked lists: fast reshaping
A linked list stores each value in a node together with a pointer to the next node. If you already hold a reference to a node, inserting or deleting after it only means rewiring a pointer, which is O(1). The price is that reaching the k-th node requires walking k steps, and every node carries extra memory for its pointer.
Dynamic arrays close much of the gap
A dynamic array grows by allocating a larger block when it fills up. Because capacity grows multiplicatively, appending is O(1) amortized. For most everyday programs this makes the dynamic array the sensible default.
A quick decision guide
- You need indexing, binary search, or compact memory: choose an array.
- You frequently insert or remove at known positions in the middle, and you already hold node references: consider a linked list.
- You are unsure: start with a dynamic array and measure before changing.
A common misconception
Linked lists are not automatically faster at insertion. If you must first search for the position, that search costs O(n), which can erase the benefit.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithms Made Simple.
Adapted from Algorithms Made Simple, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.