Python LinkedList practice — loans, the reservation queue backwards and the sorted catalogue (three library programs)

The first time I programmed the reversal of a linked list, the test printed Laura → None | len = 5. Five reservations according to len, a single one according to the list. No red error at all: the program finished as calm as anything. What had happened is that I had changed an arrow before saving where it pointed, and the rest of the queue went with it. That line of output is the best lesson in the topic, and you’ll see it with your own eyes in program 2.

In the Python LinkedList theory we built the LinkedList class with the reservation queue for a library book. Now we extend it with three medium-level programs, the kind that comes up in the second FP2 exam: loan statistics by traversing the list, reversing the queue in two ways (one of them without creating a single new node) and sorting the catalogue by insertion. The data look like real data: loans past the deadline, empty queues or queues with one person, repeated years. The library rules (15-day loans) are made up for the example.

Before you start

It helps to be clear about:

• What the LinkedList class from the theory looks like: inner Node, private head __first and __length, and the methods insert_front, insert_back, remove, contains, __iter__, __len__ and __str__.
• The traversal pattern: current = current.next_node until None.
• The golden rule: link first, move afterwards.
• That inside a subclass self.__first doesn’t work: you have to write self._LinkedList__first (we saw it in the theory, in “Inheriting from LinkedList”).

If any of these sounds shaky, review the theory before carrying on.

Program 1: search and count with conditions

The library keeps how long each loan of the week lasted, in days: 15, 8, 42, 3, 27, 19, 8, 11, 35, 8. We want to know how many there are, the total, the average, the longest and the shortest, how many went past the 15-day deadline, and a new list with only the late ones. What makes it tricky: exactly 15 days is not late, there are repeated values and the list could be empty.

The idea

All the queries are the same traversal with different work inside the loop: counting, adding, keeping the largest… As LinkedList already has __iter__, we can traverse with a normal for and not touch a single node: we don’t even need the parent’s private attribute.

To avoid writing one method per question (“how many over 15”, “how many of 8″…), count receives the condition as a function: a lambda that says True or False for each value. And filter_by builds a new list with insert_back, to keep the order.

The code

from linked_list import LinkedList

LOAN_DAYS = 15   # days a normal loan lasts (rule made up for the example)


class LoanList(LinkedList):
    """LinkedList with how many days each loan lasted and queries that traverse it."""

    def count(self, condition=None):
        """How many meet the condition (a function returning True/False). With no condition, all of them."""
        counter = 0
        for days in self:                   # the parent's __iter__: node by node
            if condition is None or condition(days):
                counter += 1
        return counter

    def sum_days(self):
        total = 0
        for days in self:
            total += days
        return total

    def average(self):
        if self.is_empty():                 # we avoid dividing by 0
            raise ValueError("the list is empty")
        return self.sum_days() / len(self)

    def maximum(self):
        if self.is_empty():
            raise ValueError("the list is empty")
        largest = None
        for days in self:
            if largest is None or days > largest:   # the first one always gets in
                largest = days
        return largest

    def minimum(self):
        if self.is_empty():
            raise ValueError("the list is empty")
        smallest = None
        for days in self:
            if smallest is None or days < smallest:
                smallest = days
        return smallest

    def filter_by(self, condition):
        """NEW list with the ones meeting the condition; the original does not change."""
        result = LoanList()
        for days in self:
            if condition(days):
                result.insert_back(days)   # at the back: keeps the original order
        return result


loans = LoanList()
for days in [15, 8, 42, 3, 27, 19, 8, 11, 35, 8]:
    loans.insert_back(days)

print("Loans (days):", loans)
print("Count:", len(loans))
print("Total:", loans.sum_days(), "days")
print(f"Average: {loans.average():.2f} days")
print("Maximum:", loans.maximum(), "days | Minimum:", loans.minimum(), "days")
print()
print("Late (more than 15):", loans.count(lambda d: d > LOAN_DAYS))
print("Returned on the last day:", loans.count(lambda d: d == LOAN_DAYS))
print("Of 8 days:", loans.count(lambda d: d == 8))
print("All:", loans.count())
late = loans.filter_by(lambda d: d > LOAN_DAYS)
print()
print("Late ones:", late)
print("Days late:", [days - LOAN_DAYS for days in late])
print("Original intact:", loans)
empty = LoanList()
try:
    empty.maximum()
except ValueError as error:
    print("Empty list → ValueError:", error)

Output

