Doubly Linked List in C++

Prerequisites

The prerequisites for understanding doubly linked lists in C++ require you to know basic C++ syntax as well as knowledge about the linked list data structure in C++. Pointers and their working along with a knowledge of structs in C++ may also come in handy. Let us move onto learning about doubly linked lists in C++.

Introduction to a Linked List

A Linked List is a data structure which consists of connected nodes. Each node is connected or linked to the next node, which is why it is called a linked list. Linked Lists can be of two types: Singly Linked List or Doubly Linked List.

You may be aware of singly linked lists, where each node consists of some data and is connected to the next node by a pointer which contains the next node's address. As we only have a pointer to the next node, we can travel in only one direction, the forward direction and hence the name singly linked list.

Conversely, a doubly linked list consists of nodes which have data, a pointer to the next node, but also a pointer to the previous node. Hence, we can travel in two directions in a doubly linked list, both forward and backward.

Hence, we generally use doubly linked lists in places where we may have to travel in both the forward and backward directions. We will be discussing the advantages, disadvantages and application of doubly linked lists in detail in the coming sections.

Representation of a Doubly Linked List Node in C++

As discussed above, a doubly linked lists consists of connected nodes. Each node contains three things:

1. Data: Information that the linked list contains.
2. "*"prev: Pointer to the previous node.
3. "*"next: Pointer to the next node.

Hence, a typical node in a doubly linked list will look like:

To create a doubly linked list in C++, we first need to represent the nodes. We use structures in C++ to represent one node of a doubly linked list, so we can create multiple such nodes and link them together using pointers to create a doubly linked list in C++.

The structure representing a node of the doubly linked list is defined as:

As you can see, here we have used data as an integer, but you can use any other data type if you want to store a different kind of data.

Another thing to note is, the first node doesn't have a previous node, so the previous pointer in this case will be set to NULL. Similarly, the last node won't have a next node and the next pointer will be set to NULL. This is the same as what is done for the last node of a singly linked list.

Let us look at a simple code to create a doubly linked list of a given size.

Output:

In the above code, we first created a structure that defines a node of the doubly linked list. Next we created a doubly linked list of two nodes. The first node had its previous pointer set to NULL and the next pointer pointing to the second node, while the second node had its next pointer set to NULL while the previous pointer was set to the first or the head node. This was the creation of a simple doubly linked list.

We inserted the two nodes in the above code one by one, which is highly redundant when we have a large amount of nodes. We will see how we can insert a node in a doubly linked list in C++ even more easily in the next section.

Insertion in Doubly Linked List in C++

Insertion in a doubly linked list in C++ means we create a new node with some data and add it to the linked list. Now, there can be three ways of inserting a node in a doubly linked list in C++. These are:

1. Insertion of node at the front of the list
2. Insertion of node after a given node of the list
3. Insertion of node at the end of the list

Let us look at each of these ways one by one.

At the Front of the Doubly Linked List

The steps to add a new node at the front of a doubly linked list are:

1. Create a new node with the required data value.
2. Set the previous pointer of this new node to NULL, as it will be added to the front of the doubly linked list and will not have any other node in front of it.
3. Set the next pointer of this new node to the current head of the doubly linked list as it will be placed in front of the head node.
4. The previous pointer of the current head node should be set to point to this new node.

The new node has been successfully added to the doubly linked list at the beginning. The diagram below illustrates the complete method.

Let us now look at the code in C++ to achieve the same.

Output:

In the above code, we have created a new function which adds a node to the start of the doubly linked list, whose start node is given as a pointer to it. It also takes the data as a parameter, which will be given to the new node. Inside the function, we created a new node with the given data.

Then assigned its previous pointer as NULL as it will be the first node. We assigned its next pointer to the current head node and then if this is not the first node being added, we change the previous pointer of the initial head node to point to this new node.

Next, let us look at the case where we may want to add the node somewhere in the middle of the doubly linked list in C++ or we can say, after a given node.

After a Given Node

The steps to add a new node after a given node in a doubly linked list are:

1. Create a new node with the required data value.
2. As we are adding the new node after the given node, it will take the place of the given node in the linked list after the insertion is done. Hence, set the next pointer of this new node to point to the node next to the given node.
3. Also, the old node will be in front of the new node after insertion, so set the next pointer of the given node to point to the new node we just made.
4. Also, the previous pointer of the new node should be set to point to the given node.
5. The node which was initially after the given node is still pointing to it with its previous pointer, so change it to point to the new node.
6. Ensure that you follow the steps in order, else the end of the linked list may be lost, if you change the next pointer of given node before assigning it to the new node.

The new node has been successfully added to the doubly linked list after the given node. The diagram below illustrates the complete method.

Let us now look at the code in C++ to achieve the same.

Output

In the above code, we have created a new function that adds a node after any given node of the doubly linked list. This means we are given that node after which the new node is supposed to be added. It also takes the data as a parameter, which will be given to the new node. Inside the function, we create a new node with the given data and assign it after the given node.

Now let us look at inserting a new node, but this time at the very end of the doubly linked list.

At the End of the DLL

We will be given the starting or the head of the doubly linked list as input. In such a case, the steps to add a new node at the very end of a doubly linked list are:

