Linked Lists — Introduction
Learn what linked lists are, how they differ from arrays, and when to use them.
Linked Lists
A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike an array, the nodes are not stored in contiguous memory — they can be scattered anywhere, connected only by their pointers.
Think of a linked list like a treasure hunt. Each clue tells you where the next clue is. You cannot jump directly to clue 5 — you have to follow the chain from clue 1.
How it looks in memory
Array:
[10][20][30][40][50] ← contiguous, each element right next to the next
Linked List:
[10|→] ··· [20|→] ··· [30|→] ··· [40|→] ··· [50|∅]
↑ ↑
head tailEach node contains two things — the data and a pointer (next) to the next node. The last node points to None.
A node in Python
class Node:
def __init__(self, value):
self.value = value
self.next = None # pointer to next node
class LinkedList:
def __init__(self):
self.head = None # pointer to first node
self.size = 0Key operations and their complexity
| Operation | Array | Linked List | Why |
|---|---|---|---|
| Access by index | O(1) | O(n) | Must walk from head |
| Insert at beginning | O(n) | O(1) | Just update head pointer |
| Insert at end | O(1) amortized | O(n) or O(1) with tail | Walk to end or use tail pointer |
| Insert at position | O(n) | O(n) | Walk to position |
| Delete at beginning | O(n) | O(1) | Just update head pointer |
| Delete at position | O(n) | O(n) | Walk to position |
| Search | O(n) | O(n) | Must traverse |
Arrays vs linked lists — when to use which
| Situation | Use |
|---|---|
| Need fast index access | Array |
| Frequent insert/delete at beginning | Linked list |
| Frequent insert/delete in middle | Linked list |
| Fixed or known size | Array |
| Unknown or dynamic size | Either |
| Cache efficiency matters | Array |
| Memory is fragmented | Linked list |
Arrays win on access speed — O(1) vs O(n). Linked lists win on insert/delete at the beginning — O(1) vs O(n). The right choice depends on what operations your program does most.
Types of linked lists
Singly linked — each node points to the next. Can only traverse forward.
Doubly linked — each node points to both next and previous. Can traverse in both directions.
Circular — the last node points back to the first. Used in round-robin scheduling.
What is coming in this section
Singly linked list — build one from scratch, implement all operations with visualization.
Doubly linked list — add backward pointers, see how insert and delete change.
Fast and slow pointers — the most important linked list technique. Detects cycles, finds midpoints, and more.