A linked list is a chain of nodes. Each node holds a piece of data and a pointer to the next node — like train cars coupled together. The last node points to None.
[ 3 | •]──>[ 7 | •]──>[ 9 | None ]
head
Unlike a Python list (stored in one solid block of memory), a linked list's nodes can live anywhere — they're connected only by their pointers.
🧱 Building a Node
We use a class with two attributes: data and next.
class Node:
def __init__(self, data):
self.data = data
self.next = None # points to nothing yet
# Link them by hand
a = Node(3)
b = Node(7)
a.next = b # 3 now points to 7
print(a.data) # 3
print(a.next.data) # 7
🚶 Walking the list (traversal)
To visit every node, start at the head and follow .next until you hit None:
current = head
while current is not None:
print(current.data)
current = current.next # hop to the next node
⚖️ Linked list vs. array
Operation
Array / list
Linked list
Get by index
O(1)
O(n)
Insert at front
O(n)
O(1)
Memory
One solid block
Scattered nodes
💡 When to use which
Linked lists shine when you add/remove at the front a lot. Arrays win when you need fast index access. Python's built-in list is an array — but knowing linked lists helps you understand stacks, queues, and trees.
✅ What you learned
A linked list is nodes connected by .next pointers.
Each node has data and a pointer; the last points to None.
Traverse by following .next from the head.
Fast inserts at the front, but slow index access.
🎮 Time to Practice!
Build a chain of nodes from scratch. 🔗
🚂
Task 1: Link & Traverse
Medium
Three nodes are created. Link them 1 → 2 → 3, then traverse from head printing each value. Output: 1, 2, 3.
class Node:
def __init__(self, data):
self.data = data
self.next = None
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
head = a
current = head
while current is not None:
print(current.data)
current = current.next
📏
Task 2: Count the Nodes
Medium
Write length(head) that counts nodes by walking the chain. The list 10 → 20 → 30 has length 3.
def length(head):
count = 0
current = head
while current is not None:
count += 1
current = current.next
return count
⏩
Task 3: Insert at the Front
Tricky
Adding to the front of a linked list is O(1)! Make the new node point to the old head, then return the new node as the new head. Insert 99 before 10 → 20 → prints 99, 10, 20.