Advantages, Disadvantages, and uses of Doubly Linked List
A Doubly Linked List(DLL) is a linear data structure that contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in a singly linked list. Below is the image to illustrate the same.
Advantages Of DLL:
- Reversing the doubly linked list is very easy.
- It can allocate or reallocate memory easily during its execution.
- As with a singly linked list, it is the easiest data structure to implement.
- The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
- Deletion of nodes is easy as compared to a Singly Linked List. A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.
Disadvantages Of DLL:
- It uses extra memory when compared to the array and singly linked list.
- Since elements in memory are stored randomly, therefore the elements are accessed sequentially no direct access is allowed.
Uses Of DLL:
- It is used in the navigation systems where front and back navigation is required.
- It is used by the browser to implement backward and forward navigation of visited web pages that is a back and forward button.
- It is also used to represent a classic game deck of cards.
- It is also used by various applications to implement undo and redo functionality.
- Doubly Linked List is also used in constructing MRU/LRU (Most/least recently used) cache.
- Other data structures like stacks, Hash Tables, Binary trees can also be constructed or programmed using a doubly-linked list.
- Also in many operating systems, the thread scheduler(the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.
Introduction
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, stacks, queues, and linked lists.
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 categorized 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 categorization.
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.
Basic structure of a doubly linked list
The basic structure of a doubly linked list contains a data field and two address fields. Here is how it can be represented in C programming language.
struct node { int data; // Data field struct node * prev; // Address of previous node struct node * next; // Address of next node };Advantages of Doubly linked list
Doubly linked list is one of the important data structures. Here are various advantages of doubly linked list.
- As like singly linked list it is the easiest data structures to implement.
- Allows traversal of nodes in both direction which is not possible in singly linked list.
- Deletion of nodes is easy when compared to singly linked list, as in singly linked list deletion requires a pointer to the node and previous node to be deleted. Which is not in case of doubly linked list we only need the pointer which is to be deleted.
- Reversing the list is simple and straightforward.
- Can allocate or de-allocate memory easily when required during its execution.
- It is one of most efficient data structure to implement when traversing in both direction is required.
Disadvantages of Doubly linked list
Not many but doubly linked list has few disadvantages also which can be listed below:
- It uses extra memory when compared to array and singly linked list.
- Since elements in memory are stored randomly, hence elements are accessed sequentially no direct access is allowed.