Nodes scattered in memory, held together by pointers. Insertion costs nothing once you are there — but getting there costs everything, and that trade-off defines when to use one.
Controls
valueposition
Nodes and Pointers
step 0
Cost of the last operation
Insight
Each node stores a value and a pointer to the next node. There is no index arithmetic — the only way to reach position k is to follow k pointers from the head.
Used for
• Queue & stack implementations
• Hash table collision chains
• LRU caches (doubly linked)
• Undo histories
Complexity
Insert / delete at headO(1)
Access by indexO(n)
SearchO(n)
Linked Lists
The structure that trades instant access for instant insertion.
Quick Context
A linked list stores each element in its own node, which also holds a pointer to the next node. Unlike an array, the elements need not sit next to each other in memory — the pointers are what impose the order.
The Fundamental Trade-off
An array gives you arr[500] in O(1) because the address is pure arithmetic: start + 500 × itemsize. A linked list has no such shortcut — you must start at the head and follow 500 pointers. That is O(n).
In exchange, inserting into the middle of an array costs O(n) because everything after the insertion point must shift up. In a linked list, once you are at the right place, insertion is O(1): create the node and rewire two pointers. Nothing moves.
Watch the cost table as you insert at position 0 versus the end — the traversal is where the time goes, never the insertion itself.
Rewiring, Step by Step
To insert node N after node P:
N.next = P.next // N points to the rest of the list
P.next = N // P now points to N
Order matters absolutely. Do those two lines the other way round and you overwrite P.next before reading it — the remainder of the list becomes unreachable and is lost. This is the classic linked-list bug.
Singly vs Doubly Linked
Singly linked — one pointer per node. Less memory, but you can only travel forward, and deleting a node requires knowing its predecessor.
Doubly linked — next and prev. Costs more memory but allows backward traversal and O(1) deletion given only the node itself.
That last property is why LRU caches use a doubly linked list: when a hash lookup hands you a node, you can unlink and re-insert it at the front in constant time.
Why Arrays Often Win Anyway
Big-O says linked lists should beat arrays for insertion-heavy work. In practice arrays frequently win regardless, because of cache locality. Array elements sit contiguously in memory, so the CPU loads many at once. Linked-list nodes are scattered, and each pointer hop risks a cache miss costing hundreds of cycles.
This is a good reminder that Big-O counts operations, not time. Modern advice: reach for a dynamic array by default, and a linked list when you specifically need O(1) splicing with a node reference already in hand.
Interactive Exploration Guide
Insert at position 0. Zero traversal steps — genuinely O(1), the linked list's best case.
Insert at the end. The cost table shows the traversal dominating; the rewiring is still just two assignments.
Delete from the middle and watch the pointer of the previous node jump over the removed one. Nothing else in the list moves.
Search for a value. Every node must be checked in order — no binary search is possible, because you cannot jump to the middle.
Switch to doubly linked and note the backward arrows, plus the extra pointer each node now has to store.
Key Takeaway
Linked lists make insertion and deletion cheap and access expensive — the exact opposite of arrays. Use them when you hold a reference to the node you need and are splicing constantly; otherwise an array's cache behaviour usually beats the theory.
Cheat sheet
Linked Lists
Nodes scattered in memory, held together by pointers. Insertion costs nothing once you are there — but getting there costs everything, and that trade-off defines when to use one.