Какое время требуется для добавления нового узла в среднюю часть двусвязного списка?

Время добавления нового узла в среднюю часть двусвязного списка зависит от того, есть ли у вас прямой доступ к узлу, после которого нужно вставить новый элемент.

• Если узел уже найден (у вас есть ссылка на него), то вставка происходит за O(1), так как нужно просто перенастроить несколько указателей.
• Если же нужно сначала найти позицию вставки, то поиск узла занимает O(n), где n — количество элементов до нужного узла.

Пример вставки после заданного узла:

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;
}

Таким образом, основное время уходит на поиск позиции, а сама вставка — константная по времени.