Linked Lists

Think of a scavenger hunt. Clue #1 doesn’t tell you where the treasure is — it tells you where clue #2 is hidden. Clue #2 points you to clue #3. You can’t skip ahead to clue #5; you have to follow the chain, one link at a time. That’s a linked list!

Here’s what one actually looks like:

The idea is simple.

A linked list is a chain of nodes. Each node holds two things: a value, and a pointer to the next node in the chain. The last node’s pointer doesn’t point anywhere — it points to NULL, which just means “nothing here, the list ends.”

That’s the whole structure. No big reserved block of memory, no fixed size. Each node just needs to know where the next one lives. Compare that to an array, where every element sits in one contiguous block and you can jump straight to element #12 because you know exactly how far away it is. A linked list has no such shortcut — to get to the 12th node, you walk through the 11 before it.

The parts of a list

1. Head — a pointer to the first node. It’s the only way in; lose it, and the whole list is unreachable.
2. Node — one link in the chain: a value plus a pointer to the next node.
3. Pointer (or “next”) — the piece of each node that says where the following node lives.
4. NULL — what the last node points to. It marks the end of the list.

A linked list only needs a few operations to work:

Insert — point the new node at what comes next, then point the previous node at the new node.

Search — walk from the head, following pointers, until you find the value or run out of list.

Traverse — start at the head, and follow every pointer to the end.

Delete — point the previous node past the one you’re removing, skipping it entirely.