1. Create a new node with the required data value.
2. As we are adding the new node at the end of the doubly linked list, there will be no nodes after it so set its next pointer to NULL.
3. If the doubly linked list is already empty, then this new node will become the head. So, set its previous pointer to NULL and assign head pointer to this node.
4. Else, we travel to the end of the linked list, so our head pointer points to the last node in the linked list.
5. As our new node will be after this last node, set the next pointer of this last node to the new node, and the previous pointer of the new node to this last node.

The new node has been successfully added to the doubly linked list at the very end. The diagram below illustrates the complete method.

Let us now look at the code in C++ to achieve the same.

Output

Now let us look at inserting a new node before a given node in a doubly linked list.

Before a Given Node

The steps to insert a new node before a given node of a doubly linked list are very similar to that of insertion after a given node. Let us look at them:

1. Check for an edge case where the given node is NULL, if so return as we cannot insert a node before NULL.
2. Create a new node with the required data value.
3. As we are adding the new node before the given node, it will take the place of the given node in the linked list after the insertion is done. Hence, set the previous pointer of this new node to point to the current previous of the given node.
4. The new node will be before the given node, so set the previous pointer of given node to the new node, and the next pointer of the new node to the given node.
5. If the node before the given node is NULL, it means our new node is the start of the linked list, so assign head to the new node.
6. Else, make the next pointer of the node before the given node point to the new node.

The new node has been successfully added to the doubly linked list before the given node. The diagram below illustrates the complete method.

Let us now look at the code in C++ to achieve the same.

Output

Constructor Call to Initialize Node

In the above codes, you may have noticed how in every function the first step was the same. This was creating a new node and then assigning some data to it. This is a bit of a redundant code which we have to write again and again in all functions.

But, for a better and well written code, we can reduce this redundancy by using a class to define the node structure and adding a custom constructor to the definition of the node structure. This contructor will take a data value as input, create a new node and initialize it with this data and return it to us, instead of returning an empty node. This will not only decrease the lines of code, but also make it cleaner and better to understand.

The class representing a node of the doubly linked list in such a case will be:

Let us next look at deletion of a node from the doubly linked list in C++.

How to Delete a Node in DLL?

In a singly linked list, we need the pointer to the node before the node we want to delete. But in a doubly linked list we have the previous pointer in the node itself.

Let us look at the steps to delete a node of a doubly linked list in C++.

1. Check if this node is the head node. If yes, then simply assign head to the next of this node.
2. Else, assign the next pointer of the previous node to point to this nodes next.
3. If the next pointer of the given node points to NULL, it means the node is the last node, and it is deleted.
4. Else, make the previous pointer of the next node point to the previous node of the given node.

The given node has been successfully deleted from the doubly linked list. The diagram below illustrates the complete method.

Let us now look at the code in C++ to achieve the same.

Output

Some Other DLL Techniques:

We looked at the basic operations such as insertion and deletion in a doubly linked list, but there are many other things we can perform in a doubly linked list in C++. Let us look at some of them next.

Traversing a DLL

In a singly linked list we know we can travel only in the forward direction, but as a doubly linked list has both previous and next pointers, we can travel in both forward and reverse directions in a doubly linked list in C++.

Let us look at both of these traversals one by one.

Forward Traversal

In forward traversal, we just need to follow the next pointers of the nodes of the doubly linked list until we reach the end, which is denoted by the NULL pointer. This can be easily achieved using a while loop in C++.

The diagram below illustrates the concept.

Let us now look at the code in C++ to achieve the same.

Output

Backward Traversal

Backward traversal is same as forward traversal, the only difference is we need to use the previous pointers of the nodes of a doubly linked list until we reach the start of the doubly linked list, which is again denoted by the NULL pointer. This can also be achieved with a simple while loop in C++.

The diagram below illustrates the concept.

Let us now look at the code in C++ to achieve the same.

Output

Searching a Node in DLL

The searching operation in a doubly linked list os very similar to that in a singly linked list. We will have to travel the linked list until we find the matching data.

Let us look at the code in C++ to search a particular node in a doubly linked list.

Output

Reverse a DLL

Reversing a doubly linked list involves reversing or swapping the next and previous pointers of all the nodes. So basically to reverse a doubly linked list we need to traverse the linked list and just swap the next and previous pointers of all the nodes.

Let us look at the code in C++ for the same.

Output

Advantages of DLL over the Singly Linked List

• A doubly linked list has both next as well as previous pointer unlike singly linked list which has only the next pointer.
• The doubly linked list can be traversed in both the forward as well in the backward direction as opposed to singly linked list which we can travel only in the forward direction.
• We can delete a node in a doubly linked list by just having the pointer to the node to be deleted. In a singly linked list we need the node before the node to be deleted.

Disadvantages of DLL over the Singly Linked List

• The operations on a doubly linked list, such as insertion and deletion are complex because of the presence of two pointers, next and previous in every node.
• Each node of the doubly linked list has to store two pointers, previous and next which takes up more memory space as compared to a singly linked list.

Applications of Doubly Linked List

• A doubly linked list has the most useful application of being used in systems where backward and forward traversals are required.
• Web browsers use a doubly linked list data structure to implement going back to the website you last visited, or to go forard in your search history as well.
• Undo and Redo functionality can also be implemented by storing all operations performed in the form of a doubly linked list data structure.
• Many thread schedulers also use a doubly linked list to schedule processes.
• Other data structures such as hash maps, binary trees and stacks can also be implemented using a doubly linked list.