Qual é a métrica de tempo para a operação de inserção de um elemento na parte central de uma lista duplamente ligada?

Inserir um elemento na parte central de uma lista duplamente ligada geralmente requer primeiro encontrar a posição de inserção, o que leva O(n) tempo, pois é necessário percorrer a lista até o nó desejado.

O próprio processo de inserção (alterar os ponteiros dos nós vizinhos) é realizado em O(1).

Resumindo:

• Pesquisa da posição — O(n)
• Inserção — O(1)

Se a posição já é conhecida (por exemplo, se você tem um ponteiro para um nó), a inserção será O(1). Caso contrário, é necessário percorrer a lista primeiro, o que dá O(n).