Arrays vs Linked Lists
Put the growing array's and the linked list's cost cards side by side, see why growing arrays win most of the time in real code, and learn the jobs where a linked list is the better fit.
Journeyman · Data Structures · Updated
After this lesson you can
- Compare the cost cards of a growing array and a linked list, operation by operation
- Explain why growing arrays usually win in real code, and name the jobs where a linked list fits
Key takeaways
- A growing array reads any position in O(1); a linked list walks to it in O(n).
- A linked list adds and removes at the front in O(1); a growing array moves everyone, O(n).
- Items side by side are read faster than nodes scattered around memory, because memory is fetched in chunks: that's cache locality.
- Growing arrays win most of the time in real code; linked lists fit work at the ends, or right where your code already is.
"Should this be a list or a linked list?" comes up in code reviews, in system-design interviews and in every data structures exam. The textbook answer compares Big-O, and that's where this lesson starts. But there's a second half to the answer that textbooks often skip, about how real computers fetch memory, and it's why experienced developers reach for the growing array almost every time. By the end you'll be able to give both halves.
The two cost cards, side by side
| Operation | Growing array | Linked list (with a tail) |
|---|---|---|
| Read the item at a position | O(1): one sum | O(n): walk from the head |
| Add at the end | O(1) amortized | O(1): couple to the tail |
| Add or remove at the front | O(n): everyone scoots over | O(1): change the head |
| Insert or remove in the middle, once you're there | O(n): everyone after it scoots | O(1): change two references |
| Get to the middle | O(1) | O(n) |
| Find an item by its value | O(n) | O(n) |
| Memory per item | the item | the item, plus one or two references |
Read it as a trade. The array is fast at jumping to any position and slow at changing the front or middle. The linked list is the other way around. Neither is faster at searching: both read item by item.

