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

In a mock exam I wrote the cycle detector comparing names instead of nodes. I tested it with a normal queue of six members in which Marta appeared twice, and my program answered, very sure of itself, that there was a cycle. There wasn’t: there were two people with the same name. You’ll see it in fragment 3 of “What’s wrong here?”, with the real output.

You’ve seen the theory and practised with three library programs. Now it’s your turn. Three exercises at three levels on the same reservation queue: reading the reservation at a position (from the front and from the back), removing repeated members without creating a new list and detecting whether the queue has a cycle without using extra memory. All three go after the two errors that wreck a LinkedList most often: going one node too far and changing an arrow at the wrong moment.

How to use this article: try each exercise on your own; if you’ve been stuck for more than ten minutes, open the hint; before looking at the solution, do “What’s wrong here?”, and paste your code into Python Tutor to see the arrows. At the end there’s an exam-style quiz and the topic’s cheat sheet.

In all three exercises you add methods to the LinkedList class from the theory (inside the class itself, so self.__first and self.__length work without tricks).

Python LinkedList exercises: basic level

Exercise 1: get the element at position N

Add to LinkedList a method get_at(position) that returns the value at that position, starting at 0 for the head. If the position doesn’t exist (negative, or greater than or equal to the length), raise IndexError with the message in the output.

Then the challenge: get_from_back(position), where 0 is the last one, 1 the one before last… without using the length and in a single traversal.

With the queue Laura → Pablo → Marta → Iván → Nora, the output must be:

Queue: Laura → Pablo → Marta → Iván → Nora → None
get_at(0) → Laura
get_at(2) → Marta
get_at(4) → Nora
get_at(5) → IndexError: position 5 out of range (length 5)
get_at(-1) → IndexError: position -1 out of range (length 5)
get_from_back(0) → Nora
get_from_back(1) → Iván
get_from_back(4) → Laura
get_from_back(5) → IndexError: position 5 out of range

Python LinkedList exercises: intermediate level

Exercise 2: remove duplicates from a LinkedList

Some members reserve the same book two or three times. Add a method remove_duplicates() that keeps only the first occurrence of each value, changing the list itself (without creating another one) and keeping len correct. It must work with the empty list and with a list without repeats.

Expected output with these four queues:

Before:  Laura → Pablo → Laura → Marta → Pablo → Iván → Laura → None (len 7)
After:   Laura → Pablo → Marta → Iván → None (len 4)
Before:  Ana → Nora → Iván → None (len 3)
After:   Ana → Nora → Iván → None (len 3)
Before:  Marta → Marta → Marta → Marta → None (len 4)
After:   Marta → None (len 1)
Before:  None (len 0)
After:   None (len 0)

Python LinkedList exercises: final challenge

Exercise 3: detect whether a LinkedList has a cycle

A list has a cycle when some node, instead of leading towards None, points back to an earlier one. Traversing it with the usual while current is not None never ends (neither does print(queue) or len(list(queue))).

Write has_cycle(), which returns True or False without changing the list and with O(1) memory: no storing the visited nodes in a set. For testing, also write create_cycle(position), which makes the last node point to the node at that position. With show_steps=True, has_cycle prints each step.

Expected output:

Normal: False
With a cycle (Iván → Pablo):
  step 1: tortoise on Pablo, hare on Marta
  step 2: tortoise on Marta, hare on Pablo
  step 3: tortoise on Iván, hare on Iván
Result: True
Empty: False
One node without a cycle: False
One node with a cycle: True
Six members, Marta twice, no cycle: False

What’s wrong here?

Three fragments with an error of the kind that comes up in exams. Predict what each one prints before reading the explanation.

Fragment 1: the duplicates that don’t go away

remove_duplicates with a single line changed (the one marked WRONG):

