Modification - Sentinel Nodes

Consider the push_front()/pop_front() example we did early. Both functions required us to check for a special case and essentially write 2 different versions of the same function for those special cases (inserting into an empty list, removing from a list with only one node). One modification we can make to our linked list in order to simplify the functions is to add the idea of sentinel nodes

Sentinel nodes are nodes that exist at the front and back of a linked list. These nodes always exist from the time the linked list is created to the time it is destroyed. They do not hold any data. The purpose for their existence is to eliminate most of the special cases when writing functions.

Most of the special case checks in our implementation involves having to modify the front_/back_ pointers or next_/prev_ pointers that were nullptr. Sentinel nodes prevent these situations from happening. In the next section we will look at what it means to have sentinel nodes.

Linked List Constructor - With Sentinels

The constructor of the linked list should set up an empty linked list. With sentinels, this effectively means we create two nodes who's data is undefined and point them at each other. One is the front sentinel the other the back sentinel. These nodes do not hold any data. Their purpose is to reduce special cases.

Empty linked lists for linked lists with sentinels will have 2 nodes. The front sentinel and the back sentinel

push_front()

The push_front function adds a node to the front of the linked list. As with all insertion of nodes, the process can be generally described in the following manner:

1. create a new node with the appropriate data

2. link the new node up with the rest of the list

Let us start by considering how this would work in a general linked list. The steps are:

Step 1: Create new node, next node is the node that follows the front sentinel. The previous node is the front sentinel.

Step 2: Make the previous pointer of the node that follows the front sentinel point to the new node

Step 3: Set the next pointer of the front sentinel to the new node.

Does the above always work?

In the non-sentinel version, we know that the function fails for empty linked lists. Does the above function work if you had an linked list that has sentinel nodes?

We begin with an empty linked list with sentinel nodes

Step 1: looks good so far

Step 2: No problem here

Step 3: and done... a valid linked list

As you can see from above, the same set of steps applied to the general case as well as empty list would end up with a proper linked list. Thus we only need one version of push_front function (3 steps, no special case checks)

void push_front(const T& data){
    Node* nn=new Node(data,front_,front_->next_);
    front_->next_->prev_=nn;
    front_->next_=nn;
}

pop_front()

The pop_front() function removes the first node from the linked list. The following are the general steps to remove a node:

1. check to make sure that the list isn't empty (or that the node to be removed actually exist).

2. unlink the node to be remove from the list (ensure other nodes are not lost in the process)

3. deallocate the memory for the node

Given the above steps, let us consider how this would work in the general case for pop_front(). The steps (with a check to ensure list isn't empty) are:

Step 1: Check to make sure list isn't empty. If it is do nothing. Otherwise continue to next steps. Remember that with sentinels, an empty list still has two nodes (the front and back sentinels). Our empty check is therefore going to look at whether those are the only nodes that exist. We can do this by checking if front sentinel's next_ pointer points to the back sentinel

Step 2: Make a local pointer point to the Node we want to remove. This will be the node that follows the front sentinel as it is the first node with real data. (hold this node so we don't lose it by accident)

Step 3: Make the front sentinel's next pointer point to second data node (the one that follows the one we want to remove

Step 4: Make the previous pointer of the node that now follows the front sentinel point back to the front sentinel

Step 5: deallocate the node we are removing

The code snippet to do this is:

if(front_->next_ != back_){  //check for empty list
    Node* rm = front_->next_;
    front_->next_=rm->next_;
    front_->next_->prev_=front_;
    delete rm;
}

Does the above always work?

When we looked at the linked list that did not use sentinels we saw that the general solution did not work when the node being removed was the only node left. Question is, will it work now if the node we want to remove is the only one left.

If we perform the four steps inside the if statement from the above snippet, this is what we will see:

Step 2:

Above looks fine.

Step 3:

This also looks correct

Step 4:

This was a problem in the non-sentinel version but we can see that there isn't a problem here. No nullptr access.

Step 5:

The final line is to delete the node. Notice now, that our list is essentially an empty linked list (with just the two sentinels). Thus, our function works for both the general and special case.

Putting all this together our pop_front() function should look something like this:

void pop_front(){
    if(front_->next_ != back_){  //check for empty list
        Node* rm = front_->next_;
        front_->next_=rm->next_;
        front_->next_->prev_=front_;
        delete rm;
    }
}