Loans (days): 15 → 8 → 42 → 3 → 27 → 19 → 8 → 11 → 35 → 8 → None
Count: 10
Total: 176 days
Average: 17.60 days
Maximum: 42 days | Minimum: 3 days

Late (more than 15): 4
Returned on the last day: 1
Of 8 days: 3
All: 10

Late ones: 42 → 27 → 19 → 35 → None
Days late: [27, 12, 4, 20]
Original intact: 15 → 8 → 42 → 3 → 27 → 19 → 8 → 11 → 35 → 8 → None
Empty list → ValueError: the list is empty

Let’s check it by hand. The total: 15 + 8 + 42 + 3 + 27 + 19 + 8 + 11 + 35 + 8 = 176, and the average 176 / 10 = 17.6. Late (more than 15) there are four: 42, 27, 19 and 35. The one with exactly 15 does not count as late: that’s why “Returned on the last day” is 1. The days late are 42 − 15 = 27, 27 − 15 = 12, 19 − 15 = 4 and 35 − 15 = 20. And filter_by keeps them in the order they were in, because it inserts at the back.

This is the trace of maximum() in its first laps:

Lap	days	largest before	largest is None or days > largest?	largest after
1	15	None	Yes (first lap)	15
2	8	15	No	15
3	42	15	Yes	42
4	3	42	No	42
5-10	27, 19, 8, 11, 35, 8	42	No	42

Questions you might ask

Why largest = None and not largest = 0? With loan days it would work, but if the list ever stores negative temperatures, 0 would be a false maximum. None + “the first lap always gets in” works for any data.

Why does filter_by use insert_back and not insert_front? Because insert_front would reverse the order: the late ones would come out 35 → 19 → 27 → 42. On the other hand, insert_back is O(n) on each insertion, so filter_by is O(n²) in the worst case. With ten loans it doesn’t matter; it would be avoided by also storing a reference to the last node in the class, as well as the head.

What exactly is lambda d: d > LOAN_DAYS? A nameless function that receives d and returns d > LOAN_DAYS. count calls it once per node: condition(days). It is the same as defining def is_late(d): return d > LOAN_DAYS and passing is_late.

Why does average check for the empty list if sum_days already does? sum_days of an empty list is 0, which is correct. The problem is dividing by len(self), which would be 0: ZeroDivisionError. We prefer a ValueError with a message that says what’s going on.

Why isn’t _LinkedList__first needed here? Because we only read values, and the parent’s for is enough for that. It’s option B from the theory: the less you touch the nodes, the less you can break.

Try it yourself

• Add filter_and_remove(condition), which as well as returning the new list removes from the original the ones meeting the condition (use remove).
• Change maximum so it also returns at which position it is (0 for the head) without traversing twice.

Program 2: reverse a linked list

The library wants to notify the reservation queue from the last to the first (the rule is made up, but the problem is an exam classic). We want two versions: one that returns a new reversed queue leaving the original as it was, and another that turns the queue itself round, reusing the same nodes. What makes the second one tricky: every arrow has to change without losing the way, and the queue can be empty or have just one person.

The idea

• New list: traverse the original from left to right and keep inserting at the front of the new one. The first in ends up last. It’s easy, but it creates a new node for every reservation.
• In the same place (in-place): traverse with three variables: previous, current and next_node. On each lap, the arrow of current stops pointing forwards and points to previous instead. Before turning it, you have to save in next_node where it pointed, or we won’t be able to move on.

Strategy 1: create a new list (easy to understand)

def reverse_new(self):
    """Strategy 1: a NEW list inserting each value at the front (the original does not change)."""
    result = ReversibleQueue()
    for member in self:              # from left to right...
        result.insert_front(member)  # ...and each one goes in front of the one before
    return result

Each insert_front is O(1), so reversing like this is O(n), but it uses a new node per reservation.

Strategy 2: reverse in the same place (in-place)

def reverse_inplace(self):
    """Strategy 2: turn round the arrows of the SAME nodes."""
    previous = None
    current = self._LinkedList__first    # the parent's private attribute (name mangling)
    while current is not None:
        next_node = current.next_node    # 1. save the rest BEFORE touching anything
        current.next_node = previous     # 2. turn the arrow round
        previous = current               # 3. move previous on...
        current = next_node              # 4. ...and current
    self._LinkedList__first = previous   # the new head is the old tail

Here we do need the nodes, so we use self._LinkedList__first (option A from the theory). Look at the drawing lap by lap:

