Doubly linked list is a collection of nodes linked together in a sequential way. Each node of the list contains two parts (as in singly linked list) data part and the reference or address part. The basic structure of node is shown in the below image:
Doubly linked list is almost similar to singly linked list except it contains two address or reference fields, where one of the address field contains reference of the next node and other contains reference of the previous node. First and last node of a linked list contains a terminator generally a NULL value, that determines the start and end of the list. Doubly linked list is sometimes also referred as bi-directional linked list since it allows traversal of nodes in both direction. The basic structure of a doubly linked list is represented as:
Since doubly linked list allows the traversal of nodes in both direction hence we can keep track of both first and last nodes.
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.
Applications/Uses of doubly linked list in real life
There are various application of doubly linked list in the real world. Some of them can be listed as:
- Doubly linked list can be used in navigation systems where both front and back navigation is required.
- It is used by browsers to implement backward and forward navigation of visited web pages i.e. back and forward button.
- It is also used by various application to implement Undo and Redo functionality.
- It can also be used to represent deck of cards in games.
- It is also used to represent various states of a game.
Basic operations performed on Doubly linked list
- Creation and traversal of list.
- Insertion of node.
- Deletion of node.
- Deletion of entire list.
- Counting total number of nodes.
- Searching an item in list.
- Reversing the list.
Note: Deleting entire list, counting elements or searching an element in doubly linked list programs are similar to singly linked list programs.