Doubly Linked List

What is a Doubly Linked List?

Unlike singly linked lists, a doubly linked list (DLL) contains nodes with two pointers:

1. Next Pointer: Points to the next node.
2. Previous Pointer: Points to the previous node.

This bidirectional structure allows for more flexible operations, like traversing in both directions and efficiently deleting nodes from the middle of the list.

Advantages of Doubly Linked Lists

• Bidirectional traversal: You can move forward or backward through the list.
• Easier deletion: Since nodes have a pointer to their predecessor, deleting nodes in the middle is more straightforward.

However, DLLs require more memory due to the additional pointer.

Common Operations

• Insertion: Add nodes at the beginning O(1), end O(1), or a specific position O(n).
• Deletion: Remove nodes using both next and previous pointers.
• Traversal: Move forward or backward through the list. O(n)

Code Examples

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, value):
        new_node = Node(value)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, "->", end=" ")
            current = current.next
        print("NULL")

dll = DoublyLinkedList()
dll.insert_at_head(10)
dll.insert_at_head(20)
dll.insert_at_head(30)
dll.print_list()

Problems to Solve

Important Problems on Linked Lists

Resources

• Doubly Linked Lists (Grokking Data Structures)