C++

Implementation of Doubly Linked List C++

A doubly Linked list is the structural concept in C++ that consists of 1 or more nodes. A single node must have three parts i.e., data, a reference towards the previous node, and the next upcoming node. The very first node is said to be the “head” node that is used to access the overall linked list. The very last node of a linked list always has the NULL value. If you are new to this concept and looking for authentic resources to get knowledge, then this guide is for you.

Let’s start this article with the new C++ file creation. We have to create it using the terminal “touch” query. After the file creation, our next task is to open it and create some c++ code. For the opening, you can make use of any built-in editor of Ubuntu 20.04 like a text editor, vim editor, or Gnu nano editor. So, we are using the “nano” instruction on our shell to open the doubly.cc file in it.

Example 01:

Let’s make a basic example of C++ code to create a double-linked list. After the file opening, we have added the iostream. The c++ standard namespace will be utilized. After this, we have been creating a node structure named “Node” with some of its elements. It contains the integer variable “d” as the data part. Then, we have defined three new node structures. The “p” node is showing the previous node, “n” is showing the next node, and the head node “h” is specified NULL as another node.

Now, the above structure is of no use until we add and show some nodes in the program code. We are using the add() function to get the node data from the main() function. At its first line, we have been creating a new node “new node” using the structure “Node” and assigning it a memory that is equal to the size of a “Node”. The “->” sign characters are used for referencing towards the node parts i.e., next, previous, data, etc. Thus, we have been referencing the data of a new node using -> sing and adding data passed by the main() function in parameter “nd” into the “d” variable of a new node. The previous node of a new node will be initialized to NULL and its next node will be a “head”. The “if” statement is here to check that the value of head “h” is not equal to NULL. If the value of “h” is not NULL, it will make the previous node of a “head” node, a new node. Also, the head will be a new node as well i.e., having a value of a new node.

Here comes the “show()” function to display the created node. Within it, we have created a “ptr” node and made it a “head”. The “while” loop is here to confirm that the value of “ptr” is not NULL. While the condition is satisfied, the cout statement will display the data added by a user in the same but opposite manner. Now, the next of “ptr” nodes will become “ptr”.

Here is our main() function from where the execution starts. We have called the “add” function 4 times to create a new node and add data into the “d” variable of a new. The cout statement is showing us that we will be calling the “show” function to display all the nodes we have added.

Now, it’s time to compile this c++ code in ubuntu’s g++ compiler for the C++ language. On running the code with “./a.out”, we have been displayed with the 4 nodes data in opposite order i.e., we have added in 4, 12, 2, 7 order and it returns in 7, 2, 12, 4, showing the last come first serve order.

Example 02:

Let’s look at another example of a doubly-linked list. Created a structure “Node” with the same variable “d”, next node “n” and previous node “p”.

Now, we have been utilizing the Frontpush() function to insert a node at the start with its data i.e. head node. We have created a new node within it i.e. “newNode” using the structure “Node*” syntax. After this, we are referencing its data “d”, its next node that will be a “head”, and the previous node that will be NULL. The “if’ statement was used to check that the value of the head is not NULL. If the head is not “NULL” already, we have to make the previous head a new node, and the header will point towards the new node.

The afterpush() function is here to insert a new node after our already made node. The “if” statement will check whether the previous node is equal to NULL or not and display that using the “cout”. A new node has been formed and data will be inserted into “d”. The “next” of the new will become the next of the previous, and the next of the previous will become a new node. The previous of new will become the previous itself. If the next of new is not equal to NULL, we will make the next of the new which is also next of the new, a new node.

Now, we will be using the “Endpush” function to insert a new node at the end of a linked list. The new node has been created and data passed by main() is assigned to “d” and next of new is NULL. We have been storing the head temporarily. The “if” will check if the linked list is empty and make the new node “head”. The “while” will traverse the linked list if the linked list is already not empty. As the “temp” is our last node, we have assigned the next temp to “new”. The previous of new is assigned to “temp”.

The delete() method is using different “if” statements to exchange next and previous of del-node, and head node. In last, the “free” function is used to free up the memory of a del-node.

The show() function of this program is again used to print out the doubly linked list.

The main() function starts executing by initializing the head node to NULL. The “Endpush” function is called for inserting a node at the end by passing “head” and 5 as data. Frontpush() is used twice to add a node at the front of the linked list. After “endpush()” usage again, we have used “Afterpush()” twice. The show() and “Delete()” functions are used one after another, while the “delete” is used to delete every last node from the linked list, and show() is displaying that.

The compilation and execution is showing the start to end linked list i.e., after each node deletion.

Conclusion

This article is explaining the simple code examples to create a doubly linked list in C++ while using the Ubuntu 20.04 Linux system. We have also taken a look at the ways to insert a node at the start and end of the linked list and insert after an already made node i.e., in between. The delete function was deleting each node every single time from the linked list.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.