Sentinel nodes for doubly lists in Python

Why this matters

A doubly linked list is a chain of boxes. Each box, called a node, holds one value, a link to the box before it, and a link to the box after it. Removing a box in the middle takes two steps. Removing the first box, the last box, or the only box takes extra steps, because the code must check whether the neighbour on one side exists.

Those checks are where most pointer bugs in list code come from. A sentinel removes them. A sentinel is an extra node that holds no real value and never leaves the list. This lesson builds one, runs it, and shows what goes wrong without it. The basics of doubly linked lists are in the earlier lesson "Doubly and circular lists" in this module, so this lesson does not repeat them.

A list without a sentinel

Start with the plain version so you can see the problem. The list keeps two variables, head for the first node and tail for the last node. Each node has a prev link and a next link. A link that is None means there is no neighbour. None is Python's word for "points at nothing".

A class is a blueprint for objects. Calling Node(5) builds one object from the blueprint. The __init__ method runs during that call, and self is the object being built. Python does not list the fields at the top of a class. The attributes appear when __init__ sets them.

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

To remove a node from this list, you must handle four cases. The node can be the head, the tail, both (the only node), or neither. Here is the code that handles all four.

class PlainList:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def remove(self, node):
        if node.prev is None:
            self.head = node.next
        else:
            node.prev.next = node.next
        if node.next is None:
            self.tail = node.prev
        else:
            node.next.prev = node.prev

This code is correct. The problem is the two if lines. Each one is a place where a programmer can forget a case. Here is a shorter version that skips the checks. It is the kind of code that looks fine at first.

def remove_careless(node):
    node.prev.next = node.next
    node.next.prev = node.prev

Call it on the first node of a list and Python stops the program. The last line of the error from one run was this.

AttributeError: 'NoneType' object has no attribute 'next' and no __dict__ for setting new attributes

An AttributeError is the error Python raises when code asks an object for a name it does not have, or tries to set one it cannot store. Here, node.prev is None because the first node has no previous node. The line node.prev.next = ... then tries to set an attribute on None. The end of the message says that None has no place to store a new attribute.

The idea: a node that is never removed

A sentinel is a node that holds no real data and stays in the list for as long as the list exists. The name comes from a guard who stands at a gate and is never sent away. In a list, the sentinel is a stand-in for "the place before the first item and after the last item".

Two changes make the sentinel work.

1. The list is circular. The last real node points forward to the sentinel, and the sentinel points back to the last real node. Nothing in the list points to None.
2. The empty list is a sentinel that points to itself in both directions.

Here are the shapes, with S for the sentinel. The arrows in the diagrams are written as text, so each one reads the same way as the code.

empty list:
  S.next = S      S.prev = S
 
list with A and B:
  S <-> A <-> B <-> back to S

Because every real node always has a previous node and a next node, the code that inserts and removes never checks for None. When a real node is the first one, its prev is the sentinel. When it is the last one, its next is the sentinel. The sentinel is always there to be the neighbour.

Building the class step by step

The full class is below. It is the version used in every example in this lesson. The sentinel is created once, in __init__. Python has no final keyword for attributes, so the rule is a convention: set self.sentinel once and never assign it again. Python does not stop code that breaks the rule.

The class uses is to ask whether two names point at the same node, and == to compare values. is checks object identity. == checks equal values.

The nodes method uses yield, which makes it a generator. Each time a loop asks for the next item, the method runs until the next yield, hands back one node, and pauses there. find and __str__ both walk the ring through nodes, so the stop condition lives in one place. Python calls __str__ when you print an object or put it in an f-string.

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None
 
 
class CircularList:
    def __init__(self):
        self.sentinel = Node(0)
        self.sentinel.prev = self.sentinel
        self.sentinel.next = self.sentinel
        self.size = 0
 
    def insert_after(self, place, value):
        created = Node(value)
        created.prev = place
        created.next = place.next
        place.next.prev = created
        place.next = created
        self.size += 1
 
    def add_first(self, value):
        self.insert_after(self.sentinel, value)
 
    def add_last(self, value):
        self.insert_after(self.sentinel.prev, value)
 
    def remove(self, node):
        if node is self.sentinel:
            raise ValueError("the sentinel cannot be removed")
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
 
    def nodes(self):
        cur = self.sentinel.next
        while cur is not self.sentinel:
            yield cur
            cur = cur.next
 
    def find(self, value):
        for node in self.nodes():
            if node.value == value:
                return node
        return None
 
    def remove_first(self):
        if self.size == 0:
            raise IndexError("list is empty")
        first = self.sentinel.next
        value = first.value
        self.remove(first)
        return value
 
    def __str__(self):
        items = [str(node.value) for node in self.nodes()]
        return "[" + " <-> ".join(items) + "]"

