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
Build the chain 10 → 20 → 30 with a Node class, then write length(head) that counts the nodes by walking the chain until it falls off the end. Print the length → 3.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(10, Node(20, Node(30)))
def length(head):
count = 0
current = head
while current is not None:
count += 1
current = current.next
return count
print(length(head))
⏩
Task 3: Insert at the Front
Tricky
Adding to the front of a linked list is O(1)! Build 10 → 20, then write push_front(head, value) that points the new node at the old head and returns it as the new head. Insert 99 and print every value.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(10, Node(20))
def push_front(head, value):
new_node = Node(value)
new_node.next = head
return new_node
head = push_front(head, 99)
current = head
while current is not None:
print(current.value)
current = current.next
🏋️ Extra Practice — Algorithm Reps
Linked lists are where pointers finally make sense. Draw the boxes and arrows on paper as you do each task — then code it.
➕
Task 4: Append to the End
Medium
Using the Node class, write append(head, value) that walks to the last node and hooks a new one on. Build a list 1 → 2 → 3 and print the values one per line.
1
2
3
class Node:
def __init__(self, value):
self.value = value
self.next = None
def append(head, value):
new_node = Node(value)
if head is None:
return new_node
current = head
while current.next is not None:
current = current.next
current.next = new_node
return head
head = None
for n in [1, 2, 3]:
head = append(head, n)
current = head
while current is not None:
print(current.value)
current = current.next
🔍
Task 5: Search the Chain
Medium
Write contains(head, target) that walks the chain and returns True if it finds the value. Build 4 → 8 → 15 and print the search for 8 and for 9.
True
False
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(4, Node(8, Node(15)))
def contains(head, target):
current = head
while current is not None:
if current.value == target:
return True
current = current.next
return False
print(contains(head, 8))
print(contains(head, 9))
🗑️
Task 6: Delete a Node
Tricky
Write delete(head, value) that removes the first node holding that value by making the previous node point past it. Build 1 → 2 → 3, delete 2, and print what is left.
1
3
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(1, Node(2, Node(3)))
def delete(head, value):
if head is not None and head.value == value:
return head.next
current = head
while current is not None and current.next is not None:
if current.next.value == value:
current.next = current.next.next
return head
current = current.next
return head
head = delete(head, 2)
current = head
while current is not None:
print(current.value)
current = current.next
🔃
Task 7: Reverse the List
Tricky
The famous interview question! Walk the chain flipping every arrow backwards, keeping track of previous, current and next. Reverse 1 → 2 → 3 → 4 and print the values.
4
3
2
1
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(1, Node(2, Node(3, Node(4))))
previous = None
current = head
while current is not None:
upcoming = current.next
current.next = previous
previous = current
current = upcoming
head = previous
current = head
while current is not None:
print(current.value)
current = current.next
🐢
Task 8: Find the Middle
Tricky
Use two pointers: a slow one moving one node at a time and a fast one moving two. When the fast one reaches the end, the slow one is in the middle. Print the middle value of 1 → 2 → 3 → 4 → 5.
3
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
print(slow.value)
🔁
Task 9: Boss Level: Detect a Loop
Boss
A broken linked list can point back on itself and loop forever. Use the slow/fast trick again: if the fast pointer ever catches the slow one, there is a cycle. Build 1 → 2 → 3 → back to 2, and print True, then a normal list printing False.
True
False
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
third = Node(3)
second = Node(2, third)
first = Node(1, second)
third.next = second # oops, a loop!
print(has_cycle(first))
clean = Node(1, Node(2, Node(3)))
print(has_cycle(clean))