← Learn DSA · Lesson 2 of 9
Linked Lists
Cheap insertion anywhere, at the price of ever finding anything.
The idea
A linked list stores each value in its own node, together with a pointer to the next one. There is no block of memory holding them in order — the only thing connecting the third element to the fourth is a pointer stored inside the third.
That single difference from an array decides everything else about it.
Because nothing is contiguous, there is no index arithmetic. You cannot jump to the middle: reaching element k means following k pointers from the head. Every lookup is O(n), and that is not an implementation detail you can optimise away — it is what the structure is.
In exchange, inserting or removing in the middle costs nothing beyond finding the spot. An array insertion shifts every element after it; a list insertion rewrites two pointers. If you already hold a reference to the node, the operation is O(1) no matter how long the list is.
The head is the only position you get for free, which is why a list makes a natural stack, and why adding a tail pointer — and paying to keep it correct — is what turns one into a queue.
Walkthrough
Searching for 6 by following the chain. There is no jumping ahead — every node before it has to be visited, which is the whole cost of the structure.
What it costs
- time
- O(1) insert or remove at a known node, O(n) to find one
- space
- O(n), plus one pointer per element
The pointer is real overhead: a list of numbers can use twice the memory of the equivalent array, and it scatters them, so it also loses the cache locality that makes array scans fast in practice.
When to reach for it
- You insert and remove in the middle constantly, and rarely look things up by position.
- You already hold a reference to the node you want to act on — then the edit is O(1).
- You need a stack or queue and never need to index into it.
- You are building something else out of it: an LRU cache, an adjacency list, a hash bucket chain.
Rather than the obvious alternative
An array or dynamic array
Almost always the better default. It gives O(1) access by index and scans far faster in practice because its elements sit together in memory. Only prefer a list when middle insertion genuinely dominates your workload — and measure, because shifting a few thousand contiguous elements is often faster than chasing a few hundred pointers.
A deque
If you only ever push and pop at the two ends, a deque gives you that in O(1) with none of the pointer overhead or cache misses.
How to spot it
- The problem hands you a `head` and never an index.
- You are asked to reverse, reorder, or detect a cycle in a sequence you can only walk forwards.
- Elements must keep their identity across moves — the node itself matters, not just its value.
- The problem forbids extra memory, which usually means rewiring pointers rather than rebuilding.
Where it goes wrong
Losing the rest of the list
Reassigning `node.next` before saving the old value drops everything after it. Keep the next pointer in a temporary variable first — this is the bug behind nearly every failed reversal.
Forgetting the empty and single-node cases
A list of length 0 or 1 is valid input, and most pointer manipulation has a special case there. Check them before writing the loop, not after it fails.
Assuming you can go backwards
In a singly linked list you cannot. If an algorithm needs the previous node, either track it as you walk or use a doubly linked list — realising this halfway through is expensive.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Return how many nodes are in nodes by walking it one step at a time. No .length.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| countNodes([4,8,15]) | several nodes | 3 | — |
| countNodes([9]) | single node | 1 | — |
| countNodes([]) | empty list | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Practise it
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.