Array vs Linked List, step by step.

An array keeps its elements side by side: it reaches any index in O(1), but inserting at the front moves every element. A linked list inserts at the front by changing two links, O(1), but reaches an index by walking from its first node, O(n). Use an array by default, a list when values come and go at the front.

Below, both take the same values twice: put in front, the array moves every value and the list only changes two links; added at the end, the array writes one slot and the list walks every node.

Array vs linked list: what differs

Insert at the front

Take two values, B and D, in an array of three slots and in a linked list, and put A in front of them. In the array, index 0 is taken; the list has no slot to free, only a head that refers to its first node. Which of the two has to move something?

Array: insert A at the beginning

All steps as text
  1. An array of 3 slots holds B and D, and index 2 is free. Step forward to insert A at index 0.
  2. D moves right, from index 1 to 2.
  3. B moves right, from index 0 to 1.
  4. Index 0 is free now, so A is written there.
  5. The array reads A, B, D. To free index 0, every value moved one place right: two here, a million in an array of a million.
Array vs Linked List — Array: insert A at the beginning. Last step: The array reads A, B, D. To free index 0, every value moved one place right: two here, a million in an array of a million.

The moves start from the last value, so that none is overwritten, and their number grows with the array: inserting at the front takes O(n). Deleting from the front moves every value back one slot left.

Linked list: insert A at the beginning

All steps as text
  1. The list is B → D, and head refers to B. Step forward to insert A at the beginning.
  2. A green arrow marks the place for A: in front of B, the node head refers to.
  3. A new node holding A is made below the list. Its next does not refer to any node yet.
  4. A's next is set to refer to B, the first node, so the rest of the list now follows A.
  5. head is set to refer to A, so A is the first node now. B and D slide right only in the drawing, to make room for A in the row.
  6. The list reads A → B → D. In memory no node moved: A was linked in front, and two links changed. With a million nodes it would still be two.
Array vs Linked List — Linked list: insert A at the beginning. Last step: The list reads A → B → D. In memory no node moved: A was linked in front, and two links changed. With a million nodes it would still be two.

Inserting at the front takes O(1) in a list of any length. Deleting from the front is O(1) too, and changes a single link: head moves on to the second node.

Note

In C and C++ a link is a pointer; in Java and Python it is a reference.

Add at the end

Now four values, A to D, and E added after the last one. The array keeps count of its values, so it knows where its first free slot is. The list knows only its first node; the last node is the one whose next is null, a link that refers to no node, drawn as an empty box with no arrow.

Array: add E at the end

All steps as text
  1. An array of 5 slots holds A, B, C and D, and index 4 is free. Step forward to add E at the end.
  2. The array keeps count of its values, 4, so the first free index is 4: E is written there. Nothing is walked and nothing moves.
  3. The array reads A, B, C, D, E. Adding at the end took one step, O(1), as long as a free slot is left.
Array vs Linked List — Array: add E at the end. Last step: The array reads A, B, C, D, E. Adding at the end took one step, O(1), as long as a free slot is left.

A dynamic array keeps spare slots so that adding at the end finds one free. When they run out, it copies every value into a larger array, often twice the size. That happens rarely enough that adding at the end takes O(1) amortized, the average per addition over a whole run from an empty array; the array page shows a resize.

Linked list: add E at the end

All steps as text
  1. The list is A → B → C → D, and head refers to A. Step forward to add E at the end.
  2. A green arrow marks the place for E, after D. The list knows only head, so it has to reach D first, starting from A.
  3. A variable, pred (short for predecessor), shown as a marker, starts at A, the node head refers to. It moves right until it refers to a node whose next is null: the last node.
  4. pred moves to B. B's next is not null, so B is not the last node.
  5. pred moves to C. C's next is not null either.
  6. pred moves to D, whose next is null: D is the last node, and E goes after it.
  7. A new node holding E is made below the list, under the place after D.
  8. D's next is set to refer to E, so E is the last node now. A to D slide left only in the drawing, to make room for E.
  9. The list reads A → B → C → D → E. Reaching D was a walk from the head, O(n); linking E took O(1).
Array vs Linked List — Linked list: add E at the end. Last step: The list reads A → B → C → D → E. Reaching D was a walk from the head, O(n); linking E took O(1).

In a list of a million nodes, pred passes almost a million of them before E can be linked. A list that also keeps a tail, a link to its last node, skips the walk and adds at the end in O(1). Deleting the last node needs the node before it, though, and only a doubly linked list reaches that one without a walk: singly vs doubly linked list.

Access by index: one step or a walk

The walk in the last player is also how a linked list reaches any index: to read the value at index 3, it follows three links from the head. An array works out where index 3 is: its elements all have the same size and stand side by side, so the element at index i starts i element sizes after the first one. That is one multiplication and one addition whatever the index: O(1). The array page shows it in memory.