Counting the difference
This program builds the same 10,000 songs both ways and reads position 5,000 from each, counting the steps. Then it adds 1,000 songs at the front of an empty growing array and an empty linked list, counting the songs the array moves and the references the linked list changes.
List<string> array = new List<string>();
for (int i = 0; i < 10000; i++)
{
array.Add("Song " + i);
}
SongNode? head = null;
for (int i = 9999; i >= 0; i--)
{
head = new SongNode("Song " + i, head);
}
SongNode? node = head;
int steps = 0;
while (node != null && steps < 5000)
{
node = node.Next;
steps++;
}
Console.WriteLine("Position 5000 in the array: " + array[5000] + ", 1 step");
Console.WriteLine("Position 5000 in the linked list: " + node?.Title + ", " + steps + " steps");
List<string> frontArray = new List<string>();
SongNode? frontHead = null;
long moved = 0;
int changed = 0;
for (int i = 0; i < 1000; i++)
{
moved += frontArray.Count;
frontArray.Insert(0, "Song " + i);
frontHead = new SongNode("Song " + i, frontHead);
changed += 2;
}
Console.WriteLine("1000 songs at the front: the array moved " + moved + " songs, the linked list changed " + changed + " references");
class SongNode
{
public string Title;
public SongNode? Next;
public SongNode(string title, SongNode? next)
{
Title = title;
Next = next;
}
}
Position 5000 in the array: Song 5000, 1 step
Position 5000 in the linked list: Song 5000, 5000 steps
1000 songs at the front: the array moved 499500 songs, the linked list changed 2000 references
class SongNode {
String title;
SongNode next;
SongNode(String title, SongNode next) {
this.title = title;
this.next = next;
}
}
void main() {
List<String> array = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
array.add("Song " + i);
}
SongNode head = null;
for (int i = 9999; i >= 0; i--) {
head = new SongNode("Song " + i, head);
}
SongNode node = head;
int steps = 0;
while (node != null && steps < 5000) {
node = node.next;
steps++;
}
IO.println("Position 5000 in the array: " + array.get(5000) + ", 1 step");
IO.println("Position 5000 in the linked list: " + node.title + ", " + steps + " steps");
List<String> frontArray = new ArrayList<>();
SongNode frontHead = null;
long moved = 0;
int changed = 0;
for (int i = 0; i < 1000; i++) {
moved += frontArray.size();
frontArray.add(0, "Song " + i);
frontHead = new SongNode("Song " + i, frontHead);
changed += 2;
}
IO.println("1000 songs at the front: the array moved " + moved + " songs, the linked list changed " + changed + " references");
}
Position 5000 in the array: Song 5000, 1 step
Position 5000 in the linked list: Song 5000, 5000 steps
1000 songs at the front: the array moved 499500 songs, the linked list changed 2000 references
class SongNode:
def __init__(self, title, next_node):
self.title = title
self.next = next_node
array = []
for i in range(10000):
array.append(f"Song {i}")
head = None
for i in range(9999, -1, -1):
head = SongNode(f"Song {i}", head)
node = head
steps = 0
while node is not None and steps < 5000:
node = node.next
steps += 1
print(f"Position 5000 in the array: {array[5000]}, 1 step")
print(f"Position 5000 in the linked list: {node.title}, {steps} steps")
front_array = []
front_head = None
moved = 0
changed = 0
for i in range(1000):
moved += len(front_array)
front_array.insert(0, f"Song {i}")
front_head = SongNode(f"Song {i}", front_head)
changed += 2
print(f"1000 songs at the front: the array moved {moved} songs, the linked list changed {changed} references")
Position 5000 in the array: Song 5000, 1 step
Position 5000 in the linked list: Song 5000, 5000 steps
1000 songs at the front: the array moved 499500 songs, the linked list changed 2000 references
class SongNode {
constructor(title, next) {
this.title = title;
this.next = next;
}
}
const array = [];
for (let i = 0; i < 10000; i++) {
array.push(`Song ${i}`);
}
let head = null;
for (let i = 9999; i >= 0; i--) {
head = new SongNode(`Song ${i}`, head);
}
let node = head;
let steps = 0;
while (node !== null && steps < 5000) {
node = node.next;
steps++;
}
console.log(`Position 5000 in the array: ${array[5000]}, 1 step`);
console.log(`Position 5000 in the linked list: ${node.title}, ${steps} steps`);
const frontArray = [];
let frontHead = null;
let moved = 0;
let changed = 0;
for (let i = 0; i < 1000; i++) {
moved += frontArray.length;
frontArray.splice(0, 0, `Song ${i}`);
frontHead = new SongNode(`Song ${i}`, frontHead);
changed += 2;
}
console.log(`1000 songs at the front: the array moved ${moved} songs, the linked list changed ${changed} references`);
Position 5000 in the array: Song 5000, 1 step
Position 5000 in the linked list: Song 5000, 5000 steps
1000 songs at the front: the array moved 499500 songs, the linked list changed 2000 references
class SongNode {
title: string;
next: SongNode | null;
constructor(title: string, next: SongNode | null) {
this.title = title;
this.next = next;
}
}
const array: string[] = [];
for (let i = 0; i < 10000; i++) {
array.push(`Song ${i}`);
}
let head: SongNode | null = null;
for (let i = 9999; i >= 0; i--) {
head = new SongNode(`Song ${i}`, head);
}
let node: SongNode | null = head;
let steps = 0;
while (node !== null && steps < 5000) {
node = node.next;
steps++;
}
console.log(`Position 5000 in the array: ${array[5000]}, 1 step`);
console.log(`Position 5000 in the linked list: ${node?.title}, ${steps} steps`);
const frontArray: string[] = [];
let frontHead: SongNode | null = null;
let moved = 0;
let changed = 0;
for (let i = 0; i < 1000; i++) {
moved += frontArray.length;
frontArray.splice(0, 0, `Song ${i}`);
frontHead = new SongNode(`Song ${i}`, frontHead);
changed += 2;
}
console.log(`1000 songs at the front: the array moved ${moved} songs, the linked list changed ${changed} references`);
Position 5000 in the array: Song 5000, 1 step
Position 5000 in the linked list: Song 5000, 5000 steps
1000 songs at the front: the array moved 499500 songs, the linked list changed 2000 references
The array moved 499,500 songs for 1,000 adds at the front: 0 + 1 + 2 + … + 999, the handshakes at a party of 1,000 again. The linked list changed 2 references per add, however long it got.
The other half: how memory is fetched
So far it sounds even. In real programs it usually isn't, and the reason is how the computer reads memory.
Think of a library where you can only fetch books a whole shelf at a time. If the books you need sit side by side on one shelf, one trip brings back a dozen of them. If each book is on a different floor, every book is its own trip. The processor works like that: it fetches memory in chunks and keeps the latest chunks close by, in a small, very fast memory called the cache. An array's items sit side by side, so reading one brings its neighbors along for free. A linked list's nodes are scattered wherever they were made, so walking the list is a trip per node. Keeping data you'll use together close together is called cache locality.

On top of that, each node carries one or two references besides its item, so a linked list of n songs takes more memory than an array of n songs.
The result: walking a growing array is often several times faster than walking a linked list of the same length, even though both are O(n), and a growing array's O(n) insert in the middle is often quicker than you'd expect for a list of a few thousand items, because shifting side-by-side items is the fastest kind of copying there is. Big-O tells you how the work grows; locality decides how fast each step is.
So which one?
Reach for your language's list (a growing array) by default. Most jobs read by position, add at the end and loop over everything, and it's the best at all three.
A linked list fits when:
- you add or remove at the front a lot, as in a queue of jobs or a "play next" button (the next chapter builds queues on this);
- you add and remove right where your code already is, holding a reference to the node, as in a music player's previous and next buttons or an editor's undo history;
- a moving day's pause is unacceptable, and steady O(1) adds matter more than speed overall.
Try it. In the code above, change the reading position from 5,000 to 9,999. How many steps does each structure take now? Then add 2,000 songs at the front instead of 1,000: about how many times as many songs does the array move?
Check yourself
2 questions to try on the lesson page.
So what
You can now answer "array or linked list?" the way experienced developers do: with the Big-O trade first, then the memory half that usually settles it. That two-part answer is exactly what an interviewer is hoping to hear.