Practical 2 continued: Deleting a Node from a Linked List

Five things in that file are the marks.

The head case is separate, because there is no node in front of it to change.

before walks position - 1 steps, exactly as for insertion, and here is before.nxt.

if here is self.tail: self.tail = before is the line most answers are missing.

Deleting the only node sets both the head and the tail to None, which the head case does with if self.head is None.

here.nxt = None at the end unlinks the removed node completely. Not doing it leaves the removed node still pointing into the list, which is harmless here and is a real bug the moment anybody keeps a reference to the removed node.

All three cases run

from linked2 import SinglyLinkedList

items = SinglyLinkedList([10, 20, 30, 40, 50])
print("start                   ", items.as_chain(), f" len {len(items)}")

value, walked = items.delete_at_position(2)
print(f"delete position 2       ", items.as_chain(),
      f" removed {value}, walked {walked}")

value, walked = items.delete_at_position(0)
print(f"delete the HEAD         ", items.as_chain(),
      f" removed {value}, walked {walked}")

value, walked = items.delete_at_position(len(items) - 1)
print(f"delete the TAIL         ", items.as_chain(),
      f" removed {value}, walked {walked}")
print("  and the tail is now    ", items.tail, "with nxt", items.tail.nxt)

items.insert_at_end(99)
print("append after that delete", items.as_chain(),
      "  the append WORKED, so the tail was updated")

value, walked = items.delete_at_position(0)
value, walked = items.delete_at_position(0)
print("down to the last node   ", items.as_chain())
value, walked = items.delete_at_position(0)
print("delete the only node    ", items.as_chain(),
      f" removed {value}")
print("  head", items.head, " tail", items.tail, " len", len(items))

start                    10 -> 20 -> 30 -> 40 -> 50 -> None  len 5
delete position 2        10 -> 20 -> 40 -> 50 -> None  removed 30, walked 1
delete the HEAD          20 -> 40 -> 50 -> None  removed 10, walked 0
delete the TAIL          20 -> 40 -> None  removed 50, walked 1
  and the tail is now     Node(40) with nxt None
append after that delete 20 -> 40 -> 99 -> None   the append WORKED, so the tail was updated
down to the last node    99 -> None
delete the only node     None   (empty)  removed 99
  head None  tail None  len 0

Look at the line after the tail deletion. The append worked and 99 appeared at the end, which is the proof that the tail was moved back. The next section shows what happens when it is not.

The bug: forgetting to move the tail

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt

    def __repr__(self):
        return f"Node({self.data!r})"


class BrokenList:
    """Deletes correctly but never moves the tail back."""

    def __init__(self, items):
        self.head = None
        self.tail = None
        for item in items:
            node = Node(item)
            if self.head is None:
                self.head = node
            else:
                self.tail.nxt = node
            self.tail = node

    def chain(self):
        parts, here = [], self.head
        while here is not None:
            parts.append(str(here.data))
            here = here.nxt
        return " -> ".join(parts) + " -> None"

    def delete_last(self):
        before, here = None, self.head
        while here.nxt is not None:
            before, here = here, here.nxt
        before.nxt = None
        # the tail is NOT updated. That is the bug.

    def append(self, value):
        node = Node(value)
        self.tail.nxt = node
        self.tail = node


items = BrokenList([10, 20, 30])
print("start            ", items.chain(), " tail", items.tail)

items.delete_last()
print("after delete_last", items.chain(), " tail", items.tail,
      "  <- the tail is a node NOT in the list")

detached = items.tail
items.append(99)
print("after append(99) ", items.chain(),
      "  <- where did 99 go?")
print("  it was linked on to", detached, "which is not in the list,")
print("  so detached.nxt is", detached.nxt, "and nothing reaches it")

start             10 -> 20 -> 30 -> None  tail Node(30)
after delete_last 10 -> 20 -> None  tail Node(30)   <- the tail is a node NOT in the list
after append(99)  10 -> 20 -> None   <- where did 99 go?
  it was linked on to Node(30) which is not in the list,
  so detached.nxt is Node(99) and nothing reaches it

There is the whole bug. The chain still reads 10 -> 20 -> None and 99 is nowhere in it, because the append linked it on to the node that had already been removed. Nothing raised, nothing printed an error, and the data is simply lost.

A stale tail is the most dangerous bug in this exercise precisely because it is silent. One line fixes it: if here is self.tail: self.tail = before.

Deleting by value, and the trailing reference in its clearest form

from linked2 import SinglyLinkedList

items = SinglyLinkedList(["Physics", "Chemistry", "Maths", "Biology"])
print("start            ", items.as_chain())

print("delete 'Maths'   ", end=" ")
position = items.delete_value("Maths")
print(f"was at position {position}:", items.as_chain())