The same difference decides searching. A sorted array can be searched by halves, looking at the middle and dropping the half that cannot hold the value, in O(log n). A linked list cannot jump to its middle, so even a sorted list is searched node by node, in O(n).

Memory and speed in practice

Memory. An array holds its values and, if it is dynamic, some spare slots: right after it doubles, about half of its slots are empty. A linked list holds a link next to every value, two in a doubly linked list, and each node is a separate piece of memory with some bookkeeping of its own. For small values, the links take more memory than the spare slots do.

The cache. A processor reads memory in blocks of neighboring bytes and keeps them close at hand, in its cache. Walking an array brings the next elements along with each block; a list's nodes can be anywhere, and each one may need a read of its own. That is why an array often wins even where both are O(n): moving the second half of an array to insert in the middle is usually faster than walking a list to the same place.

Array vs linked list at a glance

ArrayLinked list
In memoryOne block, elements side by sideSeparate nodes, each with a link to the next
Access by indexO(1)O(n)
Insert or delete at the frontO(n)O(1)
Add at the endO(1), amortized for a dynamic arrayO(n); O(1) with a tail
Delete at the endO(1)O(n); O(1) in a doubly linked list with a tail
Insert or delete in the middleO(n), to move the values after itO(n), to walk there; O(1) right after a node you hold
Search a sorted sequenceO(log n)O(n)
Extra memorySpare slots, if dynamicA link per value, two if doubly linked
The values hereFront: 2 values moved. End: 1 writeFront: 2 links changed. End: a walk of 3 steps, then 1 link

When to use an array and when a linked list

Use an array by default: whenever you read by index, scan from start to end, sort, search by halves or add at the end. Python's list, Java's ArrayList and C++ std::vector are dynamic arrays, and a stack or a heap is usually built on one.

Use a linked list when values are added and removed at the front, or right after nodes you already hold, and never read by index: a queue with a tail, the chains of a hash table, an LRU cache, which keeps its items in order of use, built on a doubly linked list. A list also suits values that must stay where they are in memory while others come and go, since a node stays where it was made. Java's LinkedList and C++ std::list are doubly linked lists; C++ std::forward_list is a singly linked one.

Common mix-ups

  • Inserting into a linked list is O(1). Only right after a node you already hold. Finding the place, as the second list player does, is a walk: O(n).
  • A Python list is a linked list. It is a dynamic array: index access is O(1), and inserting at the front moves every element.
  • A linked list saves memory, as it has no empty slots. Every value carries a link, or two, and those often take more memory than a dynamic array's spare slots.

Array vs linked list interview questions

Why is access by index O(1) in an array and O(n) in a linked list?

An array's elements have one size and stand side by side, so the place of index i is computed from the start of the array in one step. A linked list's nodes can be anywhere in memory, and the only way to the node at index i is to follow i links from the head.

When is a linked list faster than an array?

When values are inserted or deleted at the front, which moves every element of an array but changes only one or two links in a list, and when they are inserted or deleted right after a node the program already holds. For access by index, scanning and adding at the end, an array is faster.

Should I use ArrayList or LinkedList in Java?

ArrayList in most cases: get(i) is O(1), and it keeps the references to its elements side by side in one array, where LinkedList adds a separate node for each element. LinkedList, a doubly linked list that keeps its last node, adds and removes at both ends in O(1), so it works as a queue or a stack, but ArrayDeque, a growable circular array, usually does that faster.

Two operations here.
Both topics in the app.

In VisiGrab, the array is a 58-slide show and the linked list a 73-slide show, from the first element and the first node to dynamic arrays and the tail, played one step at a time.

Amortized analysis, drawn

One graph shows the worst case, resizes growing as log n and the amortized O(1) line. Then deleting at the end, with and without halving.

The list against the array

A speedometer moves from O(1) for the list's first node to O(n) for any other, and a recap gives the list a winner's cup at the beginning and the array one at the end.

Every insertion and deletion

At the beginning, in the middle and at the end of the list, each a chapter of its own, then a tail that makes insertion at the end O(1).

Forward and back

Step through every slide and step back, or jump to any slide from the list. Each show reopens where you left it.

Python, Java and C++

Static arrays in Java and C++, Python's list, Java's ArrayList and C++'s std::vector, a dynamic array built from scratch in Java and C++, and a linked list with six insert and delete methods in all three, explained part by part.

Two quizzes

Ten questions on each topic, with an explanation for every option.

A row or a chain,
step by step.

Download VisiGrab to step through the array and the linked list: dynamic arrays and their resizing, and every insertion and deletion in the list.

The array and the linked list are topics among 30+. See them all