In the world of data structures, linked lists play a crucial role in implementing dynamic collections of elements. A doubly linked list is a variation of the traditional linked list, enhancing its capabilities by providing bidirectional traversal. This blog aims to introduce and explore the concept of doubly linked lists, shedding light on their benefits, implementation, and common use cases.
Table of Contents
- What is a Doubly Linked List?
- Structure of a Node
- Advantages of Doubly Linked Lists
- Operations on Doubly Linked Lists
- Use Cases
- Code
- Conclusion
What is a Doubly Linked List?
A doubly linked list is a data structure in which each element, known as a “node,” contains two pointers: one that points to the next node and another that points to the previous node. This bidirectional linkage allows for traversing the list in both forward and backward directions, making it an attractive option for certain applications.
Structure of a Node
To comprehend a doubly linked list, let’s examine the structure of a node:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
Here, data represents the actual value of the node, next points to the next node in the list, and prev points to the previous node. The prev pointer of the first node and the next pointer of the last node are typically set to None.
Advantages of Doubly Linked Lists
- Bidirectional Traversal: Unlike singly linked lists, which only allow forward traversal, doubly linked lists enable efficient backward traversal as well. This feature is especially useful in scenarios where accessing elements in both directions is necessary.
- Insertion and Deletion: Adding or removing elements from a doubly linked list is more efficient compared to singly linked lists. In certain situations, this can be a crucial advantage.
- Reverse Iteration: With the backward pointers, reversing a doubly linked list becomes relatively straightforward. This can be beneficial in various algorithms and programming tasks.
Operations on Doubly Linked Lists
- Insertion: Inserting a new node into a doubly linked list involves adjusting the pointers of neighboring nodes to accommodate the new element.
- Deletion: Removing a node requires updating the pointers of the adjacent nodes to bridge the gap left by the deleted node.
- Traversal: Doubly linked lists can be traversed in both forward and backward directions, allowing easy access to elements from either end.
- Reversal: Reversing a doubly linked list can be done by swapping the
nextandprevpointers of each node.
Use Cases
- Browser History: Doubly linked lists can efficiently store the browser history, enabling users to navigate forward and backward through visited pages.
- Text Editors: Text editors often use doubly linked lists to manage the undo and redo functionality, allowing users to traverse through the editing history in both directions.
- Cache Management: Doubly linked lists are employed in cache management systems to prioritize recently accessed items and efficiently evict least recently used ones.
Code
class Node:
def __init__(self, data):
self.data = data
self.previous = None
self.next = None
def __str__(self):
return f"{self.data}"
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def __iter__(self):
node = self.head
while node:
yield node.data
node = node.next
def __str__(self):
return "->".join([str(item) for item in self])
def __len__(self):
return sum(1 for _ in self)
def insert_at_head(self, data):
self.insert_at_nth(0, data)
def insert_at_tail(self, data):
self.insert_at_nth(len(self), data)
def insert_at_nth(self, index: int, data):
length = len(self)
if not 0 <= index <= length:
raise IndexError("list index out of range")
new_node = Node(data)
if self.head is None:
self.head = self.tail = new_node
elif index == 0:
self.head.previous = new_node
new_node.next = self.head
self.head = new_node
elif index == length:
self.tail.next = new_node
new_node.previous = self.tail
self.tail = new_node
else:
temp = self.head
for _ in range(0, index):
temp = temp.next
temp.previous.next = new_node
new_node.previous = temp.previous
new_node.next = temp
temp.previous = new_node
def delete_head(self):
return self.delete_at_nth(0)
def delete_tail(self):
return self.delete_at_nth(len(self) - 1)
def delete_at_nth(self, index: int):
length = len(self)
if not 0 <= index <= length - 1:
raise IndexError("list index out of range")
delete_node = self.head # default first node
if length == 1:
self.head = self.tail = None
elif index == 0:
self.head = self.head.next
self.head.previous = None
elif index == length - 1:
delete_node = self.tail
self.tail = self.tail.previous
self.tail.next = None
else:
temp = self.head
for _ in range(0, index):
temp = temp.next
delete_node = temp
temp.next.previous = temp.previous
temp.previous.next = temp.next
return delete_node.data
def delete(self, data) -> str:
current = self.head
while current.data != data:
if current.next:
current = current.next
else:
raise ValueError("No data matching given value")
if current == self.head:
self.delete_head()
elif current == self.tail:
self.delete_tail()
else:
current.previous.next = current.next
current.next.previous = current.previous
return data
def is_empty(self):
return len(self) == 0
if __name__ == "__main__":
linked_list = DoublyLinkedList()
linked_list.insert_at_head(0)
linked_list.insert_at_tail(11)
linked_list.delete_tail()
Conclusion
Doubly linked lists are a versatile data structure that strikes a balance between the simplicity of singly linked lists and the enhanced functionality of more complex data structures. Their ability to traverse bidirectionally, efficient insertion and deletion operations, and usefulness in specific applications make them an invaluable tool for programmers and computer scientists.