def remove_duplicates(self):
    """Keeps only the first occurrence of each value, changing the list itself."""
    if self.__first is None:           # empty: nothing to do
        return
    seen = {self.__first.value}        # the head is never a duplicate: it is the first
    previous = self.__first
    current = self.__first.next_node
    while current is not None:
        if current.value in seen:
            previous.next_node = current.next_node   # we skip the duplicate
            self.__length -= 1
            previous = current                       # WRONG: we also move on when deleting
        else:
            seen.add(current.value)
            previous = current
        current = current.next_node

Output:

Before:  Laura → Pablo → Laura → Marta → Pablo → Iván → Laura → None (len 7)
After:   Laura → Pablo → Marta → Iván → None (len 4)
Before:  Ana → Nora → Iván → None (len 3)
After:   Ana → Nora → Iván → None (len 3)
Before:  Marta → Marta → Marta → Marta → None (len 4)
After:   Marta → Marta → None (len 1)
Before:  None (len 0)
After:   None (len 0)

What happens: with the first queue it works, because the repeats aren’t next to each other. With four Martas in a row it leaves Marta → Marta and, on top of that, len says 1. When node 2 is deleted, previous moves on to node 2, which is already out of the chain. When node 3 has to go, the program changes the arrow of node 2, not node 1, and node 1 still points to node 3. __length was decreased three times, but only two nodes really left.

Fix: when you delete, previous doesn’t move. It only moves on when the value is new.

Fragment 2: the position that isn’t validated

get_at without the check at the beginning:

def get_at(self, position):
    """Value at the given position (0 = the head). IndexError if it does not exist."""
    current = self.__first
    for _ in range(position):          # position hops from the head
        current = current.next_node
    return current.value

Output:

Queue: Laura → Pablo → Marta → Iván → Nora → None
get_at(-1) → Laura
Traceback (most recent call last):
  File "get_at_wrong.py", line 110, in <module>
    print("get_at(5) →", queue.get_at(5))
                         ~~~~~~~~~~~~^^^
  File "get_at_wrong.py", line 87, in get_at
    return current.value
           ^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

What happens: get_at(-1) returns Laura with no error: range(-1) doesn’t do a single lap and stays on the head. It’s the worst kind of bug, because it gives no warning. get_at(5) makes five hops, the last one into None, and then asks for None.value. The message ('NoneType' object has no attribute 'value') doesn’t say what’s wrong; an IndexError with the position does.

Fix: validate position < 0 or position >= self.__length before moving.

Fragment 3: the cycle that doesn’t exist

The detector from my mock exam, comparing values:

def has_cycle(self, show_steps=False):
    """Floyd's algorithm: True if some node points back to an earlier one. O(1) memory."""
    tortoise = self.__first
    hare = self.__first
    step = 0
    while hare is not None and hare.next_node is not None:
        tortoise = tortoise.next_node      # 1 hop
        hare = hare.next_node.next_node    # 2 hops
        step += 1
        if show_steps:
            print(f"  step {step}: tortoise on {tortoise.value}, hare on {hare.value}")
        if tortoise.value == hare.value:   # WRONG: compares names, not nodes
            return True
    return False                           # the hare reached None: there is an end

Last line of the output:

Six members, Marta twice, no cycle: True

What happens: in the queue Laura → Pablo → Marta → Iván → Marta → Nora, at step 2 the tortoise is on the first Marta (position 2) and the hare on the second (position 4). They’re different nodes with the same name, and == says they’re equal: a false positive.

Fix: tortoise is hare. It asks whether they are the same object, which is the only thing that proves the hare has gone round.

Commented solutions

Solution exercise 1

def get_at(self, position):
    """Value at the given position (0 = the head). IndexError if it does not exist."""
    if position < 0 or position >= self.__length:   # we validate BEFORE moving
        raise IndexError(f"position {position} out of range (length {self.__length})")
    current = self.__first
    for _ in range(position):          # position hops from the head
        current = current.next_node
    return current.value