And the same trace as a table, with the three-person queue from the drawing:

Lap	current	next_node (saved)	Arrow turned	previous after	current after
1	Laura	Pablo	Laura → None	Laura	Pablo
2	Pablo	Marta	Pablo → Laura	Pablo	Marta
3	Marta	None	Marta → Pablo	Marta	None
End	—	—	first = previous	Marta is the head

The full program, with the five-person queue and the odd cases:

from linked_list import LinkedList


class ReversibleQueue(LinkedList):

    def reverse_new(self):
        """Strategy 1: a NEW list inserting each value at the front (the original does not change)."""
        result = ReversibleQueue()
        for member in self:                 # from left to right...
            result.insert_front(member)     # ...and each one goes in front of the one before
        return result

    def reverse_inplace(self):
        """Strategy 2: turn round the arrows of the SAME nodes."""
        previous = None
        current = self._LinkedList__first   # the parent's private attribute (name mangling)
        while current is not None:
            next_node = current.next_node   # 1. save the rest BEFORE touching anything
            current.next_node = previous    # 2. turn the arrow round
            previous = current              # 3. move previous on...
            current = next_node             # 4. ...and current
        self._LinkedList__first = previous  # the new head is the old tail


queue = ReversibleQueue()
for member in ["Laura", "Pablo", "Marta", "Iván", "Nora"]:
    queue.insert_back(member)
print("Queue:", queue)

reversed_queue = queue.reverse_new()
print("Reversed (new): ", reversed_queue)
print("Original intact:", queue)

queue.reverse_inplace()
print("After reverse_inplace:", queue, "| len =", len(queue))

empty = ReversibleQueue()
empty.reverse_inplace()
print("Empty reversed:", empty)
alone = ReversibleQueue()
alone.insert_front("Ana")
alone.reverse_inplace()
print("A single node reversed:", alone)

Output

Queue: Laura → Pablo → Marta → Iván → Nora → None
Reversed (new):  Nora → Iván → Marta → Pablo → Laura → None
Original intact: Laura → Pablo → Marta → Iván → Nora → None
After reverse_inplace: Nora → Iván → Marta → Pablo → Laura → None | len = 5
Empty reversed: None
A single node reversed: Ana → None

The new reversed queue and the one reversed in place give the same, Nora → Iván → Marta → Pablo → Laura, but the first left the original intact and the second changed it. len is still 5: reversing adds and removes no nodes, so __length doesn’t need touching. With the empty queue the loop doesn’t run once (current starts at None) and with a single person it runs once, pointing Ana to None, which is what she already did.

Now, the version from my story: the same program with the first two lines of the loop swapped.

def reverse_inplace(self):
    """Strategy 2: turn round the arrows of the SAME nodes."""
    previous = None
    current = self._LinkedList__first    # the parent's private attribute (name mangling)
    while current is not None:
        current.next_node = previous     # WRONG: we turn the arrow round first...
        next_node = current.next_node    # ...and "the rest" is already previous (None)
        previous = current               # 3. move previous on...
        current = next_node              # 4. ...and current
    self._LinkedList__first = previous   # the new head is the old tail

Output:

Queue: Laura → Pablo → Marta → Iván → Nora → None
Reversed (new):  Nora → Iván → Marta → Pablo → Laura → None
Original intact: Laura → Pablo → Marta → Iván → Nora → None
After reverse_inplace: Laura → None | len = 5
Empty reversed: None
A single node reversed: Ana → None

On the first lap, current.next_node = previous sets Laura’s arrow to None, and then next_node = current.next_node saves… None. The loop ends after one lap, first becomes Laura and the other four nodes are left with nothing pointing to them. len still says 5 because nobody touched it: a list and its length can contradict each other if you break the links by hand.

Questions you might ask

Why three variables and not two? Because at the moment you turn the arrow of current you need to know two more nodes: who it will point to (previous) and where to carry on (next_node). With two variables you lose one of them.

Why first = previous at the end and not first = current? Because the loop ends when current is None. The last node we processed, the old tail, is in previous.

Do you need an if for the empty list? No. current starts at None, the while doesn’t run and first = previous leaves None. The special case comes out on its own, and the output confirms it.

Which one is better? In-place uses no extra memory (O(1)); the new one keeps the original. In the exam, if they say “reverse the list” they usually want in-place; if they say “return a reversed list”, the other one.

Can it be done with recursion? Yes, but each node is a call on the stack: with a queue of ten thousand reservations Python raises RecursionError. The iterative one has no such limit.

