Sentinel nodes for doubly lists

Why it matters

A doubly linked list stores two pointers in each node. One points to the next node and the other points to the previous node. Most bugs in this kind of list happen at the two ends, the front and the back. Inserting at the front means setting the first node's prev. Removing the last node means moving the tail back. Each end case needs its own if, and a missing line in one of those blocks causes a crash that shows up later, far from the line that caused it.

A sentinel removes most of those if statements. A sentinel is a dummy node. It holds no real data, and it is always present. Because it sits at both ends, every real node always has a node before it and a node after it. This lesson builds that list in C++, traces it by hand and runs it. Lesson 05 of this module introduced the sentinel idea. This lesson builds the full structure and shows which checks it removes and which it keeps.

The problem at the ends

Start with a doubly linked list that has no sentinel. Each node has a value, a prev pointer and a next pointer. The list keeps two pointers of its own: head for the first node and tail for the last node. A pointer that points at nothing holds nullptr, which is C++'s word for "no node here".

Here is the code that removes a node n you already hold. This is the version the sentinel replaces.

void unlink(Node*& head, Node*& tail, Node* n) {
    if (n->prev != nullptr) n->prev->next = n->next; else head = n->next;
    if (n->next != nullptr) n->next->prev = n->prev; else tail = n->prev;
    delete n;
}

The & in Node*& means the function receives the real head and tail variables, so it can change them. Without the &, the function would change its own copies, and the caller's head would still point at the deleted node.

Read the first line slowly. If n has a node before it, that node must skip over n and point to n->next. If n has no node before it, then n is the first node, and head must move forward to n->next. The second line does the same job for tail. So there are four cases: a node in the middle, the first node, the last node, and the only node. Each case has to be right.

Every operation that touches an end needs the same pair of checks. A list with five operations has about ten if blocks that must stay consistent with each other. A sentinel brings the number of end checks in insert and delete down to zero.

The idea: a ring with a dummy node

Picture the list as a ring. Add one extra box to the ring and call it the sentinel. The sentinel's next points to the first real node, and its prev points to the last real node. Follow next from the sentinel and you visit the real nodes in order. When you arrive back at the sentinel, the walk is over.

For a list with the values 5, 6 and 7, the two directions look like this.

sentinel.next -> 5 -> 6 -> 7 -> sentinel
sentinel.prev -> 7 -> 6 -> 5 -> sentinel

Each real node has both neighbours. The first real node's prev is the sentinel, and the last real node's next is the sentinel. No real node holds nullptr inside the ring, so the code never needs to ask whether a neighbour exists.

An empty list is a ring with only the sentinel in it. The sentinel's next and prev both point to the sentinel itself, so the ring is one box that points at itself. The constructor sets up exactly that state.

The sentinel's value is never read. It is set to 0 only because every Node needs a value when it is built.

Building the list in C++

The class below keeps the sentinel as a member object. The sentinel is not allocated with new. It lives inside the list object, so its address never changes while the list exists. The destructor frees the real nodes, and the sentinel goes away with the list itself.

Here is the complete program. Run it first, then read the parts below.

The output is:

-- dry run --
forward:  [5]
forward:  [5 6]
forward:  [4 5 6]
forward:  [4 5]
-- removeFirst(5) --
removed: 1
forward:  [4]
removed 99: 0
-- insertSorted --
forward:  [2 5 7 9]
forward:  [1 2 5 7 9]
forward:  [1 2 5 7 9 20]
backward: [20 9 7 5 2 1]

The constructor closes the ring

sentinel_.next = &sentinel_; reads as "the sentinel's next is the sentinel". The & takes the address of the sentinel. Both pointers point at the sentinel, so an empty list is a ring of one box.

insertAfter: one function for every position

insertAfter(where, v) puts a new node right after the node where. It changes four pointers, and the order of the lines matters.

1. The new node's prev is set to where, and its next is set to the node that currently follows where. The new node's pointers only point at existing nodes, so nothing is lost yet.
2. The node that currently follows where gets its prev set to the new node.
3. where->next is set to the new node. This line must come last. If it ran first, the old next node would be lost, and step 2 could not find it.

pushFront is insertAfter(&sentinel_, v). pushBack is insertAfter(sentinel_.prev, v). The code is the same in both, and only where changes. When the list is empty, where is the sentinel, and step 2 sets the sentinel's prev. That is the correct result, so the empty case needs no separate branch.

erase: one function for every real node

erase(n) skips over n on both sides and then deletes it. The first real node has the sentinel as its prev, and the sentinel accepts the update like any other node. The last real node has the sentinel as its next, which works the same way. So erase needs no check for the ends.

erase is private and must never be called with the sentinel. The public functions popFront and popBack make sure of that, as the next section explains.

Walks stop at the sentinel

In a list without a sentinel, a walk stops at nullptr. In this list, the walk must stop when it reaches the sentinel:

for (Node* p = sentinel_.next; p != &sentinel_; p = p->next)