def get_from_back(self, position):
    """Value counting from the back (0 = the last one), without the length and in one traversal."""
    if position < 0:
        raise IndexError(f"position {position} out of range")
    fast = self.__first
    for _ in range(position + 1):      # fast goes position + 1 nodes ahead
        if fast is None:               # the list is shorter than that
            raise IndexError(f"position {position} out of range")
        fast = fast.next_node
    slow = self.__first
    while fast is not None:            # they move together: the gap does not change
        fast = fast.next_node
        slow = slow.next_node
    return slow.value

get_at validates first and then makes position hops. Validating with the stored length is O(1), and that way there’s no need to check for None inside the loop. Check: get_at(2) hops twice, Laura → Pablo → Marta, and returns Marta.

get_from_back can’t use __length (that’s the challenge), so it uses two references position + 1 nodes apart. Trace of get_from_back(1) (the one before last):

When fast reaches None, slow is on Iván, the one before last. Why position + 1 and not position? Because we want fast to end at None, one position after the last one: if you only move it position nodes ahead, slow ends up one further on. The if fast is None inside the first loop detects that the list is shorter than the position asked for: that’s why get_from_back(5) gives IndexError without ever asking for None.next_node.

Solution exercise 2

def remove_duplicates(self):
    """Keeps only the first occurrence of each value, changing the list itself."""
    if self.__first is None:           # empty: nothing to do
        return
    seen = {self.__first.value}        # the head is never a duplicate: it is the first
    previous = self.__first
    current = self.__first.next_node
    while current is not None:
        if current.value in seen:
            previous.next_node = current.next_node   # we skip the duplicate
            self.__length -= 1
            # previous does NOT move on: we have not looked at its new next node yet
        else:
            seen.add(current.value)
            previous = current
        current = current.next_node

The decisions:

• The head goes into seen before the loop. It can never be a repeat (it’s the first occurrence), so the traversal starts at the second node with previous on the head. That way there’s no special case of “deleting the head”.
• If it deletes, previous stays still. Its new next node is one we haven’t looked at yet.
• current always moves on, at the end of the loop, in both cases.
• __length goes down with each deletion, so len keeps telling the truth.

Trace with four Martas (nodes 1 to 4):

Three deletions: 4 − 3 = 1, and len says so. Compare it with the table in fragment 1.

And without a set? For each node, traverse the following ones and delete the equal ones: O(1) memory but O(n²) time. With the set it’s O(n) time and O(n) memory. In the exam, if they don’t forbid auxiliary structures, the set is the way to go.

Solution exercise 3

def has_cycle(self, show_steps=False):
    """Floyd's algorithm: True if some node points back to an earlier one. O(1) memory."""
    tortoise = self.__first
    hare = self.__first
    step = 0
    while hare is not None and hare.next_node is not None:
        tortoise = tortoise.next_node     # 1 hop
        hare = hare.next_node.next_node   # 2 hops
        step += 1
        if show_steps:
            print(f"  step {step}: tortoise on {tortoise.value}, hare on {hare.value}")
        if tortoise is hare:              # the SAME node, not the same value
            return True
    return False                          # the hare reached None: there is an end

def create_cycle(self, position):
    """Only for testing: the last node is made to point to the node at that position."""
    target = self.__first
    for _ in range(position):
        target = target.next_node
    last = self.__first
    while last.next_node is not None:
        last = last.next_node
    last.next_node = target

The drawing with the example queue and the table of steps from the output:

The decisions:

• The condition hare is not None and hare.next_node is not None protects the hare’s two hops. If you only checked hare, in an even-length list hare.next_node.next_node would ask for None.next_node. Thanks to it, the empty list and the one-node list without a cycle return False without any extra if.
• First they move, then they’re compared. At the start both are on the head: if you compared before moving them, everything would have a cycle.
• is and not ==, because of fragment 3.
• A node pointing to itself is a cycle of length 1: the tortoise hops to itself, the hare too (twice), and tortoise is hare.