Try it yourself

• Write reverse_from(position), which leaves the first nodes as they are and reverses only from that position on.
• Add an is_palindrome() method to ReversibleQueue that says whether the queue reads the same forwards and backwards (use reverse_new and compare with a zip).

Program 3: sort a LinkedList by insertion

The returns trolley brings books from 2008, 1985, 2019, 1994, 2011, 1978 and 2003, and we want the catalogue from oldest to newest. We solve it with the most natural sort for a linked list: insertion sort. What makes it tricky: the new value can go before all of them, in the middle or at the end, the list can be empty and there can be repeated years.

The idea

First a helper method, insert_sorted(value), which puts a value in its place in a list that is already sorted. Then sorted_copy() creates a new empty list and inserts in order each value of the original. An empty list or a one-element list is already sorted, so the result always is.

For insert_sorted there are two cases: if it goes before the head (or the list is empty), it’s an insert_front; otherwise, we look for the last node smaller than the value and hook the new one on after it.

The code: build the sorted list

from linked_list import LinkedList


class SortableList(LinkedList):

    def insert_sorted(self, value):
        """Inserts value in its place, keeping the list from smallest to largest."""
        first = self._LinkedList__first
        if first is None or value <= first.value:   # case 1: empty, or it goes before all of them
            self.insert_front(value)                # we reuse it: it already adds to the length
            return
        current = first
        while current.next_node is not None and current.next_node.value < value:
            current = current.next_node             # we stop at the LAST one smaller than value
        current.next_node = self.Node(value, current.next_node)   # new → rest, current → new
        self._LinkedList__length += 1

    def sorted_copy(self):
        """Insertion sort: a NEW sorted list; the original does not change."""
        result = SortableList()
        for value in self:
            result.insert_sorted(value)
        return result


catalogue = SortableList()          # publication years of the books in the returns trolley
for year in [2008, 1985, 2019, 1994, 2011, 1978, 2003]:
    catalogue.insert_back(year)
print("Original:", catalogue)
print("Sorted:", catalogue.sorted_copy())
print("Original intact:", catalogue)

print()
print("Empty:", SortableList().sorted_copy())
equal = SortableList()
for year in [2020, 2020, 2020]:
    equal.insert_back(year)
print("Equal:", equal.sorted_copy())

print()
step = SortableList()
for year in [2008, 1985, 2019, 1994, 2011]:
    step.insert_sorted(year)
    print(f"After inserting {year}: {step} (len {len(step)})")

The delicate part is the loop in insert_sorted:

while current.next_node is not None and current.next_node.value < value:
    current = current.next_node                   # we stop at the LAST one smaller than value
current.next_node = self.Node(value, current.next_node)   # new → rest, current → new
self._LinkedList__length += 1

The condition has two parts and the order matters: first current.next_node is not None (that there is a next node) and only then current.next_node.value < value. Swap them and, at the end, Python asks for None.value. When the loop stops, the last line creates the new node already pointing to the rest and hooks current onto it: link first, move afterwards, in a single assignment.

Output

Original: 2008 → 1985 → 2019 → 1994 → 2011 → 1978 → 2003 → None
Sorted: 1978 → 1985 → 1994 → 2003 → 2008 → 2011 → 2019 → None
Original intact: 2008 → 1985 → 2019 → 1994 → 2011 → 1978 → 2003 → None

Empty: None
Equal: 2020 → 2020 → 2020 → None

After inserting 2008: 2008 → None (len 1)
After inserting 1985: 1985 → 2008 → None (len 2)
After inserting 2019: 1985 → 2008 → 2019 → None (len 3)
After inserting 1994: 1985 → 1994 → 2008 → 2019 → None (len 4)
After inserting 2011: 1985 → 1994 → 2008 → 2011 → 2019 → None (len 5)

The step by step in the last lines is the full trace of insert_sorted:

Insert	Case	current stops at	List after
2008	Empty: front	—	2008
1985	1985 ≤ 2008: front	—	1985 → 2008
2019	At the end	2008 (its next is None)	1985 → 2008 → 2019
1994	In the middle	1985 (2008 is no longer < 1994)	1985 → 1994 → 2008 → 2019
2011	In the middle	2008 (2019 is no longer < 2011)	1985 → 1994 → 2008 → 2011 → 2019

And len goes up one at a time: the “front” case is counted by insert_front and the general case by the line self._LinkedList__length += 1.

Questions you might ask

