Data structures are a way of storing and retrieving data in an efficient manner. Data structures may be linear or non-linear depending on whether they store data sequentially or not. Linear data structures include arrays, stack, queues and linked list.
Non-linear include trees and graphs. Each data structures contain information about the type of data it stores, the relationship between data and operations allowed on the data structure. Data Structures can also be categorised as Homogeneous and Non-Homogeneous depending on whether the data stored in a repository is of the same type or not. How data structures are compiled can also be a deciding factor for their categorisation.
Before learning about the features, let us understand what Doubly Linked List is. It is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields and one data field.
Linked list are linear data structures that has a collection of nodes connected to each other. It’s more like a chain structure. Each node consists the type of data it stores and a reference to the next node. Here are some points that make a linked list better than arrays.
- A linked list is dynamic in nature, which means they can grow and shrink at runtime. This also ensures no memory wastage.
- Insertion and deletion of nodes in a linked list are easier. Insertion and deletion in arrays require shifting of nodes.
- Other linear data structures like stacks and queue can also be implemented using linked lists.
- Converting a linked list to other forms of non-linear data structures like trees is also possible.
Linked lists can be classified as Singly, Doubly and Circular Linked lists. A basic C++ structure of node in a singly linked list is shown below.
Doubly Linked List
Doubly linked list or more commonly referred to as DLL is similar in node structure as that for a singly linked list except for the fact that they have an extra pointer which is used for back traversal on the list. It has two pointers namely next and previous. DLL can be considered as a variation of the singly linked list. Here one pointer (or reference) points to the next node and the other pointer points to the previous node.
The previous pointer for the first node points to NULL. A node structure in a doubly-linked list is as follows.
Many would have been wondering what would be the use of such data structure in real world. Well consider the following situations.
- A music player which has next and previous buttons.
- Undo Redo operations
- The Browser cache which allows you to move front and back between pages is also a good example of doubly linked list.
- LRU cache
- Most Recently Used is also an example of DLL.
- A deck of cards in a game is a classic example of application of DLL. It is also used to store state of game during play.
The entire above mentioned scenario makes use of doubly linked list. But why are we using DLL for all the above mentioned cases. Well here are some key points to note while learning DLL.
- Just like Singly Linked lists they are easy to implement.
- Allow traversal in both directions.
- Deletion of nodes is easier as compared to singly linked lists.
- Can allocate or de-allocate memory easily when required during execution.
Now we will move on to how and what operations are performed on doubly linked lists.
- Inserting a node at the front: Inserting a new node means making the head point to the new node and breaking its link with the previous node. We also need to point the previous pointer of the new node to NULL and previously new node previous pointer to a new node.
2. Inserting a node at the end: While inserting a node at the end of the linked list we need to do the following:
- Make the next pointer of New Node to NULL.
- Make the previous pointer of the New Node to point the previous last node.
- Make the previously last node next pointer point to New Node.
3. Inserting Node in between: This is more complicated than the above insertion process and its implementation must be done carefully. In real-world, this functionality is mostly used. In this process, the new node comes in between two nodes. Let’s denote the nodes N1 and N2.
Here the New Node N will be after N1 and before N2. Now we need to do the following:
- Make the next of N1 point to New Node and previous of New Node to N1.
- Point Next of New Node to N2 and previous of N2 to New Node.
Deletion also involves three different types namely deletion from front, deletion in between and deletion at end. All these steps have a common algorithm. Obviously the implementation depends on the syntax of language but the algorithm remains same. While deleting a node in a Doubly Linked list we first re-position the pointer pointing to that particular node so that the previous and after nodes do not have any connection to the node to be deleted. Follow the below mentioned steps to delete a node in a doubly linked list
- If the first, node is to be deleted then make head point to next of deleted node. Simply point head->next= deleted Node->next. We also need to make previous next node as NULL.
- If the last, node is to be deleted the next pointer of the previous node must be set to NULL.
- If an in-between node is to be deleted simply connect next and previous node of the node. This point will be more clear from the below diagram.
The above diagram shows how node B is deleted and nodes A and C are connected. The implementation must be done very precisely specially while changing the pointers.
Searching in a doubly-linked list is similar to that of singly list. We need to traverse the entire list and search for target value. If the value of a node equals the target node we simply print that value and return 1 indicating value is present in linked list else return 0 indicating the absence of the target node. A simple C++ implementation is shown below:
This operation also makes a doubly linked list very useful for practical purposes. We have already used two pointers in a DLL node so that the previous node can be accessed easily. Reversing a Doubly Linked List is fairly easy as compared to a singly linked list. All we need to do is swap the two pointers for the entire list and also swap the head and tail pointers.
A C++ code snippet for the same is given below. Alert! Do read the comments for better understanding.
Like the two sides of a coin, every data structure has its own pros and cons. Disadvantages of DLL include the following
- Extra memory for an extra pointer, i.e. previous pointer. Hence memory space consumed is more than the singly linked list.
- Implementation can be hectic. Need to take care of the allocation of pointers while implementing functions for different operations and thereby making a performance bottleneck.
To read more about Linked List, click here.
By Mridul Kumar