Insert a Node at the Beginning of a Doubly Linked List

Inserting a Node at the Beginning

Inserting a node at the beginning of a doubly linked list involves creating a new node and updating the head reference to point to this new node, as well as updating the previous reference of the old head node to point to the new node. This operation is efficient as it only requires updating a few pointers.

---

Step-by-Step Process

Consider a doubly linked list with the following structure before insertion:

Head <-> 1 <-> 2 <-> 3 <-> 4 <-> None

We want to insert a new node with the value 0 at the beginning. Follow these steps:

1. Create a New Node: Create a new node with the desired value (0).
2. Set the New Node's Next Reference: Update the next reference of the new node to point to the current head of the list.
3. Update the Previous Reference of the Current Head: If the list is not empty, update the previous reference of the current head to point to the new node.
4. Update the Head Reference: Update the head reference to point to the new node.
5. Set the Previous Reference of the New Node: Set the previous reference of the new node to None, since it is now the first node in the list.

After performing these steps, the linked list will have the following structure:

Head <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None

---

Python Program to Insert a Node at the Beginning

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def insert_at_beginning(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
print("Doubly linked list before insertion at beginning:")
dll.traverse()  # Output: 1 <-> 2 <-> 3 <-> 4 <-> None

dll.insert_at_beginning(0)
print("Doubly linked list after insertion at beginning:")
dll.traverse()  # Output: 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None

This Python program defines a doubly linked list with methods for appending nodes, inserting a node at the beginning, and traversing the list. The insert_at_beginning method creates a new node, sets its next reference to the current head, updates the previous reference of the current head, and updates the head reference to the new node.