Why Should You Care About Linked Lists?
Linked lists power many features you use every day
From music playlists to browser history to undo/redo, linked lists are the backbone of dynamic data management.
Music Playlist
Your music app uses a linked list for playlists! Each song points to the next one. Skip forward? Just follow the pointer. Add a song? Insert a new node!
Browser History
The back and forward buttons in your browser use a doubly linked list. Each page points to both the previous and next page you visited!
Undo/Redo in Apps
Text editors and Photoshop use linked lists for undo/redo. Each action is a node pointing to the previous state!
Photo Viewer
When you swipe through photos, that's a linked list! Each photo knows about the next and previous ones.
Operating System Tasks
Your OS uses linked lists to manage running programs. Each process is a node in the task queue!
Social Media Feed
Instagram and Twitter use linked lists for your feed. New posts are added at the head, and you scroll through the chain!
The Basics: What is a Linked List?
Think of a linked list as a train where each car is connected to the next one. You can only move from one car to the next through the connection. That's exactly how a linked list works!
Key Points:
- Each train car is a node
- The connection between cars is a pointer
- You start at the engine (HEAD) and follow connections
- The last car points to NULL (end of train)
- You can add cars anywhere by changing connections
Your First Linked List in Python
# Think of a Node as a train car with two parts:
# 1. Cargo (data) - what the car carries
# 2. Connector (next) - link to the next car
class Node:
def __init__(self, data):
self.data = data # The cargo this car carries
self.next = None # Connection to next car (initially none)
# Create our train cars
engine = Node("Engine") # First car (HEAD)
car1 = Node(10) # Second car
car2 = Node(20) # Third car
car3 = Node(30) # Fourth car
# Connect the cars together
engine.next = car1 # Engine connects to Car 1
car1.next = car2 # Car 1 connects to Car 2
car2.next = car3 # Car 2 connects to Car 3
# car3.next stays None (end of train)
# Travel through the train
current = engine
while current:
print(f"Visiting: {current.data}")
current = current.next # Move to next carCommon Mistake: Forgetting the NULL Check
When you reach the last node, current.next is None. Trying to access None.data crashes your program!
# ✘ WRONG - This will crash!
current = head
while True: # Infinite loop!
print(current.data)
current = current.next # Error when current becomes None!
# ✔ CORRECT - Always check if current exists
current = head
while current: # Stops when current becomes None
print(current.data)
current = current.nextTry It Yourself: Build a Linked List
Enter values separated by commas to create your own linked list!
Common Patterns
Pattern 1: Two Pointers (Tortoise and Hare)
Imagine a race where the hare runs twice as fast as the tortoise. This technique helps find the middle or detect cycles!
Finding the Middle Element
Start both pointers at the head. Move the slow pointer 1 step and the fast pointer 2 steps. When the fast pointer reaches the end, the slow pointer is at the middle!
Start: Both at the beginning
Move: Hare moves 2 steps, Tortoise moves 1 step
Result: When hare reaches end, tortoise is at middle!
def find_middle(head):
# Handle empty list
if not head:
return None
# Start both at the beginning
slow = head # Tortoise
fast = head # Hare
# Hare runs twice as fast
while fast and fast.next:
slow = slow.next # Tortoise: 1 step
fast = fast.next.next # Hare: 2 steps
# Tortoise is now at the middle!
return slow.data
# Example: List [1,2,3,4,5]
# Hare reaches end, Tortoise at 3 (middle)Pattern 2: Reversing a Linked List
Like turning a one-way street into the opposite direction!
def reverse_list(head):
# We need three pointers to reverse connections
prev = None # Previous node (starts as None)
current = head # Current node we're processing
while current:
# Save the next node before we change the pointer
next_temp = current.next
# Reverse the pointer (point backward instead of forward)
current.next = prev
# Move forward
prev = current
current = next_temp
# prev is now the new head
return prev
# Before: 1 → 2 → 3 → 4 → None
# After: 4 → 3 → 2 → 1 → NonePractice Problems
Easy Problem 1: Count Nodes in a Linked List
Given a linked list, count how many nodes it has. Think: how would you count train cars? Start at the engine and count each car until you reach the end!
Traverse the list from head to tail, incrementing a counter at each node. Stop when you hit None.
def count_nodes(head):
# Start counting from 0
count = 0
current = head
# Visit each node and count
while current:
count += 1
current = current.next
return count
# Time: O(n) - visit each node once
# Space: O(1) - only using a counterEasy Problem 2: Find Last Node
Find the last node in a linked list (the tail). The last node is the one whose next pointer is NULL!
Keep moving through nodes until you find one where .next is None.
def find_last(head):
# Handle empty list
if not head:
return None
current = head
# Keep going until we find a node with no next
while current.next:
current = current.next
return current.dataMedium Problem 3: Delete a Node by Value
Remove the first node that contains a specific value. Strategy: find the node BEFORE the one you want to delete, then skip over it!
Handle the special case where the head itself needs to be deleted. Then traverse until you find a node whose .next.data matches the target.
def delete_node(head, value):
# Special case: deleting the head
if head and head.data == value:
return head.next
current = head
while current and current.next:
if current.next.data == value:
# Skip over the node to delete it
current.next = current.next.next
break
current = current.next
return headAdvanced Techniques
Detecting Cycles - Floyd's Algorithm
What if the linked list loops back on itself? Use the tortoise and hare!
def has_cycle(head):
# Empty list has no cycle
if not head:
return False
slow = head # Tortoise
fast = head # Hare
while fast and fast.next:
slow = slow.next # Move 1 step
fast = fast.next.next # Move 2 steps
# If they meet, there's a cycle!
if slow == fast:
return True
# Hare reached the end, no cycle
return False
# Why it works: In a cycle, the faster runner
# will eventually lap the slower runner!Doubly Linked Lists
Each node has TWO pointers - to both next AND previous nodes!
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None # Points forward
self.prev = None # Points backward
# Advantages:
# - Can traverse in both directions
# - Easier deletion (no need to track previous)
# - Used in browser history, undo/redoQuick Reference
| Operation | What It Does | Time | Notes |
|---|---|---|---|
Insert at Head |
Add to beginning | O(1) | Instant - just change one pointer |
Insert at Tail |
Add to end | O(n) | Must find the end first |
Delete First |
Remove head | O(1) | Instant - just move head pointer |
Search |
Find a value | O(n) | Check each node one by one |
Access by Index |
Get nth element | O(n) | Walk through n nodes |
When to Use Linked Lists
Frequent insertion/deletion at beginning, unknown or dynamic size, no need for random access, implementing stacks/queues.
When NOT to Use Linked Lists
Need fast access by index, binary search required, cache performance matters, fixed size is known.
Common Interview Patterns
Two Pointers (find middle, detect cycle), Dummy Node (simplify edge cases), Recursion (reverse, merge lists), Fast & Slow (Floyd's algorithm).