print("delete 'Physics' ", end=" ")
position = items.delete_value("Physics")
print(f"was at position {position}:", items.as_chain(),
      " head now", items.head)

print("delete 'Biology' ", end=" ")
position = items.delete_value("Biology")
print(f"was at position {position}:", items.as_chain(),
      " tail now", items.tail)

print("delete 'History' ", end=" ")
position = items.delete_value("History")
print(f"returned {position}, which means not found:", items.as_chain())

start             Physics -> Chemistry -> Maths -> Biology -> None
delete 'Maths'    was at position 2: Physics -> Chemistry -> Biology -> None
delete 'Physics'  was at position 0: Chemistry -> Biology -> None  head now Node('Chemistry')
delete 'Biology'  was at position 1: Chemistry -> None  tail now Node('Chemistry')
delete 'History'  returned -1, which means not found: Chemistry -> None

before is None is how this version recognises the head case, which is neater than a separate block: if nothing is behind here, then here is the head.

Why a singly linked list cannot delete a node it is holding

This is the question an examiner asks to separate a student who has understood the structure from one who has copied it.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt

    def __repr__(self):
        return f"Node({self.data!r})"


def chain(head):
    parts, here = [], head
    while here is not None:
        parts.append(str(here.data))
        here = here.nxt
    return " -> ".join(parts) + " -> None"


third = Node(30)
second = Node(20, third)
head = Node(10, second)

print("the list          ", chain(head))
print("I am holding      ", second)
print("can I reach the node before it? ",
      "no: a node has only a forward reference")
print("so to delete it I must walk from the head again:")

before, here = None, head
steps = 0
while here is not second:
    before, here = here, here.nxt
    steps += 1
before.nxt = here.nxt
print(f"  walked {steps} node(s) from the head, then one assignment")
print("the list          ", chain(head))

the list           10 -> 20 -> 30 -> None
I am holding       Node(20)
can I reach the node before it?  no: a node has only a forward reference
so to delete it I must walk from the head again:
  walked 1 node(s) from the head, then one assignment
the list           10 -> 30 -> None

So holding the node does not help: deletion still costs a walk from the head, which is O(n). That is the single strongest argument for a doubly linked list, in which each node also holds a reference backwards and a held node can be removed in constant time.

It is also why MU's practical 3 and 4 are a stack and a queue: both only ever remove from a position they already hold, which a singly linked list does perfectly well.

What happens to the deleted node

import gc
from linked2 import SinglyLinkedList


class Watched:
    def __init__(self, name):
        self.name = name

    def __del__(self):
        print(f"    the object {self.name} was freed")

    def __repr__(self):
        return self.name


items = SinglyLinkedList([Watched("a"), Watched("b"), Watched("c")])
print("list built:", items.as_chain())

print("  deleting position 1")
value, _ = items.delete_at_position(1)
print("  delete returned", value, "so a name still holds it")

print("  now dropping that name")
del value
gc.collect()

print("list now  :", items.as_chain())

list built: a -> b -> c -> None
  deleting position 1
  delete returned b so a name still holds it
  now dropping that name
    the object b was freed
list now  : a -> c -> None
    the object a was freed
    the object c was freed

Read the order carefully. The object was not freed when it was unlinked, because delete_at_position returned it and a name still held it. It was freed the moment that name went away. That is reference counting, and it is MU's Course Objective 9 in one demonstration. There is no free to call, and the memory goes back when the last reference does. [If Your College Runs Module 2 in C] shows the same deletion with free, where forgetting the call is a leak.

Reversing the list, which is the other question on this exercise

from linked2 import SinglyLinkedList

items = SinglyLinkedList([10, 20, 30, 40, 50])
print("before  ", items.as_chain(), " head", items.head, " tail", items.tail)
items.reverse()
print("after   ", items.as_chain(), " head", items.head, " tail", items.tail)

items.insert_at_end(5)
print("append 5", items.as_chain(), "  the tail was updated by reverse")

one = SinglyLinkedList([7])
one.reverse()
print("one node", one.as_chain())

empty = SinglyLinkedList()
empty.reverse()
print("empty   ", empty.as_chain())

before   10 -> 20 -> 30 -> 40 -> 50 -> None  head Node(10)  tail Node(50)
after    50 -> 40 -> 30 -> 20 -> 10 -> None  head Node(50)  tail Node(10)
append 5 50 -> 40 -> 30 -> 20 -> 10 -> 5 -> None   the tail was updated by reverse
one node 7 -> None
empty    None   (empty)

The reversal uses three references: before, here and after. The order of the four lines inside the loop is the whole answer:

after = here.nxt     # save it FIRST
here.nxt = before    # then turn the link round
before = here        # then advance both
here = after

Overwrite here.nxt before saving after and the rest of the list is unreachable. And note that reverse sets self.tail = self.head at the start, before the head moves, because the old head becomes the new tail.

