What's happening?
- Adding at the head is O(1): the new node points at the old head and becomes the head.
- Reaching the end, or finding a value, means walking node by node from the head — O(n).
- Removing a node is just re-pointing its predecessor past it; nothing else moves.
Complexity
- Time
- O(1) add/remove at the head · O(n) to find or reach the end
- Space
- O(n) plus one pointer per node
Where you'll meet it
Queues and stacks underneath, LRU caches (with a hash map), undo histories, and the buckets of a hash map with chaining.
Common mistake
Losing the rest of the list when unlinking: change the predecessor's pointer before you let go of the node.
FAQ
Linked list vs array?
Arrays jump straight to any index (O(1)) but inserting in the middle shifts everything. Linked lists insert cheaply once you are there but must walk to get anywhere.
Why keep a tail pointer?
It makes adding at the end O(1) instead of walking the whole list.
What is a doubly linked list?
Each node also points back to the previous one, so you can walk both ways and remove a node without finding its predecessor.