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

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

• Поиск нужной позиции в среднем случае занимает O(n), так как нужно пройти примерно половину списка.
• Самая операция вставки (изменение ссылок предыдущего и следующего узлов) выполняется за O(1).

Итого, время выполнения вставки в среднюю часть двусвязного списка — O(n) из-за необходимости поиска позиции.

Пример на Java:

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

// Вставка после узла prevNode
void insertAfter(Node prevNode, int newData) {
    if (prevNode == null) return;
    Node newNode = new Node(newData);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;
    if (newNode.next != null) newNode.next.prev = newNode;
}