What is a Doubly linked List in Data Structure?
A doubly linked list is a data structure in which each node contains a reference to both the next and the previous node. This allows for easy traversal in both directions, and also allows for efficient insertion and deletion operations. Each node typically contains a value or data and a reference to the next node, and a reference to the previous node. This is in contrast to a singly linked list, in which each node only contains a reference to the next node.
How Doubly linked List Works in Data Structure?
A doubly linked list works by having each node in the list contain a reference to both the next and previous nodes. This allows for easy traversal in both directions.
Insertion: To insert a new node into the list, the new node's previous reference is set to the node that currently precedes it, and the new node's next reference is set to the node that currently follows it. Then, the previous and next nodes' references are updated to include the new node.
Deletion: To delete a node from the list, the previous and next nodes' references are updated to remove the node being deleted, and the node being deleted is removed from memory.
Traversal: To traverse the list, you can start at the head or the tail of the list, and follow the next or previous references, respectively, to move through the list.
Doubly linked list also have some advantages over singly linked list, for example, a doubly linked list can be traversed in both directions whereas singly linked list can be traversed in one direction only.
Types of Doubly linked List
There are several types of doubly linked lists:
Circular Doubly Linked List: In this type of list, the last node's next reference points to the first node, and the first node's previous reference points to the last node. This creates a circular loop, allowing for easy traversal in both directions without having to check for the end of the list.
XOR Doubly Linked List: In this type of list, each node contains a reference to the next node, but instead of storing the previous node's reference, it stores the XOR of the current node's memory address and the next node's memory address. This allows for efficient traversal in both directions, but it can be difficult to implement.
Sentinel Doubly Linked List: In this type of list, an extra node called a sentinel is added to the list. The sentinel node acts as a placeholder and allows for easier implementation of certain operations such as insertion and deletion.
Head-Tail Doubly Linked List : In this type of list, two pointers are maintained, one pointer pointing to the head and the other pointer pointing to the tail of the list. This allows for constant time insertion and deletion at the head and tail.
Threaded Doubly Linked List: In this type of list, in addition to next and previous references, each node also has a flag indicating whether it's a thread or not. This allows for efficient traversal without the need for explicit stack operations.
Each of these types of doubly linked list have their own advantages and disadvantages, and the choice of which type to use depends on the specific requirements of the application.
Example of Doubly linked List
Here is an example of a basic doubly linked list implementation in C++:
#include <iostream>
class Node {
public: int data;
Node* next;
Node* prev;
Node(int data) {
this->data = data;
this->next = nullptr;
this->prev = nullptr;
}
};
class DoublyLinkedList {
private: Node* head; Node* tail;
public: DoublyLinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void insertAtHead(int data) {
Node* newNode = new Node(data);
if (this->head == nullptr) {
this->head = newNode;
this->tail = newNode;
return;
}
newNode->next = this->head;
this->head->prev = newNode;
this->head = newNode;
}
void insertAtTail(int data) {
Node* newNode = new Node(data);
if (this->tail == nullptr) {
this->head = newNode;
this->tail = newNode;
return;
}
newNode->prev = this->tail;
this->tail->next = newNode;
this->tail = newNode;
}
void deleteAtHead() {
if (this->head == nullptr) {
return;
}
if (this->head->next == nullptr) {
this->head = nullptr;
this->tail = nullptr;
return;
}
this->head = this->head->next;
this->head->prev = nullptr;
}
void deleteAtTail() {
if (this->tail == nullptr) {
return;
}
if (this->tail->prev == nullptr) {
this->head = nullptr;
this->tail = nullptr;
return;
}
this->tail = this->tail->prev;
this->tail->next = nullptr;
}
void printList() {
Node* current = this->head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList list;
list.insertAtHead(5);
list.insertAtHead(10);
list.insertAtTail(15);
list.insertAtTail(20);
list.printList(); // Output: 10 5 15 20
list.deleteAtHead();
list.deleteAtTail();
list.printList(); // Output: 5 15 return 0;
} Please note that the example is to show the basic structure of doubly linked list and demonstrate the use of it, the actual implementation may have different requirements and constraints.
Applications of Doubly linked List
Doubly linked lists have a number of useful applications, here are a few examples:
Caching: A doubly linked list can be used to implement a cache eviction policy, where the least recently used item is removed from the cache when it becomes full.
Graphs: A doubly linked list can be used to implement a graph data structure, where each node in the list represents a vertex in the graph, and the next and previous references represent the edges between the vertices.
Undo/Redo: A doubly linked list can be used to implement an undo/redo feature in an application, where each node in the list represents a change that has been made, and the next and previous references allow for easy traversal through the list of changes.
Browser history: A doubly linked list can be used to implement a browser history feature, where each node in the list represents a webpage that has been visited, and the next and previous references allow for easy traversal through the list of webpages.
Text editors: A doubly linked list can be used to implement a text editor feature, where each node in the list represents a character in the text, and the next and previous references allow for easy insertion and deletion of characters.
Game development: In game development, doubly linked list can be used for collision detection, pathfinding, etc.
Database management: Doubly linked list can be used in database management systems for indexing and data retrieval.
Memory management: A doubly linked list can be used to implement a memory management algorithm, where each node in the list represents a block of memory, and the next and previous references allow for easy traversal through the list of memory blocks.
Time and Space Complexity of Doubly linked List
The time and space complexity of operations on a doubly linked list depend on the specific implementation.
Insertion at the head: O(1) time complexity and O(1) space complexity.
Insertion at the tail: O(1) time complexity and O(1) space complexity.
Deletion at the head: O(1) time complexity and O(1) space complexity.
Deletion at the tail: O(1) time complexity and O(1) space complexity.
Searching for a specific element: O(n) time complexity, where n is the number of elements in the list.
Traversing the list: O(n) time complexity, where n is the number of elements in the list.
Accessing an element by index: O(n) time complexity, where n is the number of elements in the list.
In terms of space complexity, a doubly linked list uses O(n) space, where n is the number of elements in the list. This is because each element in the list requires two references (prev and next) in addition to the data stored at each node.
Overall, doubly linked list offers constant time complexity for insertions and deletions at both head and tail, but linear time complexity for other operations and space complexity is linear O(n).
Advantages and Disadvantages of Doubly linked List
Advantages of a doubly linked list:
Efficient insertion and deletion: Because each node in a doubly linked list contains references to both the next and previous nodes, insertion and deletion operations can be performed in constant time.
Traversal in both directions: Because a doubly linked list contains references to both the next and previous nodes, it can be easily traversed in both directions.
Dynamic memory allocation: A doubly linked list can be implemented using dynamic memory allocation, which means that the list can grow and shrink as needed.
Better cache locality: A doubly linked list has better cache locality than an array or a singly linked list, which can improve performance in certain cases.
Flexibility: Doubly linked list can be used in a wide range of applications such as caching, undo/redo feature, browser history, text editors, game development, database management, memory management, etc.
Disadvantages of a doubly linked list:
Increased overhead: A doubly linked list uses more memory than a singly linked list, as each node contains two references (prev and next) in addition to the data stored at each node.
More complex implementation: A doubly linked list is more complex to implement than a singly linked list, as it requires maintaining two references (prev and next) for each node.
Extra memory usage: It uses extra memory for maintaining the previous pointer, which can be an issue when memory is limited.
Not always efficient: For certain operations such as searching and access by index, doubly linked list is not as efficient as other data structures such as arrays or binary trees.
Harder to implement: Implementing certain types of doubly linked list such as XOR doubly linked list and Threaded doubly linked list can be difficult.