Why does the hare always catch the tortoise? When both are inside the cycle, on each lap the gap between them shrinks by exactly 1 (the hare takes two steps, the tortoise one). A gap that goes down one at a time ends at 0: it can’t skip it. In the example they meet at step 3, on Iván.

create_cycle only exists for testing: it finds the target node, reaches the last one and hooks it on. Careful: after calling it, don’t print the list: __str__ traverses with __iter__ and would never finish.

Exam-style quiz

Now test yourself as in the lab. The FP2 quizzes look like this: about 10 questions in 10-15 minutes, with single choice, multiple choice (wrong ticks subtract), true or false, fill in the gaps, matching and «what does this code print?». Here are 13 original questions on linked lists. Answer without running anything, press Check and read the explanation for each one. These questions are also the question bank for the FP2 theory mock exam, which will mix them with those from the other topics.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

c = Node(3)
b = Node(2, c)
a = Node(1, b)
a.next = c
n = a
text = ""
while n is not None:
    text += str(n.value)
    n = n.next
print(text)

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class Stack:
    def __init__(self):
        self.first = None
        self.size = 0

    def push(self, v):
        self.first = Node(v, self.first)
        self.size += 1

    def pop(self):
        v = self.first.value
        self.first = self.first.next
        self.size -= 1
        return v

s = Stack()
for x in [5, 8, 1]:
    s.push(x)
s.pop()
print(s.first.value, s.size)

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, *values):
        self.first = None
        for v in reversed(values):
            self.first = Node(v, self.first)

    def __iter__(self):
        n = self.first
        while n:
            yield n.value
            n = n.next

l = LinkedList(4, 7, 9)
print(sum(l), max(l), list(l)[1])

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def reverse(first):
    previous = None
    current = first
    while current:
        nxt = current.next
        current.next = previous
        previous = current
        current = nxt
    return previous

p = Node(1, Node(2, Node(3)))
q = reverse(p)
print(q.value, q.next.value, p.next)

Watch it step by step in Python Tutor

Floyd really clicks when you see the two references move. Go to Python Tutor, choose Python 3 and paste the class-free version of exercise 3:

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)

laura, pablo = Node("Laura"), Node("Pablo")
marta, ivan = Node("Marta"), Node("Iván")
laura.next_node = pablo
pablo.next_node = marta
marta.next_node = ivan
ivan.next_node = pablo        # the cycle: Iván goes back to Pablo

tortoise = laura
hare = laura
cycle = False
while hare is not None and hare.next_node is not None:
    tortoise = tortoise.next_node
    hare = hare.next_node.next_node
    if tortoise is hare:
        cycle = True
        break
print("Cycle?", cycle, "| they meet at", tortoise.value)

Output:

Cycle? True | they meet at Iván

What to watch step by step:

1. After the four next_node assignments, Iván’s arrow goes back to Pablo: Python Tutor draws the cycle.
2. On each lap, tortoise moves its arrow one node and hare two. Count the hops.
3. On the second lap the hare has already gone round the cycle and is behind the tortoise, on Pablo.
4. On the third, both arrows reach the same node, Iván: tortoise is hare is True.
5. Delete the line ivan.next_node = pablo and run it again: the hare reaches None and the result is False.

Cheat sheet: Python LinkedList

The essentials in 30 seconds: a node stores a value and a reference to the next one; the list only stores the head. To insert, link first and move afterwards. To delete, you need the previous node. Traverse with while current is not None; to stop at the last one, while current.next_node is not None. Validate before moving and always test the empty list and the one-node list.

Templates for the exercises:

Before you hand it in, ask yourself:

1. Does it work with the empty list and with a single node?
2. Is there any .value or .next_node on something that could be None?
3. Have I linked before moving in every change of references?
4. Is len still telling the truth after my method?

And with this you close the Python part of FP2. Next comes Java: start with Java syntax, where you’ll see that the references you’ve just mastered work the same way.

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