Array vs Singly Linked List
Array and Singly Linked List are both data structures. Play them side by side below, then see exactly where they diverge.
Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.
Array
Full topicNumbered slots side by side, so reaching any one of them costs the same.
INDEX -> CELL -> VALUE. Insert shifts neighbours right, delete shifts left.
Singly Linked List
Full topicEach node points at the next. To reach the tenth you walk the first nine.
VALUE | NEXT boxes joined by arrows. Insertion is a pointer detaching and reattaching, never a shift.
How they differ
An array keeps its values in numbered slots side by side, so reaching any one is O(1), but inserting or deleting in the middle shifts everything after it: O(n). A singly linked list reaches the tenth node only by walking the first nine, O(n), but once you hold a node, inserting or deleting after it is O(1) - nothing moves, one pointer changes.
The run shown here takes 6 steps for Array and 11 steps for Singly Linked List. That count moves with the input - use the example tabs above either player to see it change.
| Cost | Array | Singly Linked List |
|---|---|---|
| access | O(1) | O(n) |
| search | O(n) | O(n) |
| insert | O(n) | not documented |
| delete | O(n) | not documented |
| insert at head | not documented | O(1) |
| insert after node | not documented | O(1) |
| delete after node | not documented | O(1) |
| insert at tail | not documented | O(n) |
| space | O(n) | O(n) |
A dash means the curriculum entry for that topic documents no cost under that name. It is not a claim that the operation is impossible: push on a stack and enqueue on a queue are written as different operations, so they are listed as different rows rather than paired up here.