Double linked list with C++

The structure of a node in a double linked list is almost identical to that of a single linked list. The only difference is that the node in a double linked list will have an extra pointer. This can visually be seen a:

Now for the C++ code for this node.

struct node {

       node(int x) {

             data = x;

             previous = nullptr;

             next = nullptr;

       }

       int data;

       node* previous;

       node* next;

};

Here we can see that we are creating a standard to call the nodes. This being through a constructor. Where both previous and next will be set as a nullptr. The reason for this, is that we want to create the first node as something pointing to nullptr for both the previous and next pointer. Which can later be overwritten by a class we will have to make. Furthermore, it can be pointed out that the pointers in a double linked list can visually be seen as this:

Where node n1 is previous for n2, and node n3 is next for node n2. In other words, the pointers must point on the next and previous nodes. However, if one of the nodes aren't pointing to another spesific node, it must point to a nullptr.

Now that we have the structure for the node we can begin working on the class, which we will name as LinkedList. It's in this class we will specify how we differentiate between the nodes; who has to point to nullptr, and who has to point towards actual nodes.

class LinkedList {

public:

       LinkedList(){

             head = nullptr;

             tail = nullptr;

             size = 0;

       }

       void add_front(int x);

       void add_last(int x);

       void remove_front();

       void remove_last();

       void display();

       void front();

       void front_next();

       void last();

       void last_previous();

       bool is_empty();

       bool is_full();

private:

       node* head;

       node* tail;

       int size;

};

This will be our LinkedList structure. Now let's start creating the functions for it. We can start with add_front().

void add_front(int x) {

       node* new_node = new node(x);

       if (head == nullptr) {

             head = tail = new_node;

       }

       else {

             head->previous = new_node;

             new_node->next = head;

             head = new_node;

       }

       size++;

}

The first thing we observe with the add_front() function is that it takes one parameter. From there, it'll create a node that has data = x, previous = nullptr and next = nullptr. After that, we will have to differentiate between tail and head, and everything inbetween those.

In order to do that, we can check if head is equal to nullptr. This means that if head is equal to nullptr, it'll be the first node in our double linked list. Which translates into us starting our list with head and tail pointing at the first node. The previous and next pointers will also do nothing at this point, because these are supposed to point towards nullptr (set by the constructor). Visually we can see this as:

If this if-statement doesn't work for our scenario, we'll enter the else-statement. Where we are prepared to move all the new nodes "to the left" (imagine this visually). In other words, move head to the left. That'll also mean that tail will stand still in it's spot, and previous and next will be set to point at the correct nodes.

else {

       head->previous = new_node;

       new_node->next = head;

       head = new_node;

}

But let's take a closer look at what that really means. First we can see that head->previous = new_node, this will be the same as saying "We will get access to previous through head node and set the previous pointer equal to new_node". Furthermore, we will also set new_node->next = head, something that translates to "We will get access to next to node new_node through new_node and set the next pointer equal to the head node". I know this might be a bit heavy, but if you visualize this for yourself it will start to make sense. Lastly, we will set head pointer equal to new_node, this is because we want to declare the new node as the head. We can visually see this (with two nodes) as:

And if we were to add an extra node to this (changes marked in green):

Now that we're done with add_front() we can look at how we add to the back (tail) of the LinkedList. We will follow the same concept as with add_front(), but in this case we want tail to move instead of head. In other words, we will move our nodes to the right this time.

void add_last(int x) {

       node* new_node = new node(x);

       if (tail == nullptr) {

             tail = head = new_node;

       }

       else {

             tail->next = new_node;

             new_node->previous = tail;

             tail = new_node;

       }

       size++;

}

Here we can see that add_last() looks a lot like add_front(). The difference is that we are using the same logic "backwards". We can visually see this as:

Without going too much into detail about add_last(), simply because we went into detail with add_front(). Moving on, let's see ourselves done with these functions and move onto the next one. I will choose display(). Which will be the function that prints out the nodes in their respective order.

void display() {

       node* temp = head;

       for (int i = 0; i < size; i++) {

             std::cout << temp->data << " ";

             temp = temp->next;

       }

       std::cout << std::endl;

}

For the display() function we're using recursion. First we will make a temporary node pointer that we will call temp, which are set equal to head. From there on we will enter the for-loop and print out the data from temp, and move to the next (towards the right) for temp till we've reached the end of the list. The way we will know how far we should go with our recursion is because of the size variable we've been using when we created add_front() and add_last().

Let's look at some of the easy functions we have for our double linked list.

void front() {

       std::cout << head->data << std::endl;

}

void front_next() {

       std::cout << head->next->data << std::endl;

}

And the same for "the other side".

void last() {

       std::cout << tail->data << std::endl;

}

void last_previous() {

       std::cout << tail->previous->data << std::endl;

}

These functions will help us display information. One can also add the functions is_empty(), is_full() and size() if it is desired. But I covered that in single linked list, so we won't have to go into details about that here. Now, let's move on with remove_front().

void remove_front() {

       node* old = head;

       head = old->next;

       delete old;

       size--;

}

Here we can see that we're first creating a node pointer that we are naming old, which is then set equal to head. From there on we are setting head equal to old->next. From there on we will delete the old pointer. With this structure, we are able to move head one step "towards the right". We will do almost the exact same for remove_last().

void remove_last() {

       node* old = tail;

       tail = old->previous;

       delete old;

       size--;

}

From there on we can start playing around with adding new functions if we like. For example, we could've made a function get_middle_node() or add_middle_node() by using the size variable for this.

As a side note, we aren't using the is_empty() and is_full() in this code. But these would've been useful for checking if we can remove something from the list, or if we choose a limit on the list. This double linked list is currently a generic list that cannot be full, if there's space on the heap for it (Enough memory). This is because the nodes are stored in the heap and not in something like a fixed array.