How much time is required to add a new node to the middle part of a doubly linked list?

The time to add a new node to the middle of a doubly linked list depends on whether you have direct access to the node after which you want to insert the new element.

• If the node is already found (you have a reference to it), then the insertion occurs in O(1) time, as it only requires reassigning a few pointers.
• If you need to first find the insertion position, then searching for the node takes O(n), where n is the number of elements before the desired node.

Example of inserting after a given node:

class Node {
    int data;
    Node prev, next;
    Node(int data) { this.data = data; }
}

void insertAfter(Node node, int newData) {
    if (node == null) return;
    Node newNode = new Node(newData);
    newNode.next = node.next;
    newNode.prev = node;
    if (node.next != null) {
        node.next.prev = newNode;
    }
    node.next = newNode;
}

Thus, the main time is spent on finding the position, while the insertion itself is constant time.