Insert a Node at a Specific Position in a Doubly Linked List

Inserting a Node at a Specific Position

Inserting a node at a specific position in a doubly linked list involves traversing the list to find the desired position and updating the next and previous references of the surrounding nodes to include the new node. This operation requires careful manipulation of pointers to maintain the integrity of the list.

---

Step-by-Step Process

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

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

We want to insert a new node with the value 3 at the 3rd position (0-based index). Follow these steps:

1. Create a New Node: Create a new node with the desired value (3).
2. Traverse to the Node Before the Desired Position: Start at the head and follow the next references until you reach the node before the desired position (node with value 2).
3. Set the New Node's Next Reference: Update the next reference of the new node to point to the node currently at the desired position (node with value 4).
4. Update the Previous Reference of the Node at the Desired Position: Update the previous reference of the node at the desired position to point to the new node.
5. Update the Next Reference of the Node Before the Desired Position: Set the next reference of the node before the desired position to point to the new node.
6. Set the Previous Reference of the New Node: Set the previous reference of the new node to point to the node before the desired position.

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

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

---

Python Program to Insert a Node at a Specific Position

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_position(self, position, data):
        new_node = Node(data)
        if position == 0:
            if self.head is None:
                self.head = new_node
            else:
                new_node.next = self.head
                self.head.prev = new_node
                self.head = new_node
            return
        current = self.head
        for _ in range(position - 1):
            if current is None:
                raise IndexError("Position out of bounds")
            current = current.next
        new_node.next = current.next
        if current.next is not None:
            current.next.prev = new_node
        current.next = new_node
        new_node.prev = current

    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(4)
dll.append(5)
print("Doubly linked list before insertion at position 2:")
dll.traverse()  # Output: 1 <-> 2 <-> 4 <-> 5 <-> None

dll.insert_at_position(2, 3)
print("Doubly linked list after insertion at position 2:")
dll.traverse()  # Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None

This Python program defines a doubly linked list with methods for appending nodes, inserting a node at a specific position, and traversing the list. The insert_at_position method creates a new node, traverses to the node before the desired position, and updates the next and previous references to include the new node.