Linked List
Imagine a treasure hunt. Each clue holds a prize and tells you where the next clue is hidden. There is no map of all the spots — you can only follow the trail one step at a time. A linked list works the same way: each item holds a value and a pointer to the next item. Give up the ability to jump straight to any spot, and you gain something an array can't do easily — adding and removing in the middle without shuffling anything.
What is it
A linked list is a chain of items where each one points to the next. Every link, called a node, holds two things: a value, and the address of the node after it. The last node points at nothing, which marks the end. Unlike an array's neat numbered row, these nodes can live anywhere in memory — the pointers are what hold the chain together.
How it works
The list remembers just the first node, called the head. To reach the fifth item, you start at the head and follow the 'next' pointer four times — there is no shortcut, because the nodes aren't in a numbered row. That is the trade. What you get back is cheap editing: to insert a new node, you point the previous node at it and point it at what came next — two pointer changes, no shuffling. Removing a node is the same idea in reverse. The chain re-links itself; nothing else moves.
Operations
| Name | Big-O | Why |
|---|---|---|
| Access by position | O(n) | no jumping — you walk the chain from the head |
| Search for a value | O(n) | follow the pointers until you find it or hit the end |
| Insert at the head | O(1) | point the new node at the old head, done |
| Insert after a known node | O(1) | just re-link two pointers, nothing shuffles |
| Delete a known node | O(1) | point its predecessor past it, the chain heals |
When to use
Reach for a linked list when you add and remove a lot, especially at the front or around nodes you already hold. Because editing is just re-linking pointers, there is no costly shuffle like an array's. It also grows one node at a time, so you never guess the size up front or pay for a big resize. When the work is mostly stitching and unstitching a sequence, the linked list shines.
Watch out for
The catch is that you lose instant access by position. Want item number 900? You walk 900 pointers to get there, while an array would jump in one step. Each node also costs extra memory to store its pointer, and because nodes are scattered in memory rather than side by side, they are slower for the computer to read in bulk. Use a linked list for heavy editing, not for heavy random reading.
Analogy
A treasure hunt. Each clue holds a prize and points to where the next clue hides. You can only follow the trail one step at a time — but slipping a new clue into the middle just means rewriting which clue points where.
Practice lessons
Lessons coming soon.