Read insert_after slowly, because it is the heart of the lesson. It takes a place node and puts a new node right after it. There are four pointer changes, and the order matters.

1. created.prev = place and created.next = place.next set the new node's two links first. Now the new node knows both neighbours.
2. place.next.prev = created makes the old next node point back at the new node.
3. place.next = created makes the place point forward at the new node.

If you swap steps 2 and 3, you lose a link. Think of it as changing a train's carriages. You must connect the new carriage to the carriage ahead before you unhook the old connection. Otherwise the carriages ahead are lost.

Now add_first and add_last are one line each. add_first inserts right after the sentinel, which puts the new node at the front. add_last inserts right after self.sentinel.prev, which is the current last real node, or the sentinel itself when the list is empty. Both methods are the same code with a different place.

remove also has no branches. A removed node's neighbours point at each other, and the node itself is left unlinked. The list shrinks by one, and the code never checks which side the node was on. The remove method raises ValueError only for the sentinel, because the sentinel is a bad value to pass in. ValueError is Python's error for an argument with a wrong value.

Worked example 1: insert and remove, shown step by step

The next program does the same work as the class above but prints the links after each step. It uses a Node with a name attribute, so the output shows names such as A and B instead of numbers.

The show function uses while True with a break at the end. Python has no do-while loop, so this is the usual way to write a loop that must run its body once before it checks for the stop point.

The show function walks the ring from the sentinel and prints each node with its links. Its output from one run was this.

start: S(prev=S,next=S)
insert A: S(prev=A,next=A) A(prev=S,next=S)
insert B: S(prev=B,next=A) A(prev=S,next=B) B(prev=A,next=S)
remove A: S(prev=B,next=B) B(prev=S,next=S)

Walk through the second line. After insert A, the sentinel's next and prev both point at A, because A is the only real node. A's prev and next both point at the sentinel. The ring has two members and each one points at the other.

Walk through the last line. Removing A changes two links. B's prev becomes the sentinel, and the sentinel's next becomes B. The sentinel now points at B in both directions, and B points back at the sentinel in both directions. There was no branch for "A is the only node", because the two lines for removal work in that case too.

Worked example 2: find, then remove

Finding a value and removing it is the most common pair of operations. The find method walks from the first real node until it reaches the sentinel again. It returns the node or None when the value is missing.

The program below uses the CircularList class from the section above. Put it in the same file, after the class. The variable is named ring instead of list, because list is the name of a built in Python type, and a variable with that name would hide it.

ring = CircularList()
ring.add_last(10)
ring.add_last(20)
ring.add_last(30)
ring.add_first(5)
print(f"after adds: {ring} size={ring.size}")
 
twenty = ring.find(20)
ring.remove(twenty)
print(f"after removing 20: {ring} size={ring.size}")
 
print(f"find 99: {ring.find(99)}")
 
try:
    ring.remove(ring.sentinel)
except ValueError as error:
    print(f"error: {error}")
 
one = CircularList()
one.add_last(7)
only = one.find(7)
one.remove(only)
print(f"one removed: {one} size={one.size} sentinel self-loop={one.sentinel.next is one.sentinel}")

The output from one run was this.

after adds: [5 <-> 10 <-> 20 <-> 30] size=4
after removing 20: [5 <-> 10 <-> 30] size=3
find 99: None
error: the sentinel cannot be removed
one removed: [] size=0 sentinel self-loop=True

