Doubly Linked List

A Doubly Linked List is a type of linked list in which each node contains a reference to both the next and the previous node, allowing traversal in both directions.

Basic Structure

• Each node has three parts: data, next pointer, and previous (prev) pointer.
• The first node's previous pointer points to NULL.
• The last node's next pointer points to NULL.
• Nodes are connected bidirectionally.

Advantages Over Singly Linked List

• Can traverse forward and backward through the list.
• Easier to delete a node as access to the previous node is available.

Basic Operations

• Insertion: At beginning, end, or after a specified node.
• Deletion: Removing a node given its reference or position.
• Traversal: Moving through nodes forwards or backwards.

Example Implementation in Python

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

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

    def insert_front(self, data):
        new_node = Node(data)
        new_node.next = self.head
        new_node.prev = None
        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("None")

# Usage
dll = DoublyLinkedList()
dll.insert_front(10)
dll.insert_front(20)
dll.insert_front(30)
dll.print_list()  # Output: 30 <-> 20 <-> 10 <-> None

Ye example doubly linked list ko head par insertion aur traversing ke sath demonstrate karta hai.