Insert a Node in the Middle of a Doubly Linked List

Inserting a Node in the Middle

Inserting a node in the middle of a doubly linked list involves finding the middle of the list, traversing to that 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 in the middle of the list. Follow these steps:

1. Find the Middle Position: Use the slow and fast pointer technique to find the middle of the list.
2. Create a New Node: Create a new node with the desired value (3).
3. Set the New Node's Next Reference: Update the next reference of the new node to point to the node currently at the middle position (node with value 4).
4. Update the Previous Reference of the Node at the Middle Position: Update the previous reference of the node at the middle position to point to the new node.
5. Update the Next Reference of the Node Before the Middle Position: Set the next reference of the node before the middle 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 middle 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 in the Middle

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_middle(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        slow = self.head
        fast = self.head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        new_node.next = slow.next
        if slow.next is not None:
            slow.next.prev = new_node
        slow.next = new_node
        new_node.prev = slow

    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 in the middle:")
dll.traverse()  # Output: 1 <-> 2 <-> 4 <-> 5 <-> None

dll.insert_at_middle(3)
print("Doubly linked list after insertion in the middle:")
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 in the middle, and traversing the list. The insert_at_middle method uses the slow and fast pointer technique to find the middle of the list, creates a new node, and updates the next and previous references to include the new node.