Introduction to Linked Lists
Linked lists are the first dynamic data structure you’ll encounter. Unlike arrays, they don’t need a fixed size upfront — and that changes everything.
The Problem Arrays Can’t Solve Well
You learned in Day 2 that arrays are stored in contiguous memory — every element sits right next to the previous one. That’s great for random access (arr[42] in O(1)), but it creates a painful problem: insertions and deletions in the middle require shifting elements.
Imagine you have an array of 10,000 sorted names and you need to insert a new name at position 0. Every single element has to shift one spot to the right — that’s O(n) work just to make room.
But there’s a deeper issue: what if you don’t know the size ahead of time?
int names[50]; // What if you get the 51st student?You’re stuck. You either over-allocate (wasting memory) or run out of space.
Enter the Linked List
A linked list solves both problems elegantly. Instead of storing elements in a contiguous block, each element (called a node) is stored wherever there’s free memory — and each node carries a pointer to the next node.
Think of a linked list like a scavenger hunt. Each clue (node) tells you where the next clue is hidden. You can’t jump to clue #5 directly — you must follow the trail from clue #1.
Here’s what a linked list with 5 nodes looks like:
Each node has two parts:
- Data — the actual value stored
- Next — the memory address (pointer) of the next node
The last node’s next pointer holds NULL, signaling the end of the list.
Arrays vs Linked Lists — The Trade-off
Neither is universally better. Choose based on your use case:
| Feature | Array | Linked List |
|---|---|---|
| Random access (get element by index) | ✅ O(1) | ❌ O(n) |
| Insert at beginning | ❌ O(n) | ✅ O(1) |
| Insert at end | ✅ O(1)† | ✅ O(1) with tail pointer |
| Insert in middle | ❌ O(n) shift | ✅ O(1) once position found |
| Delete at beginning | ❌ O(n) shift | ✅ O(1) |
| Memory layout | Contiguous | Scattered |
| Extra memory | None | Pointer per node |
| Dynamic size | ❌ Fixed (or costly resize) | ✅ Grows/shrinks freely |
†Dynamic arrays like C++ vector or Python list amortize to O(1)
Linked lists use more memory per element than arrays because each node must store a pointer (typically 8 bytes on a 64-bit system) in addition to the data. For a list of 1 million integers, that’s 8 MB of extra overhead just for pointers.
Where Are Linked Lists Used?
Linked lists aren’t just textbook theory — they power many real systems:
- Undo/Redo history — Each action is a node; undo = traverse backward
- Browser history — Back/forward = doubly linked list navigation
- Music playlists — Next/previous song = linked list traversal
- OS memory management — Free memory blocks tracked as a linked list
- Hash tables — Chaining for collision resolution uses linked lists
- Implementing stacks & queues — Dynamic push/pop without size limits
Try It Yourself
Play with this interactive linked list. Insert nodes at the front or end, search for values, and delete nodes:
Notice how Insert Front is always instant (O(1)) — we just update the
HEAD pointer. But Insert End needs to traverse all nodes to find the
last one (O(n)). You can fix this by keeping a tail pointer alongside
head.
Quick Check
What’s Next?
In the following sections you’ll learn:
- Introduction — Deep dive into node structure and all four linked list types
- Singly Linked List — Complete operations with code in C++ and Python
- Circular Linked List — When the last node points back to the first
- Doubly Linked List — Bidirectional traversal with
prevandnextpointers - Circular Doubly Linked List — The most flexible variant
- Practice Questions — Curated problems to sharpen your skills