Procedure

1. Save linked2.py with the list from the previous chapter plus delete_at_position,

delete_value and reverse.

1. In delete_at_position, handle the head as its own case, walk position - 1 nodes for the rest,

and move the tail back when the deleted node was the tail.

1. Set both the head and the tail to None when the only node is deleted.
2. Raise IndexError for an empty list and for a position out of range.
3. In a driver, delete from the middle, the head and the tail of a five node list, printing the chain

and the walk count each time.

1. Append immediately after deleting the tail and confirm the new node appears. That is the test

for the stale tail.

1. Write a deliberately broken version that does not move the tail, and record that the append is

silently lost.

1. Delete every node one at a time down to the empty list, and print the head, the tail and the

length at the end.

1. Write delete_value using before is None to recognise the head.
2. Reverse the list with three references and confirm the tail was updated by appending afterwards.

Result

Deleting from position 2 walked past one node; deleting the head walked past none; deleting the tail walked to the node before it and moved the tail back, which an append immediately afterwards confirmed by appearing at the end. Deleting the last remaining node set both the head and the tail to None. The deliberately broken version lost the appended value silently: the chain still read 10 -> 20 -> None after appending 99, because the append had been linked on to the detached node. delete_value removed a middle, a head and a tail value and returned -1 for a value not present. Deleting a node did not free it while the returned value was still named; it was freed when that name was deleted. Reversing a five node list, a one node list and an empty list all behaved correctly and the tail was updated.

Where marks are lost

• No trailing reference. A singly linked node cannot reach the one before it, so the walk must

carry before.

• Not moving the tail when the deleted node was the tail. This is the silent one.
• Not setting both head and tail to None when the only node goes.
• Treating the head like any other node, which crashes because there is nothing in front of it.
• Walking position nodes instead of position - 1.
• No bounds check, and no error for an empty list.
• Not returning the removed value.
• Overwriting here.nxt before saving after in reverse, which loses the rest of the list.
• Forgetting that reverse must also swap the head and the tail.

For the journal

The aim in MU's words. The two pictures, before and after, with the removed node shown detached and nothing pointing at it. The three case table with the tail line highlighted. The class in full and the driver, with the chain and the walk count printed after every deletion, and then the append immediately after the tail deletion, because that line is the evidence that the tail was updated. Then the broken version and its silently lost append, with one sentence: a stale tail is dangerous because nothing raises. Then the deletion down to empty, with the head, tail and length printed. One sentence on why holding a node does not help: deletion changes the previous node's link and there is no way back, which is why a doubly linked list exists. The conclusion: deletion needs the node in front of the one being removed, so it has three cases and a trailing reference.

Quick revision

• Deletion changes the nxt of the node in front, so the walk carries a trailing reference

before.

• Three cases: the head (self.head = here.nxt), the middle (before.nxt = here.nxt), the tail

(also self.tail = before).

• A fourth: the only node, which sets head and tail to None.
• before walks position - 1 steps; here is before.nxt.
• A stale tail is silent. The next append links onto a detached node and the value disappears.
• here.nxt = None after unlinking, so the removed node does not still point into the list.
• delete_value: before is None means here is the head.
• Deletion is O(n) even when you are holding the node, because the walk is needed to find the one

in front. A doubly linked list fixes that.

• Python frees the node when the last reference goes, not when it is unlinked.
• reverse: three references, and save after before overwriting here.nxt. Set the tail to

the old head first.

Questions you should be able to answer

1. Why does deletion need a trailing reference? Because removing a node means changing the nxt of the node in front of it, and a singly linked node has no reference backwards.

2. What are the three cases of deletion? The head, where there is no node in front; the middle, where before.nxt = here.nxt; and the tail, where the tail must also be moved back to before.

3. What is the fourth case? Deleting the only node, which must set both the head and the tail to None.

4. What goes wrong if you do not move the tail? The tail still points at a node that has been removed, so the next append links the new node on to that detached node and the value never appears in the list. Nothing raises, which is why it is dangerous.

5. How do you test for that bug in one line? Delete the tail and then append. If the appended value appears, the tail was updated.

6. To delete position 5, how many nodes do you walk and which one do you stop at? Four, stopping at position 4, the node before the one to be removed.

7. Why does holding the node not make deletion cheaper? Because the deletion changes the previous node's link, and there is no way from a node to its predecessor, so the walk from the head is still needed. That is O(n).

8. Which structure fixes that, and how? A doubly linked list: each node also holds a reference to the previous node, so a held node can be unlinked in constant time.

9. When is the removed node's memory released in Python? When the last reference to it goes away. Unlinking is not enough if the delete method returned it and a name still holds it.

10. Write the four lines that reverse a list. after = here.nxt, here.nxt = before, before = here, here = after. Saving after must come first, and when the loop ends before is the new head.