The loop starts at the first real node. It stops when p returns to the sentinel. The sentinel is never nullptr, so a check against nullptr would never end the loop. The mistakes section shows what happens.

What the sentinel changes

The table compares the checks needed in a plain doubly linked list with the checks needed when the list has a sentinel.

The last row is the one check that stays. The sentinel is never a real node, so the function must refuse to erase it.

A dry run, step by step

A dry run means you follow the code by hand, one line at a time, and write down what each pointer holds after each line. Use this method whenever a list bug is hard to see. It is slower than running the program, but you see every change.

Start with an empty list. Call the sentinel S, and call the new nodes N5, N6 and N4. The four operations are pushBack(5), pushBack(6), pushFront(4) and popBack().

Step 1 shows the empty case. where is S.prev, and S.prev is S. The line where->next->prev = n sets S.prev to N5, because where->next is S at that moment. The last line sets S.next to N5. Both ends now point at the only node, and that node points at the sentinel on both sides.

Step 2 shows the usual case. where is N5, the last real node. The new node is placed after it. The node after N5 was S, so the line where->next->prev = n sets S.prev to N6. Now the backward walk starts at N6.

Step 3 uses the front. where is S, so the new node goes after the sentinel. The node after S was N5, so N5.prev changes to N4. The forward walk now starts at N4.

Step 4 removes the last node. erase reads n->prev and n->next before it deletes n. Both neighbours are updated, so no pointer still refers to N6 when it is freed.

After step 3, the backward walk starts at S.prev, which is N6, and goes N6, N5, N4 and then the sentinel. A backward walk at that point prints 6 5 4. After step 4, the list has two nodes, and both directions agree with the table.

Removing a value and inserting in order

The sentinel helps most when a walk and an insert happen at the same time. The next two functions show that.

removeFirst(v) walks from the first real node until it reaches the sentinel. When it finds the first node with the value, it calls erase on that node. The loop never checks for nullptr, and the front of the list needs no special case, because the first real node is just the node after the sentinel.

insertSorted(v) keeps the list in increasing order. It starts at the sentinel and moves forward while the next node has a smaller value. Then it inserts right after the last node it passed.

Take the list 2, 5, 9 and call insertSorted(7). The walk starts at the sentinel. The next node is 2, which is less than 7, so the walk moves to 2. The next node is 5, which is less than 7, so the walk moves to 5. The next node is 9, which is not less than 7, so the walk stops. insertAfter(5, 7) runs, and the list becomes 2, 5, 7, 9.

Now call insertSorted(1) on the same list. The walk starts at the sentinel. The next node is 2, which is not less than 1, so the walk does not move. insertAfter(S, 1) runs, which places 1 at the front. The front case needs no if in insertSorted. The sentinel is a real starting point for the walk, so the same loop handles the front, the middle and the end.

Why popFront still checks for empty

The sentinel removes the null checks. It does not remove the empty check. Look at popFront:

bool popFront() {
    if (empty()) return false;
    erase(sentinel_.next);
    return true;
}

Without the if, an empty list would call erase on sentinel_.next. On an empty list that pointer is the sentinel itself. erase would then unlink the sentinel and call delete on it. The sentinel is not a heap node, so a memory checker called a sanitizer stops the program. The mistakes section shows the message.

The check is needed because erase must never receive the sentinel. In a plain list, the same bad call would fail on nullptr instead. Both need one guard in the public function. The sentinel changes where the guard is written, but it does not remove the need for it.

Copying the list

The class deletes its copy constructor and its copy assignment operator. This is deliberate. The sentinel's address is stored inside the list's own nodes. A copy would copy the next and prev pointers of the original sentinel, so the copy's ring would point into the original's nodes and never come back to the copy's own sentinel.

The two lists would then share nodes. Their destructors could free the same node twice. Declaring a copy constructor also stops the compiler from creating a move constructor, so the list cannot be moved either. The rule of three (if a class needs a custom destructor, copy constructor or copy assignment, it usually needs all three) is covered in the object-oriented module.

If you need a copy, write the copy operations yourself. The copy must make a new sentinel, then copy each real value into a new node. Lesson 05 covers std::list, which already does this.

Common mistakes and the messages you will see

Mistakes 1 to 3 compile and run without a complaint, and the program then fails in a different place. The messages below come from the same code, built with g++ -std=c++20 -Wall -Wextra -g -fsanitize=address,undefined. Process IDs and memory addresses in the messages will differ on your machine.

Mistake 1: a walk that stops at nullptr

If the forward walk checks p != nullptr, the loop never ends. The sentinel is not nullptr, so after the last real node the loop moves to the sentinel, then to the first real node again. With one value in the list, the loop prints without end, and the program only stops when something kills it. This run, on the list that holds only 5, was stopped by timeout 2:

forward:  [50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 ...

The 50 is the value 5 followed by the sentinel's value 0, because the loop prints the sentinel as if it were a real node. The program exited with status 124, which is the code timeout uses when it stops a command. In two seconds it printed tens of megabytes of text, and the exact amount depends on the machine. Always stop a sentinel walk at &sentinel_.

Mistake 2: popping an empty list

If you delete the if (empty()) line from popFront, then push one value, pop it, and pop again, the second pop erases the sentinel:

==171961==ERROR: AddressSanitizer: attempting free on address which was not malloc()-ed
    #1 in DList::erase(Node*)
    #2 in DList::popFront()
    #3 in main

The message says delete was given an address that was not returned by new. The address is the sentinel, which is a member of the list object, not a heap node. Keep the check in every public pop function.

Mistake 3: setting where->next before reading it

Changing the order inside insertAfter breaks the list. If where->next = n; runs before where->next->prev = n;, then where->next is already n when the second line runs. That line sets n->prev to n, so the new node points at itself, and the old next node is no longer reached from where. The fix is to keep the order from the section above: set the new node's pointers first, then the next node's prev, then where->next last.

Mistake 4: copying the list

Trying to copy a list gives this error from the compiler (the line numbers depend on your file):

error: use of deleted function 'DList::DList(const DList&)'
   95 |     DList b = a;
note: declared here
   16 |     DList(const DList&) = delete;

The message is correct. The copy constructor is deleted on purpose, as the copying section explains. Pass the list by reference, or write the copy operations.

Mistake 5: the same pointer logic as a plain list

The plain list from the start of this lesson needs both head and tail updated. A common error is to update only one of them. This version forgets the else head = n->next; part:

void unlinkBuggy(Node*& head, Node*& tail, Node* n) {
    if (n->prev != nullptr) n->prev->next = n->next;
    if (n->next != nullptr) n->next->prev = n->prev; else tail = n->prev;
    delete n;
}

The compiler warns with unused parameter 'head'. That warning points at head in the first line of the function, a hint that the function never uses it. When this function runs on the first node, head still points at the deleted node. Reading head->value then gives this error:

ERROR: AddressSanitizer: heap-use-after-free
READ of size 4
freed by thread T0 here:
    #1 in unlinkBuggy(Node*&, Node*&, Node*)

The sentinel version has no head to forget, which is one of its benefits.

Practice

Exercise 1: dry run

Start with an empty list. Call these in order: pushFront(3), pushBack(8), pushFront(1), popFront(), pushBack(9). Write the forward order of the list after each call.

Show the answer

After the calls, the forward order is: 3, then 3 8, then 1 3 8, then 3 8 (the popFront removes 1), then 3 8 9.

Exercise 2: sum the values

Write a member function int sum() const that returns the sum of every value in the list. Use the walk that stops at the sentinel.

Show the answer

int sum() const {
    int total = 0;
    for (const Node* p = sentinel_.next; p != &sentinel_; p = p->next) {
        total += p->value;
    }
    return total;
}

For the list 2, 5, 9 the function returns 16. For an empty list it returns 0, because the loop body never runs.

Exercise 3: the walk with nullptr

The printBackward function walks with prev. Suppose its loop condition were p != nullptr instead of p != &sentinel_. Describe what the program does on the list 2, 5, 9.

Show the answer

The walk starts at the last real node, 9, and moves to 5, then to 2. The next pointer is the sentinel, which is not nullptr, so the loop keeps going. It prints the sentinel's value 0 and then moves to 9 again. The output repeats 9, 5, 2, 0 until the program is stopped.

Exercise 4: remove by index

Write bool removeAt(int index) that removes the node at a position. Position 0 is the first real node. The function returns false if the index is negative or too large, and true after a removal.

Show the answer

bool removeAt(int index) {
    if (index < 0) return false;
    Node* p = sentinel_.next;
    for (int i = 0; i < index && p != &sentinel_; ++i) {
        p = p->next;
    }
    if (p == &sentinel_) return false;
    erase(p);
    return true;
}

On the list 2, 5, 9, removeAt(1) returns true and leaves 2, 9. removeAt(5) returns false. The loop stops at the sentinel, and the check after the loop catches the case where the list is shorter than the index.

Exercise 5: why erase needs no end checks

The plain unlink function has four cases. Explain why erase in this class needs none of them.

Show the answer

Every real node has a prev and a next pointer. At the front, prev is the sentinel, and at the back, next is the sentinel. Both are nodes in the ring, so erase can always write to n->prev->next and n->next->prev. Head and tail do not exist as separate variables, because the first and last nodes are found from the sentinel. There is nothing to move, so the cases disappear.

Summary

• A sentinel is a dummy node that holds no data and sits in the ring between the last and first real nodes.
• An empty list is a sentinel that points at itself on both sides.
• insertAfter and erase run the same code at the front, the middle and the back, because every real node has neighbours.
• Walks must stop at &sentinel_, never at nullptr.
• The sentinel removes the null checks in insert and delete, but a pop on an empty list still needs a check, and the class must not be copied.