Qual é o tempo de execução para inserir um elemento na parte média de uma lista duplamente ligada?

A inserção de um elemento na parte média de uma lista duplamente ligada requer primeiro encontrar a posição de inserção e depois alterar os links dos nós.

• A busca pela posição necessária no pior caso leva O(n), pois é preciso percorrer aproximadamente metade da lista.
• A operação de inserção em si (alterar os links do nó anterior e do próximo) é realizada em O(1).

No total, o tempo de execução da inserção na parte média de uma lista duplamente ligada é O(n) devido à necessidade de procurar a posição.

Exemplo em Java:

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

// Inserir após o nó 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;
}