Why <= in case 1 and < in the loop? With equal years the order doesn’t matter, but this way a value equal to the head goes in at the front without traversing anything. The important thing is not to leave a gap: with < in case 1, a repeated 1985 would go to the loop and would also work, just traversing.

Why does sorted_copy return a new list? So as not to destroy the original: catalogue comes out intact. If you wanted to sort in place, you could do self._LinkedList__first = result._LinkedList__first at the end.

How much does it cost? Each insert_sorted traverses at most the already sorted list, so in the worst case it’s O(n²). If the data arrive almost sorted from smallest to largest… it traverses almost the whole list every time. With data almost sorted from largest to smallest it’s O(n), because they all go in at the front.

Why reuse insert_front in case 1? Because it already does both things right: linking in the correct order and adding to the length. Rewriting it is one more chance to get it wrong.

Try it yourself

• Change insert_sorted to sort from newest to oldest by touching only two comparisons.
• Add insert_without_repeats(value), which doesn’t insert a year if it’s already there (think where to check so you don’t traverse twice).

The pattern you should take away

The three programs are three patterns that repeat in every LinkedList exercise:

Pattern	When	Skeleton
Traversal with an accumulator	Count, add up, maximum, filter	for value in self: and update the accumulator
Three variables	Turning arrows (reversing)	next_node = current.next_node, turn, move previous and current on
Stop at the previous node	Insert in order, insert at a position, delete	while current.next_node is not None and condition: and hook on

Common mistakes in this practice

• Using self.__first in the subclass. Python looks for _SortableList__first and raises AttributeError. Use self._LinkedList__first or the parent’s for.
• Turning an arrow without saving the next node first. The list is left with one node and len doesn’t notice.
• Checking current.next_node.value before current.next_node is not None. On the last node it asks for None.value.
• Forgetting to update __length in methods that add nodes without going through insert_front/insert_back.
• Building the result with insert_front when you wanted to keep the order. It comes out backwards.
• Not testing the empty list and the one-element list. They are the ones that break programs in the exam.

Watch it step by step in Python Tutor

In-place reversal is the program that gains most from Python Tutor: you see every arrow turn. Choose Python 3 and paste:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value          # the data: who made the reservation
        self.next_node = next_node  # reference to the next node (None if it is the last one)

# Queue: Laura → Pablo → Marta → None
laura = Node("Laura")
pablo = Node("Pablo")
marta = Node("Marta")
laura.next_node = pablo
pablo.next_node = marta
first = laura

previous = None
current = first
while current is not None:
    next_node = current.next_node   # 1. save the rest
    current.next_node = previous    # 2. turn the arrow round
    previous = current              # 3. move previous on
    current = next_node             # 4. move current on
first = previous                    # new head: Marta
print(first.value, first.next_node.value, first.next_node.next_node.value)

Output:

Marta Pablo Laura

What to watch step by step:

1. Before the loop: three nodes with the arrows pointing right, previous at None and current on Laura.
2. First lap, line 1: next_node points to Pablo. It’s the “rope” that stops you losing the rest.
3. Line 2: Laura’s arrow jumps to None. At this moment Laura is alone, and only next_node links us to Pablo.
4. At the end of the third lap every arrow points left and current is None.
5. Swap lines 1 and 2 of the loop and run it again: you’ll see the loop end after one lap, with Pablo and Marta left with no arrows reaching them.

Summary and next step

• To read values the parent’s for is enough: no need to touch nodes or private attributes.
• filter_by with insert_back keeps the order; with insert_front, it reverses it.
• Reversing in place is three variables and a fixed order: save, turn, move on.
• To insert in order you have to stop at the node before the gap, checking first that there is a next node.
• If you change nodes by hand from a subclass, self._LinkedList__length is your job too.
• Always test the empty list and the one-element list.

Checklist: have you practised it?

• Have you run the three programs and checked the outputs?
• Can you explain why reverse_inplace doesn’t need an if for the empty list?
• Can you write from memory the four lines of the reversal loop in the right order?
• Do you understand why the condition in the insert_sorted loop has to go in that order?
• Have you tried the “Try it yourself” tasks without looking at the theory?

If you answered yes to almost everything, you’re ready for the Python LinkedList exercises, where I no longer give you the code. See you there!

Next step: exercisesPython LinkedList exercises — reservation number N, repeated members and the queue that never ends (with solutions and a cheat sheet)

Did this article help you? Here is how you can support SergioLearns →