Arrays solved one problem (fast indexing), but they created new pain points:
Problems with Arrays
- Fixed size (or expensive resizing)
- Insertions and deletions are O(n) due to shifting
- Memory must be contiguous
Insert at index 1 in array:
Before: [10][20][30][40]
After : [10][15][20][30][40]
↑ shift everything
This is where Linked Lists enter the scene.
Core Idea of a Linked List
Instead of placing elements next to each other in memory, we store them as nodes, where each node knows who comes next.
[Data | Next] -> [Data | Next] -> [Data | Next] -> NULL
- No shifting
- No contiguous memory requirement
- Dynamic size by design
The Structure Behind a Linked List (The Node)
This is the fundamental structure that makes a linked list possible.
Node Structure (Singly Linked List)
+------+-------+
| Data | Next |
+------+-------+
In code (conceptually):
struct Node {
int data;
Node* next;
};
Key insight
A Linked List is NOT a special structure — it’s just:
- a Node structure
- plus a reference to the first node (head)
Visualizing the Whole Linked List
Head
↓
+----+-----+ +----+-----+ +----+-----+
| 10 | o--+--> | 20 | o--+--> | 30 | NULL|
+----+-----+ +----+-----+ +----+-----+
headpoints to the first node- last node points to
NULL
Types of Linked Lists (And Their Structures)
Singly Linked List
[Data | Next] -> [Data | Next] -> NULL
Structure
struct Node {
int data;
Node* next;
};
Use when
- Memory is tight
- One-direction traversal is enough
Doubly Linked List
Each node knows previous and next.
NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL
Structure
struct Node {
int data;
Node* prev;
Node* next;
};
Trade-off
- Faster deletions
- More memory per node
Circular Linked List
Last node points back to the first.
[Data] -> [Data] -> [Data]
^--------------------|
Key idea
- No
NULL - Useful for round-robin scheduling, buffers
Operations and Their Complexity
| Operation | Linked List | Array |
|---|---|---|
| Access (index) | O(n) | O(1) |
| Insert at head | O(1) | O(n) |
| Insert at middle | O(1)* | O(n) |
| Delete node | O(1)* | O(n) |
| Memory locality | Poor | Excellent |
- given you already have the node pointer
When Should You Use a Linked List?
Good choice when:
- Frequent insertions/deletions
- Size is highly dynamic
- You don’t need random access
Bad choice when:
- You need cache-friendly performance
- You rely heavily on indexing
- You do heavy iteration (arrays win here)
What “cache-friendly” actually means
Modern CPUs don’t read memory byte-by-byte.
They read chunks called cache lines (typically 64 bytes).
Main Memory
┌──────────────────────────┐
│ Cache Line (64 bytes) │ ← fetched at once
└──────────────────────────┘
If your program accesses memory that is physically close together, the CPU:
- fetches once
- reuses data many times
- stays fast
This is called spatial locality.
Why Arrays ARE cache-friendly
Arrays are stored contiguously in memory.
Array in memory:
[10][20][30][40][50][60][70][80]
↑ ↑ ↑ ↑
same cache line
When you do:
for (int i = 0; i < n; i++)
sum += arr[i];
What happens:
- CPU fetches one cache line
- gets multiple elements for free
- next iterations hit the cache
✅ Very fast
✅ Predictable
✅ CPU prefetcher loves this
Why Linked Lists are NOT cache-friendly
Linked list nodes are allocated separately (usually on the heap).
Memory (simplified):
[Node A] [Node C] [Node B]
| | |
v v v
next ----------> next ----------> next
Traversal looks logical:
A -> B -> C
But physical memory reality is:
jump → jump → jump
Each step:
- pointer points to an unrelated memory location
- CPU must fetch a new cache line
- previous cache data is mostly useless
❌ Cache miss
❌ Pipeline stall
❌ Slower execution