Python LinkedList practice — 3 real programs that consolidate the structure
In the previous article we built the LinkedList from scratch. Now it’s time to extend it with real algorithms. In this article we implement three programs that go beyond basic insert and delete — searching with conditions, insertion sort and reversing a linked list. Each one deepens your understanding of how to traverse and manipulate the node chain.
We start from the complete LinkedList class built in the theory article. All three programs add methods to it.
Table of Contents
The base class
class LinkedList:
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
def __init__(self):
self.__first = None
self.__length = 0
def insert_front(self, value):
self.__first = self.Node(value, self.__first)
self.__length += 1
def insert_back(self, value):
new = self.Node(value)
if self.__first is None:
self.__first = new
else:
current = self.__first
while current.next_node is not None:
current = current.next_node
current.next_node = new
self.__length += 1
def delete(self, value):
if self.__first is None:
raise ValueError(f"{value} not in list")
if self.__first.value == value:
self.__first = self.__first.next_node
self.__length -= 1
return
previous = self.__first
current = self.__first.next_node
while current is not None:
if current.value == value:
previous.next_node = current.next_node
self.__length -= 1
return
previous = current
current = current.next_node
raise ValueError(f"{value} not in list")
def is_empty(self):
return self.__first is None
def __len__(self):
return self.__length
def __iter__(self):
current = self.__first
while current is not None:
value = current.value
current = current.next_node
yield value
def __str__(self):
return ' → '.join(str(v) for v in self) + ' → None'
def __contains__(self, value):
return any(v == value for v in self)
Python LinkedList Practice — Program 1: Search and count with conditions
This program adds a rich set of search and statistical methods to the LinkedList. All of them follow the same traversal pattern — they just do different things at each node.
class LinkedList(LinkedList): # extend the base class
def find_first(self, condition):
"""
Return the first value satisfying condition(value).
Returns None if not found.
"""
current = self.__first
while current is not None:
if condition(current.value):
return current.value
current = current.next_node
return None
def find_all(self, condition):
"""Return list of all values satisfying condition(value)."""
return [v for v in self if condition(v)]
def count_if(self, condition):
"""Count values satisfying condition(value)."""
return sum(1 for v in self if condition(v))
def minimum(self):
"""Return the minimum value. Raises ValueError if empty."""
if self.is_empty():
raise ValueError('Cannot find minimum of empty list')
current = self.__first
min_val = current.value
current = current.next_node
while current is not None:
if current.value < min_val:
min_val = current.value
current = current.next_node
return min_val
def maximum(self):
"""Return the maximum value. Raises ValueError if empty."""
if self.is_empty():
raise ValueError('Cannot find maximum of empty list')
current = self.__first
max_val = current.value
current = current.next_node
while current is not None:
if current.value > max_val:
max_val = current.value
current = current.next_node
return max_val
def average(self):
"""Return average of all values. Raises ValueError if empty."""
if self.is_empty():
raise ValueError('Cannot compute average of empty list')
total = sum(self)
return total / len(self)
def index_of(self, value):
"""Return 0-based index of first occurrence. Returns -1 if not found."""
current = self.__first
index = 0
while current is not None:
if current.value == value:
return index
current = current.next_node
index += 1
return -1
def get(self, index):
"""Return value at position index. Raises IndexError if out of range."""
if index < 0 or index >= len(self):
raise IndexError(f'Index {index} out of range (length {len(self)})')
current = self.__first
for _ in range(index):
current = current.next_node
return current.value
def to_list(self):
"""Convert to Python list."""
return list(self)
Using the search methods
# Build a list of grades
ll = LinkedList()
for grade in [7.5, 3.0, 8.5, 5.0, 9.5, 4.5, 6.0, 2.0, 8.0]:
ll.insert_back(grade)
print(f'List: {ll}')
print(f'Length: {len(ll)}')
# Basic search
print(f'\nMinimum: {ll.minimum()}')
print(f'Maximum: {ll.maximum()}')
print(f'Average: {ll.average():.2f}')
# Search with condition (lambda)
passing = ll.find_all(lambda g: g >= 5.0)
print(f'\nPassing grades: {passing}')
print(f'Count passing: {ll.count_if(lambda g: g >= 5.0)}')
print(f'Count failing: {ll.count_if(lambda g: g < 5.0)}')
# Find first outstanding grade
first_outstanding = ll.find_first(lambda g: g >= 9.0)
print(f'First outstanding: {first_outstanding}')
# Index operations
print(f'\nIndex of 8.5: {ll.index_of(8.5)}')
print(f'Index of 1.0: {ll.index_of(1.0)} (not found → -1)')
print(f'Element at [2]: {ll.get(2)}')
# Statistical breakdown
print(f'\n--- Grade breakdown ---')
categories = [
('Outstanding (9-10)', lambda g: g >= 9.0),
('Merit (7-8.9)', lambda g: 7.0 <= g < 9.0),
('Passed (5-6.9)', lambda g: 5.0 <= g < 7.0),
('Failed (0-4.9)', lambda g: g < 5.0),
]
for label, condition in categories:
count = ll.count_if(condition)
grades = ll.find_all(condition)
print(f' {label}: {count} → {grades}')
Output:
List: 7.5 → 3.0 → 8.5 → 5.0 → 9.5 → 4.5 → 6.0 → 2.0 → 8.0 → None Length: 9 Minimum: 2.0 Maximum: 9.5 Average: 5.94 Passing grades: [7.5, 8.5, 5.0, 9.5, 6.0, 8.0] Count passing: 6 Count failing: 3 First outstanding: 9.5 Index of 8.5: 2 Index of 1.0: -1 (not found → -1) Element at [2]: 8.5 --- Grade breakdown --- Outstanding (9-10): 1 → [9.5] Merit (7-8.9): 3 → [7.5, 8.5, 8.0] Passed (5-6.9): 2 → [5.0, 6.0] Failed (0-4.9): 3 → [3.0, 4.5, 2.0]
The lambda functions passed to find_first, find_all and count_if are the key technique — they let you write generalised traversal code once and apply any criterion you want. find_all(lambda g: g >= 5.0) and find_all(lambda g: g >= 9.0) use the same traversal logic but different filtering conditions. This is the equivalent of Python’s built-in filter() applied to a linked structure.
Python LinkedList Practice — Program 2: Insertion sort
Insertion sort on a linked list works differently from insertion sort on a Python list. Instead of shifting elements to make space, we remove the node and reinsert it in the correct position. The algorithm traverses the unsorted portion, picks each element and inserts it at the right position in the sorted portion.
def insertion_sort(self):
"""
Sort the list in ascending order using insertion sort.
Modifies the list in place.
Returns self for chaining.
"""
if self.__first is None or self.__first.next_node is None:
return self # empty or single element — already sorted
# Strategy: rebuild sorted list from scratch
# Take each node from original, insert in correct position in new list
sorted_first = None
current = self.__first
while current is not None:
next_node = current.next_node # save next before modifying current
# Find correct position in sorted portion
# Case 1: insert before sorted_first (new minimum)
if sorted_first is None or current.value <= sorted_first.value:
current.next_node = sorted_first
sorted_first = current
else:
# Case 2: find position in sorted portion
search = sorted_first
while (search.next_node is not None and
search.next_node.value < current.value):
search = search.next_node
# Insert current after search
current.next_node = search.next_node
search.next_node = current
current = next_node # advance to next unsorted node
self.__first = sorted_first
return self
def sort(self, reverse=False):
"""
Sort the list. Returns self for chaining.
Uses insertion sort.
"""
self.insertion_sort()
if reverse:
self.reverse() # we'll implement this in Program 3
return self
Step by step — sorting [5, 3, 8, 1, 4]
Start: 5 → 3 → 8 → 1 → 4 → None
sorted: (empty)
Take 5: sorted = 5 → None
Take 3: 3 < 5 → insert before 5
sorted = 3 → 5 → None
Take 8: 8 > 5 → insert after 5
sorted = 3 → 5 → 8 → None
Take 1: 1 < 3 → insert before 3
sorted = 1 → 3 → 5 → 8 → None
Take 4: 4 > 3, 4 < 5 → insert between 3 and 5
sorted = 1 → 3 → 4 → 5 → 8 → None
# Demo
ll = LinkedList()
for v in [5, 3, 8, 1, 9, 2, 7, 4, 6]:
ll.insert_back(v)
print(f'Unsorted: {ll}')
ll.insertion_sort()
print(f'Sorted: {ll}')
# Verify sorted property
values = ll.to_list()
assert values == sorted(values), "List not properly sorted!"
print('Verification: ✓ correctly sorted')
# Sort in reverse
ll2 = LinkedList()
for v in [3, 1, 4, 1, 5, 9, 2, 6]:
ll2.insert_back(v)
print(f'\nUnsorted: {ll2}')
ll2.sort(reverse=True)
print(f'Sorted reverse: {ll2}')
# Performance note
import time
ll3 = LinkedList()
import random
values = list(range(1000))
random.shuffle(values)
for v in values:
ll3.insert_back(v)
start = time.time()
ll3.insertion_sort()
elapsed = time.time() - start
print(f'\n1000 elements sorted in {elapsed:.4f}s')
print(f'First 5: {ll3.to_list()[:5]}')
print(f'Last 5: {ll3.to_list()[-5:]}')
Output:
Unsorted: 5 → 3 → 8 → 1 → 9 → 2 → 7 → 4 → 6 → None Sorted: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → None Verification: ✓ correctly sorted Unsorted: 3 → 1 → 4 → 1 → 5 → 9 → 2 → 6 → None Sorted reverse: 9 → 6 → 5 → 4 → 3 → 2 → 1 → 1 → None 1000 elements sorted in 0.0312s First 5: [0, 1, 2, 3, 4] Last 5: [995, 996, 997, 998, 999]
The key line is next_node = current.next_node saved before modifying current. When you change current.next_node to point somewhere else (the insertion step), you’d lose track of where to continue in the original unsorted list if you hadn’t saved it first. This is the most common mistake in node manipulation — always save what you need before modifying anything.
Python LinkedList Practice — Program 3: Reverse the list
Reversing a linked list has two approaches. The iterative approach is more efficient and easier to understand with a diagram. The recursive approach is shorter but uses call stack space proportional to the list length.
Iterative approach
The idea: traverse the list and flip each arrow — make every node point backwards instead of forwards.
Before: None ← [1] ← [2] ← [3] → None
first last
After: None ← [3] ← [2] ← [1] → None
first last
We need three pointers: previous (starts as None), current (starts at first) and next_node (saved before modification).
Step 0: previous=None, current=[1], next=?
Step 1: save next=[2], flip [1].next=None, advance:
previous=[1], current=[2]
Step 2: save next=[3], flip [2].next=[1], advance:
previous=[2], current=[3]
Step 3: save next=None, flip [3].next=[2], advance:
previous=[3], current=None → STOP
first = previous = [3]
Result: [3] → [2] → [1] → None
def reverse(self):
"""
Reverse the list in place.
Returns self for chaining.
"""
previous = None
current = self.__first
while current is not None:
next_node = current.next_node # 1. save next
current.next_node = previous # 2. flip the arrow
previous = current # 3. advance previous
current = next_node # 4. advance current
self.__first = previous # previous is now the new first (old last)
return self
def reverse_recursive(self):
"""
Reverse the list in place using recursion.
Note: uses O(n) stack space — prefer iterative for long lists.
"""
def _reverse(node):
if node is None or node.next_node is None:
return node # base case: empty or single node — new head
new_head = _reverse(node.next_node) # recurse to end
node.next_node.next_node = node # flip arrow
node.next_node = None # current's next is now None
return new_head
self.__first = _reverse(self.__first)
return self
def is_palindrome(self):
"""Return True if the list reads the same forwards and backwards."""
values = self.to_list()
return values == values[::-1]
def get_middle(self):
"""
Return the value at the middle position using two-pointer technique.
For even length, returns the second middle element.
"""
if self.is_empty():
raise ValueError('Empty list has no middle')
slow = self.__first # moves 1 step at a time
fast = self.__first # moves 2 steps at a time
while fast is not None and fast.next_node is not None:
slow = slow.next_node
fast = fast.next_node.next_node
return slow.value
The two-pointer technique in get_middle is a classic linked list trick. When fast reaches the end, slow is at the middle — because fast moves twice as fast. For a list of 9 elements, fast takes 4 steps (reaching element 8 or None) while slow takes 4 steps (reaching element 4 — the middle).
Demo
# Reverse
ll = LinkedList()
for v in [1, 2, 3, 4, 5]:
ll.insert_back(v)
print(f'Original: {ll}')
ll.reverse()
print(f'Reversed: {ll}')
ll.reverse()
print(f'Re-reversed: {ll}')
# Palindrome detection
palindromes = [
([1, 2, 3, 2, 1], True),
([1, 2, 3, 4, 5], False),
([5], True),
([1, 1], True),
([1, 2, 1], True),
]
print(f'\n--- Palindrome detection ---')
for values, expected in palindromes:
ll = LinkedList()
for v in values: ll.insert_back(v)
result = ll.is_palindrome()
status = '✓' if result == expected else '✗'
print(f' {status} {values} → {result}')
# Middle element
print(f'\n--- Middle element (two-pointer technique) ---')
for size in [1, 3, 5, 6, 9]:
ll = LinkedList()
for v in range(1, size + 1): ll.insert_back(v)
middle = ll.get_middle()
print(f' {list(range(1, size + 1))} → middle: {middle}')
# Chain: sort + reverse
ll = LinkedList()
for v in [5, 3, 8, 1, 9, 2, 7]:
ll.insert_back(v)
print(f'\nUnsorted: {ll}')
ll.sort()
print(f'Sorted ascending: {ll}')
ll.reverse()
print(f'Sorted descending: {ll}')
Output:
Original: 1 → 2 → 3 → 4 → 5 → None Reversed: 5 → 4 → 3 → 2 → 1 → None Re-reversed: 1 → 2 → 3 → 4 → 5 → None --- Palindrome detection --- ✓ [1, 2, 3, 2, 1] → True ✓ [1, 2, 3, 4, 5] → False ✓ [5] → True ✓ [1, 1] → True ✓ [1, 2, 1] → True --- Middle element (two-pointer technique) --- [1] → middle: 1 [1, 2, 3] → middle: 2 [1, 2, 3, 4, 5] → middle: 3 [1, 2, 3, 4, 5, 6] → middle: 4 [1, 2, 3, 4, 5, 6, 7, 8, 9] → middle: 5 Unsorted: 5 → 3 → 8 → 1 → 9 → 2 → 7 → None Sorted ascending: 1 → 2 → 3 → 5 → 7 → 8 → 9 → None Sorted descending: 9 → 8 → 7 → 5 → 3 → 2 → 1 → None
Visualise with Python Tutor
Copy this code into pythontutor.com and step through it:
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
# Build list: 1 → 2 → 3 → None
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.next_node = n2
n2.next_node = n3
first = n1
# Reverse iteratively
previous = None
current = first
while current is not None:
next_node = current.next_node # save
current.next_node = previous # flip
previous = current # advance
current = next_node # advance
first = previous # new head
# Print reversed list
current = first
while current is not None:
print(current.value)
current = current.next_node
Step through the reverse algorithm and watch each arrow flip direction. Before the loop: 1 → 2 → 3 → None. After step 1 (processing node 1): node 1’s arrow flips to point at previous=None — None ← 1, and previous now points to node 1. After step 2 (processing node 2): node 2’s arrow flips to point at previous=node1 — None ← 1 ← 2. After step 3 (processing node 3): node 3’s arrow flips to None ← 1 ← 2 ← 3. When current=None, the loop ends and first = previous = node3. The visual is worth ten minutes of reading. Pay attention to the order: always save next_node first, then flip, then advance both pointers.
Summary and next step
In this article you extended the LinkedList with three families of algorithms. The search methods showed how lambda conditions generalise traversal without rewriting the loop. Insertion sort showed the key pattern for in-place node rearrangement — save next_node before any modification. The reversal showed the three-pointer technique that flips every arrow in a single pass, plus the two-pointer technique that finds the middle in O(n) without knowing the length.
In the next article you’ll find exercises to solve on your own — including cycle detection, merging two sorted lists and a doubly linked list.
One Comment