Algorithms from zero
The linked list
You know that an array is a row of contiguous boxes in memory, and that contiguity gives you O(1) indexing but O(n) insertion in the middle. Now imagine a different structure: nodes scattered across memory, each holding a value and pointing to the next node. This is a linked list. You lose the superpower of O(1) indexing—finding the 5th element now costs O(n)—but you gain the power to insert at the head in O(1) time, no shifting required.
After this lesson you can explain what a node and a pointer are, draw a linked list in memory, implement push (insert at head) and traverse, understand why indexing by position is O(n) and why insertion at the head is O(1), compare the time and space costs of linked list vs. array operations, and recognize when a linked list is the right choice.
The basic idea: nodes and pointers
An array is a row of boxes all lined up together. A linked list is a sequence of nodes. Each node is a small container that holds two things:
- A value (the data you care about)
- A pointer (a memory address pointing to the next node)
The linked list starts at a special node called the head. If you want to visit every value, start at the head, read the value, follow the pointer to the next node, and repeat.
Example: A linked list holding [10, 20, 30]:
head → [10 | next → ] → [20 | next → ] → [30 | next → null]Each [ value | next → ] is a node. The last node’s next is null, meaning “there is no next node.”
Why scattered memory matters:
Arrays store all elements in a contiguous block. The computer can calculate the address of any element instantly: base_address + (index × element_size).
Linked lists are different. Nodes can be stored anywhere in memory. To find the node at position 5, you cannot calculate its address. Instead, you must start at the head, follow the pointer, step 1, step 2, step 3, step 4, step 5. This costs O(n) time.
Why pointers matter:
Because nodes are scattered, each node must store the address of the next node. That address is the pointer. In memory, a pointer is just a number—typically 8 bytes on a 64-bit system—but it tells the computer: “The next piece of data is at this address.”
Example memory layout (imaginary):
Address 1000: node 1 = [10, pointer to 3008]
Address 3008: node 2 = [20, pointer to 5016]
Address 5016: node 3 = [30, pointer to null]Notice the addresses are not consecutive. Nodes 1, 2, 3 are at 1000, 3008, 5016. But each node points to the next, so we can traverse the list.
Insert at the head: the linked list superpower
In an array, inserting at the beginning requires shifting all n elements. Expensive.
In a linked list, insert at the head is trivial:
- Create a new node with your value.
- Set its pointer to the current head.
- Update head to point to the new node.
That is three operations. Time: O(1).
1
class Node {
2
constructor(value, next = null) {
3
this.value = value;
4
this.next = next;
5
}
6
}
7
8
let head = new Node(10); // List: [10]
9
10
// Insert 20 at the head
11
head = new Node(20, head); // List: [20, 10]
12
13
// Insert 30 at the head
14
head = new Node(30, head); // List: [30, 20, 10]
- L1 Each node holds a value and a pointer to the next node
- L8 Create the first node
- L11 Create a new node pointing to the old head
- L14 Update head to the new node. O(1) — no shifting!
Traverse: the linked list cost
To find a value or access position i, you must traverse from the head:
1
function getAtIndex(head, index) {
2
let current = head;
3
for (let i = 0; i < index; i++) {
4
if (current === null) return null; // End of list
5
current = current.next; // Follow pointer
6
}
7
return current?.value;
8
}
- L2 Start at head
- L3 Loop index times
- L5 Follow the pointer to the next node
- L8 Return the value at position index, or null if not found
For a list of n nodes, finding position i costs O(i) time. In the worst case (i = n), it is O(n).
Linked list vs. array at a glance:
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert in middle | O(n) | O(n) |
| Insert at tail | O(1) amortized | O(n) |
| Delete at head | O(n) | O(1) |
| Delete in middle | O(n) | O(n) |
| Search for value | O(n) | O(n) |
The tradeoff: arrays are fast for reading; linked lists are fast for inserting at the head.
Let us build a simple linked list class with push (insert at head) and traverse:
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Insert at the head: O(1)
push(value) {
this.head = new Node(value, this.head);
}
// Get value at index: O(n)
getAtIndex(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (current === null) return null;
current = current.next;
}
return current?.value;
}
// Get node at index (useful for deletion/insertion): O(n)
getNodeAt(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (current === null) return null;
current = current.next;
}
return current;
}
// Traverse and print all values: O(n)
traverse() {
const values = [];
let current = this.head;
while (current !== null) {
values.push(current.value);
current = current.next;
}
return values;
}
}Try building and traversing a linked list:
Let us trace the push operation step by step. We start with an empty list and push three values: 10, 20, 30.
1
const list = new LinkedList();
2
list.push(10);
3
list.push(20);
4
list.push(30);
Now trace a getAtIndex(2) call on the list [30, 20, 10]:
1
function getAtIndex(index) {
2
let current = head;
3
for (let i = 0; i < index; i++) {
4
current = current.next;
5
}
6
return current?.value;
7
}
Each hop to the next node is one step. To reach position i, you must hop i times. Time: O(i).
Linked list operations:
| Operation | Time | Space |
|---|---|---|
| Access element at index i | O(i) | O(1) aux |
| Search for value | O(n) | O(1) aux |
| Push (insert at head) | O(1) | O(1) |
| Insert after node at index i | O(i) to find node, then O(1) to insert | O(1) |
| Delete at head | O(1) | O(1) |
| Delete at index i | O(i) | O(1) |
| Traverse all | O(n) | O(1) aux |
Why is push O(1)? You create a new node and update one pointer. Two operations. No traversal needed.
Why is accessing by index O(n)? You must follow pointers one by one. No formula to jump straight to position i.
Contrast with arrays:
Arrays are O(1) for indexing because memory is contiguous. Linked lists are O(n) because memory is scattered and you must follow pointers.
The intuition: Contiguity enables calculation. Scattering requires traversal.
In a linked list with 1000 nodes, how much time does it take to find the node at index 500?
In a linked list, why is inserting at the head O(1)?
An array of 100 elements allows O(1) access to arr[99]. A linked list of 100 nodes requires O(n) to reach node 99. Why this difference?
You insert values 10, 20, 30 at the head of a linked list (in that order). What is the list after all three pushes?
In a linked list, why can't you just calculate the memory address of the node at position i, like you do in an array?
Edge cases
Inserting in the middle: If you have a reference to a node and want to insert after it, that is O(1)—just redirect the pointer. But if you want to insert at position i (where you don’t have a reference yet), you must traverse to position i first, costing O(i). So “insert at position i” in a linked list is O(i), not O(1).
Common mistake
“Linked lists are always slower.” False. Linked lists are slower at indexing (O(n)) but faster at insertion at the head (O(1)). The right tool depends on the task. If you frequently push and rarely index, a linked list is better. If you frequently index, an array is better.
Why does a linked list achieve O(1) insertion at the head while an array requires O(n) to insert at the beginning?
A linked list is a sequence of nodes, each holding a value and a pointer to the next node.
Key facts:
- Node: A container with two fields—value and next (pointer to the next node).
- Head: The first node. Iteration starts here.
- Pointer: A memory address pointing to the next node.
- Scattered memory: Nodes are not contiguous. Pointers link them together.
- Indexing is O(n): No formula to jump to position i. Must follow pointers one by one.
- Push is O(1): Create a new node, point it at the old head, update head. No shifting.
- Tradeoff: Give up O(1) indexing; gain O(1) head insertion.
- Use when: Frequent insertions at the front, infrequent random access.
Next, you will learn the stack and queue—two other sequential data structures built on linked lists, each with their own discipline and use cases.