Linear Data Structures — Doubly Linked Lists

In the last article, we learnt about Linear Data Structures and particularly Linked lists, and also got to know about the advantages of Linked lists and arrays over each other. We also learnt about Singly Linked lists in detail. In this article, we are gonna dive into Doubly Linked lists. If you haven’t read the previous one, kindly have a look and come back!

Linear Data Structures — Linked Lists

Courtesy: Towards Data Science

What is a Doubly Linked List?

A Doubly linked list is a linear data structure in which each node consists of three fields viz., the data field, previous, and the next field. The previous and the next are the address fields that store the address of the previous element and the next element respectively.

Courtesy: Geeks for Geeks

A DLL can be represented as shown above. However, in memory, the elements are not stored in a contiguous manner as we can see below.

The first element of the list is called the head and the last is called the tail. Each node has three fields; the previous is the pointer storing the address of the previous element in the list and the next is another pointer that stores the address of the next element in the list and the data field is where the value is stored. As you can see that the last element has the next pointer set to NULL since there are no more elements after that.

Now that we have understood the structure of the DLL, let us compare it with SLL and see what advantages this has to offer over SLL.

1. A DLL can be traversed in both forward and backward direction.

2. We can easily insert a node before a given node.

But DLL also suffers from some limitations such as:

1. Every node of DLL requires extra space for a previous pointer.

The operations that can be performed on a DLL are :

1. Insertion
2. Deletion
3. Traversal

Before we perform any of these operations, we need to create the node for the head. Let us see how we create a node. (The language used in this article for demonstration is C++).

Now we have created the node, let us see how to add the new node to the linked list.

The addNode() function takes two arguments viz., the reference to the head node and the data to be inserted. While inserting it is important to check if the head is already NULL. If it is so, then the new_node becomes the head. Otherwise, we will traverse to the end of the list and insert the node after the last node and make the new_node to be the last node.

We can traverse the Linked list both in the forward and backward directions. Let us see how!

We can traverse in the reverse direction by starting from the last node and print the data each time using the previous pointer.

Now, let us see how to delete a node. Suppose if we want to delete a particular element in the middle of the linked list:

Now, We make use of these functions to create a linked list and add nodes as shown below:

Exercise:

1. As an exercise, try to implement a function that would delete the last element of the linked list.
2. As an exercise, try to implement a function that would add elements at the beginning of the linked list.

Hope you enjoyed reading the article!

If you have any queries please post in the comment section below. Connect with me on LinkedIn. Also, if you want to look at my amazing collection of apps developed, don’t forget to check Google Play Store.

Know more about me here.

With that being said, thanks for reading my article, and Happy Coding!

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer