push_front and pop_front

Implementation - push_front(), pop_front()

This section of the notes walks through the implementation of push_front() and pop_front()

Python

push_front(data)

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 current front of list, there is no previous node which means that next node's prev should be set to a nullptr:

Step 2: Make the previous node of the current front of list point to the new node

Step 3: Make the front pointer point to the new node

Putting this together in code:

nn = self.Node(data, self.front)
self.front.prev = nn
self.front = nn

Does above always work?

Now lets consider if the following would work if we started off with a linked list that is empty.

Step 1:

Step one will run without problems

Step 2:

self.front is None, so self.front.prev will crash. Thus, it looks like we need to skip this step or do something different if we have an empty list

Step 3:

The above will work. However, if we were to simply skip step 2, our linked list would not be valid as back would not be correctly set. The node we just added is not only the first node in the linked list but also the last. To make this work, we should add code to make back point to nn.

Putting all this together, The final function would look like the following:

def push_front(self, data):
    nn = self.Node(data, self.front)
    if self.front is None:
        self.back = nn
    else:
        self.front.prev= nn
    self.front = 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. The steps for performing a pop_front are:

Step 1: Check to make sure list isn't empty. If it is do nothing. Otherwise continue to next steps

Step 2: Make a local pointer point to the first node in the list (hold this node so we don't lose it by accident)

Step 3: Make the front pointer point to the second node

Step 4: Make the new front node's previous pointer a nullptr

The code snippet to do this is:

if self.front is not None:
    rm = self.front
    self.front = self.front.next
    self.front.prev = None
    del rm

Does the above always work?

The snippet of code above works for the general linked list and empty linked lists. However, does it always work? Let us consider the following situation. If we only had one node left in the list, would the above snippet still work?

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:

If we were to try to do the above at this point we would end up crashing the program as front is currently nullptr. This step will either need to be skipped for lists with just one node or something differnt will need to be done

The list is not in a valid state. We have a back pointer that points to the memory location of the node that should be deallocated. This pointer is therefore invalid. For lists with just one node, we must also adjust the back pointer to a nullptr/None (as the list should get empty after removing its only node.)

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

def pop_front(self):
    if self.front is not None:
        rm = self.front
        self.front = self.front.next
        if self.front is None:
            self.back = None
        else:
            self.front.prev = None
        del rm

C++

push_front(data)

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 current front of list, there is no previous node which should be set to a nullptr

Step 2: Make the previous node of the current front of list point to the new node

Step 3: Make the front pointer point to the new node

Putting this together in code:

Node* nn = new Node(data,front);
front->prev=nn;
front=nn;

Does above always work?

Now lets consider if the following would work if we started off with a linked list that is empty.

Step 1:

Step one will run without problems

Step 2:

front is nullptr, so front->prev will crash. Thus, it looks like we need to skip this step or do something different if we have an empty list

Step 3:

The above will work. However, if we were to simply skip step 2, our linked list would not be valid as back would not be correctly set. The node we just added is not only the first node in the linked list but also the last. To make this work, we should add code to make back point to nn.

Putting all this together, The final function would look like the following:

void push_front(const T& data){
    Node* nn = new Node(data,front);
    if(front){
        front->prev=nn;
    }
    else{
        back=nn;
    }
    front=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 removed 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. The steps for performing a pop_front are:

Step 1: Check to make sure list isn't empty. If it is do nothing. Otherwise continue to next steps

Step 2: Make a local pointer point to the first node in the list (hold this node so we don't lose it by accident)

Step 3: Make the front pointer point to the second node

Step 4: Make the new front node's previous pointer a nullptr

Step 5: deallocate the node we are removing

tip

delete p; does not deallocate the pointer p itself. Rather it deallocates what the pointer points at. Thus, delete rm; deallocates the node rm points at.

The code snippet to do this is:

if(front){
    Node* rm = front;
    front=front->next;
    front->prev=nullptr;
    delete rm;
}

tip

A common misconception is that when you declare a pointer, you must use new. Unless you are trying to create an instance of the object, you do not need to use new. If you are using the pointer to simply refer to something that exist (like rm in the code above), there is no reason to use new and in fact, if you used new, you would end up with a memory leak.

Does the above always work?

The snippet of code above works for the general linked list and empty linked lists. However, does it always work? Let us consider the following situation. If we only had one node left in the list, would the above snippet still work?

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:

If we were to try to do the above at this point we would end up crashing the program as front is currently nullptr. This step will either need to be skipped for lists with just one node or something differnt will need to be done

Step 5:

The final line is to delete the node, which won't crash. However, the list is not in a valid state. We have a back pointer that points to the memory location of the node that has now been deallocated. This pointer is therefore invalid. For lists with just one node, we must also adjust the back pointer to a nullptr as the list is now empty

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

void pop_front(){
    if(front_){
        Node* rm = front;
        front=front->next;
        if(front==nullptr){  //if only one node exists
            back=nullptr;
        }
        else{
            front->prev=nullptr;
        }
        delete rm;
    }
}