Linked structures / lists, stacks, queues / interactive
Four data structures, one piece of plumbing
A linked list is a value that knows where the next value lives. That is the entire idea — and a stack, a queue and a deque are all the same chain of nodes with different rules about which end you're allowed to touch. Learn the plumbing once and the other three are a change of vocabulary. Every diagram below runs, and every one can be stepped a line at a time.
The shared shape
A node holds a value and a reference. Chain them and you have a list; the reference is what makes it linked rather than laid out.
Where you meet them
Java'sLinkedList, ArrayDeque and Stack; the undo history in every editor you've used.Call stacks
Every method call pushes a frame; every return pops one. A stack overflow is literally this structure running out of room.Schedulers and buffers
Print queues, task queues, keyboard input, breadth-first search — anything that must be served in arrival order.Inside other structures
Hash table buckets chain collisions in a linked list. Adjacency lists in graphs are lists of lists.Why not just use an array?
Because the two structures fail in opposite places. An array is a block; a list is a chain.
An array stores elements next to each other in memory. Element i is at base + i × size, so indexing is one multiplication — genuinely instant. The price is that inserting at the front means shifting every other element up one slot.
A linked list stores elements wherever they land, each pointing at the next. Splicing a node in or out is a couple of assignments no matter how long the list is. The price is that there is no arithmetic that finds element i — you have to walk there, one node at a time.
The honest caveat: big-O is not the whole story. Array elements sit in a contiguous block, so a CPU pulls several into cache at once. List nodes are scattered, and each hop may be a cache miss. In practice an ArrayList often beats a LinkedList even at tasks the table below says lists should win. Reach for a list when you genuinely splice at known positions, or when you need the guarantee rather than the average.
| Operation | Array | Singly | Doubly |
|---|---|---|---|
| get(i) | O(1) | O(n) | O(n) |
| add at front | O(n) | O(1) | O(1) |
| add at back | O(1)* | O(1)† | O(1) |
| remove front | O(n) | O(1) | O(1) |
| remove back | O(1) | O(n) | O(1) |
| remove known node | O(n) | O(n) | O(1) |
| search by value | O(n) | O(n) | O(n) |
| memory / element | value | value + 1 ref | value + 2 refs |
* amortised — a dynamic array occasionally reallocates and copies. † only if you keep a tail reference; without one it is O(n).
Structure 01
Singly linked list
One reference per node, pointing forward. Everything else on this page is built out of this.
Structure 02
Doubly linked list
Add a backward reference and two O(n) operations collapse to O(1). You pay for it on every single write.
Structure 03
Stack — last in, first out
The same list, with a rule: you may only touch one end. That restriction is the whole feature.
Textbooks draw stacks vertically, growing upward. It is the same diagram rotated — what matters is that push and pop touch the same end, which is why both are O(1) with no tail pointer needed.
Structure 04
Queue — first in, first out
Add at one end, remove from the other. The only new requirement is a reference to the far end.
One structure, four interfaces
Identical nodes, identical pointer surgery. The difference is purely which ends the public methods expose.
| Type | Add | Remove | What the restriction buys you |
|---|---|---|---|
| Stack | push → head | pop → head | Reversal and backtracking for free. The most recent thing is always the cheapest to reach — undo, call frames, expression evaluation, depth-first search. |
| Queue | enqueue → tail | dequeue → head | Fairness. Nothing overtakes anything else, so arrival order is preserved — schedulers, buffers, breadth-first search. |
| Deque | either end | either end | Both of the above. Needs a doubly linked list, because removing from the back requires knowing the second-to-last node. |
| List | anywhere | anywhere | Nothing — and that is the point. Full access means no guarantees about cost, and callers can put the structure in any state they like. |
The four cases you must test
Almost every linked-list bug is one of these four situations going unhandled. Write the tests before the method.
Case 01
Empty list
head == null. Every method must survive it. Adding must set both head and tail; removing must return gracefully rather than dereferencing null.
Case 02
Single element
head == tail. Removing it has to null out both references. This is the case that gets forgotten, and it leaves a dangling tail pointing at a node no longer in the list.
Case 03
At the head
There is no previous node to rewire, so the general "prev.next = cur.next" line does not apply. Either special-case it or use a dummy head node so it never arises.
Case 04
At the tail
cur.next == null. Removing here must update tail, and in a singly linked list that means you needed the previous node all along — which is exactly the O(n) the table promised.
Reference code
Java implementations of all four, plus the node classes they share.
Dummy head
Allocating one unused sentinel node before the real head removes case 03 entirely —prev always exists. Costs one node, deletes a whole class of bug.Keep a size field
Maintain it in every add and remove. Walking the list to count is O(n) and callers will callsize() inside loops.Null out removed nodes
Settingremoved.next = null helps the garbage collector and turns "used a stale node" into an immediate NPE rather than silent corruption.Iterators break
Modifying a list while iterating it is undefined behaviour. Java throwsConcurrentModificationException on purpose — track a modification counter.