The find 99 line prints None because no node holds 99. The remove(ring.sentinel) call fails with a clear message, because the sentinel is not a real item. The try block runs the call. When it raises a ValueError, the except block runs and the program keeps going. The guard at the top of remove is the only check in the whole class that looks for a special node. Everything else relies on the ring shape.

The last part shows the one-node case. The node holding 7 has prev and next both set to the sentinel. Removing it runs sentinel.next = sentinel and sentinel.prev = sentinel, and those two assignments give the empty-list shape again. No special code is needed.

Worked example 3: moving a node to the front

The third example is harder because it combines two operations. Moving a value to the front means removing it from where it is and inserting it at the start. With a sentinel, this takes one remove call and one insert_after call, with no branches for the ends of the list.

It is a function that takes the list as its first argument, so the class above stays unchanged.

def move_to_front(ring, node):
    ring.remove(node)
    ring.insert_after(ring.sentinel, node.value)

This function creates a new node with the same value. The old node is discarded. If another variable still holds the old node, it now points at a node that is no longer in the list. A version that relinks the same node avoids this, and it is a good exercise after this lesson.

The program below calls move_to_front three times and then once more with a value that is already first. It needs the class and the function above in the same file.

ring = CircularList()
ring.add_last(1)
ring.add_last(2)
ring.add_last(3)
ring.add_last(4)
print(f"start {ring} size={ring.size}")
move_to_front(ring, ring.find(3))
print(f"move 3 to front {ring} size={ring.size}")
move_to_front(ring, ring.find(4))
print(f"move 4 to front {ring} size={ring.size}")
move_to_front(ring, ring.find(4))
print(f"move 4 again {ring} size={ring.size}")

Its output from one run was this.

start [1 <-> 2 <-> 3 <-> 4] size=4
move 3 to front [3 <-> 1 <-> 2 <-> 4] size=4
move 4 to front [4 <-> 3 <-> 1 <-> 2] size=4
move 4 again [4 <-> 3 <-> 1 <-> 2] size=4

The size stays at 4 each time, because the code removes one node and adds one node. The last line shows that moving a node that is already first leaves the order the same.

Checking a sentinel list by hand

Before you trust a method that changes links, check the ring by walking it. Start at the sentinel and follow next until you return to it. Count the nodes you pass, and compare the count with size. Then walk the same ring backwards with prev. You should reach the same nodes in reverse order, and the walk should end at the sentinel again.

Each real node should also satisfy one rule: node.prev.next is node and node.next.prev is node. If that rule fails for any node, a link was changed in only one direction, and the list will break the next time someone walks it backwards. The debugging lab in lesson 16 of this module covers how to find these mistakes in longer code.

A sentinel does not protect the list from every mistake. It does not stop code from keeping a reference to a node that was removed, and it does not keep size correct. Those two checks are the caller's job.

Common mistakes

Looping with is not None on a circular list. A loop that walks a sentinel list must stop when it reaches the sentinel, not when it reaches None. The pattern while cur is not self.sentinel: is correct, as the nodes method shows. The pattern below is wrong here, because no node in the ring has a next of None. That loop never ends, and the program keeps going around the ring until something stops it. This version is not run here, because it does not finish.

cur = ring.sentinel.next
while cur is not None:
    print(cur.value)
    cur = cur.next

Removing the sentinel. The sentinel holds no value, so removing it would break the ring. The guard in remove prevents this. The message from one run was error: the sentinel cannot be removed.

Setting the new node's links in the wrong order. If place.next = created runs before created.next = place.next, then created.next copies the new node itself, not the old next node. The list loses everything after place. The correct order is the one in insert_after above: set the new node's two links first, then fix the neighbours.

This test builds a ring with 1 and 3, then inserts 2 after node 1 with the wrong order. It walks the first four nodes and checks whether the walk reached the sentinel again.

def insert_after_wrong_order(place, value):
    created = Node(value)
    created.prev = place
    place.next = created
    created.next = place.next
    place.next.prev = created
 
 
