What is a linked list?
A data structure is a way to organise data in memory. A linked list is a chain of nodes. Each node has:
- data: the value we store (a number, a nameβ¦)
- next: a pointer, which is the memory address of the next node
A variable head holds the address of the first node. The last node's next is NULL (None in Python), meaning "no more nodes". We draw nodes as boxes and pointers as arrows: 12 β 7 β 25 β 3 β NULL.
A linked list is recursive: a list is either empty, or one node followed by a smaller list.
Static vs dynamic memory
An array is static: you reserve a fixed block of side-by-side cells. Growing it means copying everything to a bigger block.
A linked list is dynamic: each node is created only when needed (malloc/new in C/C++, a new object in Python or Java) and freed when removed. Nodes do not need to be next to each other, because each one knows where the next lives.
You can also build a list statically inside an array: store data[] and next[] arrays, where next[i] is the index of the next item (β1 for the end). This is common in exam questions and in languages without pointers.
Operations: traverse, insert, delete, search, length
- Traverse: p = head; while p is not NULL: visit p.data; p = p.next.
- Length: traverse and count nodes. O(n).
- Search: traverse until you find the value. Worst case n steps, O(n).
- Insert at front: new.next = head; head = new. O(1), just 2 pointer changes.
- Insert after node p: new.next = p.next; p.next = new. Order matters! Doing it the other way loses the rest of the list.
- Delete after node p: p.next = p.next.next (and free the removed node in C).
class Node:
def __init__(self, data):
self.data = data
self.next = None
def push_front(head, x):
n = Node(x); n.next = head
return n # new head
Linked list vs array, and its family
| Array | Linked list | |
|---|---|---|
| Get k-th item | O(1) jump | O(k) walk |
| Insert/delete at front | O(n) shifting | O(1) |
| Size | fixed or re-copied | grows node by node |
| Extra memory | none | one pointer per node |
Doubly linked list: each node also has a prev pointer, so you can walk backwards. Circular list: the last node points back to the first. A stack is a list where you only push/pop at the head; a queue adds at the tail and removes at the head.
Try it
Write 5 numbers on 5 slips of paper. On the back of each slip write where the next slip is hidden in the room. Give a friend only the first slip (the head). Time how long it takes to reach the last one. Now insert a new slip at the front: what did you have to change?
Key formulas and definitions
- Node = (data, next)
- Insert at front: new.next = head; head = new β O(1)
- Insert after p: new.next = p.next; p.next = new
- Delete after p: p.next = p.next.next
- Search / length / access k-th: O(n)
- Last node: next = NULL (None)
Worked examples
1. List: head β 4 β 9 β 2 β NULL. Insert 7 at the front. Write the list.
new(7).next = head (node 4); head = new. List: 7 β 4 β 9 β 2 β NULL.
2. In 4 β 9 β 2, delete 9.
p = node 4. p.next = p.next.next, so 4 now points to 2. List: 4 β 2 β NULL.
3. How many nodes are visited to search for 2 in 7 β 4 β 9 β 2?
Start at head: 7 (1), 4 (2), 9 (3), 2 (4). 4 nodes.
4. A static list: data = [D, A, C, B], next = [β1, 3, 0, 2], head = 1. Read the list.
Index 1 = A, next 3 = B, next 2 = C, next 0 = D, next β1 = end. List: A β B β C β D.
5. Why is 'p.next = new; new.next = p.next' wrong?
After the first line p.next is already new, so new.next becomes new itself: a loop, and the rest of the list is lost. Set new.next first.
Common mistakes
- Changing p.next before saving it in new.next. You lose the rest of the list.
- Forgetting to update head when inserting or deleting at the front.
- Not checking for an empty list (head = NULL) before reading head.next.
- Thinking a linked list gives fast access to item k like an array. It needs a walk from head.