What Is Doubly Linked List in Data Structure With Example?
A doubly linked list is a type of data structure that consists of a sequence of elements, where each element contains a reference to the previous and the next element in the sequence. This allows for efficient traversal in both directions, forward and backward.
Structure of a Doubly Linked List
A doubly linked list is composed of nodes, where each node contains two pointers: one to the previous node and one to the next node. The first node in the list is called the head, while the last node is called the tail. The head node’s previous pointer points to null, indicating that it is the first element, and the tail node’s next pointer also points to null, indicating that it is the last element.
The basic structure of a doubly linked list can be represented as follows:
- Node: Contains data and two pointers – previous and next.
- Head: Points to the first element in the list.
- Tail: Points to the last element in the list.
Doubly Linked List Operations
A doubly linked list supports various operations that can be performed on it:
- Insertion: Elements can be inserted at different positions within a doubly linked list. For example, an element can be inserted at the beginning (before the current head), at a specific position (between two existing nodes), or at the end (after the current tail).
- Deletion: Elements can be deleted from a doubly linked list.
Similar to insertion, elements can be deleted from the beginning, a specific position, or the end of the list.
- Traversal: It is possible to traverse a doubly linked list in both forward and backward directions. Starting from the head node, each node can be accessed by following the next pointers until reaching the tail node. Similarly, starting from the tail node, each node can be accessed by following the previous pointers until reaching the head node.
Example of Doubly Linked List
Let’s consider an example to better understand how a doubly linked list works:
We have a doubly linked list that contains five elements: 10, 20, 30, 40, and 50. The initial state of the list is as follows:
- Head -> null (points to null)
- Tail -> null (points to null)
To insert an element at the beginning of the list (before the current head), we add element 5:
- Insertion at beginning:
Head -> [5 | prev: null | next: 10] <- Tail
[10 | prev: 5 | next: 20]
[20 | prev: 10 | next: 30]
[30 | prev: 20 | next: 40]
[40 | prev: 30 | next: 50]
[50 | prev: 40 | next: null]
To insert an element at a specific position (between two existing nodes), we add element 25 between nodes with values of 20 and 30:
- Insertion at specific position:
Head -> [5 | prev: null | next: 10]
[10 | prev: 5 | next: 20]
[20 | prev: 10 | next: 25]
[25 | prev: 20 | next: 30]
[30 | prev: 25 | next: 40]
[40 | prev: 30 | next: 50]
[50 | prev: 40 | next: null] <- Tail
To delete an element from the list (at a specific position), let's remove the node with a value of 25:
- Deletion at specific position:
Head -> [5 | prev: null | next: 10]
[10 | prev: 5 | next: 20]
[20 | prev: 10 | next: 2530]
[2530|prev:2010|next:3040]
[30|prev:2530|next:4050]
[40|prev:30|next:50null] <- Tail
Conclusion
A doubly linked list is a versatile data structure that allows for efficient traversal in both forward and backward directions. It provides flexibility in terms of insertion and deletion operations at different positions within the list. Understanding the concept and implementation of a doubly linked list is crucial for designing efficient algorithms that require bidirectional traversal or dynamic insertions and deletions.
Now that you have a solid understanding of doubly linked lists, you can explore and implement them in your own projects!