ring = CircularList()
ring.add_last(1)
ring.add_last(3)
insert_after_wrong_order(ring.find(1), 2)
cur = ring.sentinel.next
values = []
for _ in range(4):
    values.append(cur.value)
    cur = cur.next
print("first four nodes:", values)
print("sentinel reached again:", cur is ring.sentinel)

The output from one run was this.

first four nodes: [1, 2, 2, 2]
sentinel reached again: False

The walk never returns to the sentinel. The node holding 2 points at itself, and the node holding 3 is no longer reachable from the sentinel.

Writing self in the wrong place. Inside a method, a plain name such as sentinel is a local variable. It disappears when the method ends. To keep the sentinel on the object, write self.sentinel. The class below forgets the self. in __init__, and then another method uses it.

class Broken:
    def __init__(self):
        sentinel = Node(0)
        sentinel.prev = sentinel
        sentinel.next = sentinel
 
    def first(self):
        return self.sentinel.next
 
 
Broken().first()

The error from one run was this.

AttributeError: 'Broken' object has no attribute 'sentinel'

Forgetting size. The size attribute is not used by the links, so the list still works when it is wrong. But size then disagrees with the number of real nodes, and any code that trusts it will fail later. Both insert_after and remove change size, so keep the two changes together when you edit either method.

Mixing sentinel and head. Some code keeps both a sentinel and a head variable. Only one should be the source of truth. This class uses self.sentinel.next as the first real node and never stores a separate head.

Practice

Exercise 1. Start with an empty CircularList. Call add_last(5). What are ring.sentinel.prev and ring.sentinel.next after that call?

Show the answer

Both point at the single node holding 5. Inserting into an empty list runs insert_after(self.sentinel, 5). The new node's prev and next both end up at the sentinel, and the sentinel's prev and next both end up at the new node. A test run printed 5 5 True for ring.sentinel.next.value, ring.sentinel.prev.value and ring.sentinel.next is ring.sentinel.prev.

Exercise 2. Starting from an empty list, call add_first(1), then add_first(2), then add_last(3). What does print show for the list?

Show the answer

It prints [2 <-> 1 <-> 3]. The first call makes [1]. The second puts 2 in front, giving [2, 1]. The third puts 3 at the end, giving [2, 1, 3]. The program run for this exercise printed ex2: [2 <-> 1 <-> 3].

Exercise 3. Why does remove have no if for the case where the removed node is the only real node?

Show the answer

In that case node.prev and node.next are both the sentinel. The two lines node.prev.next = node.next and node.next.prev = node.prev then set the sentinel's next and prev to the sentinel. That is the shape of an empty list, so the same two lines handle the case with no special branch.

Exercise 4. Write a method remove_first(self) for the CircularList class. The class above already has one, so write yours in a copy with that method deleted. It removes the first real node and returns its value. It raises IndexError with the message list is empty when the list has no real nodes. Use the size attribute to check for empty.

Show the answer

The code is the remove_first method in the class above. It checks self.size == 0 first, then saves self.sentinel.next, reads its value, removes it, and returns the value. A test run with the list [4, 5] printed ex4: 4 then [5]. A second call on the one-node list returned 5 and left []. A third call raised IndexError, and the message printed was ex4 error: list is empty. Python raises IndexError when you take an item from an empty list with pop(), so the same error type fits here.

Exercise 5. The list is [1, 2, 3]. Find the node holding 2 and remove it. What is printed, and what is size?

Show the answer

It prints [1 <-> 3] and size=2. The find(2) call returns the middle node. The remove call links node 1 directly to node 3 and reduces size by one.

Summary

• A sentinel is an extra node that holds no value and stays in a list for as long as the list exists.
• A circular doubly linked list with a sentinel never has a None link, so insert and remove need no end-of-list checks.
• An empty list is a sentinel that points to itself in both directions.
• In insert_after, set the new node's two links first, then change the two neighbours.
• Walk the list from sentinel.next and stop when the walk reaches the sentinel again, not when it reaches None.
• Removing the only real node needs no special case, because the two link changes leave the sentinel pointing at itself.