Double Linked List

Doubly Linked Lists: A Powerful Data Structure

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?

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 next and prev pointers 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.

Leave a Comment

Your email address will not be published. Required fields are marked *