Como é determinada a complexidade temporal da operação de inserção de um elemento numa lista duplamente ligada?

A complexidade temporal da operação de inserção de um elemento numa lista duplamente ligada depende de termos um ponteiro para a posição de inserção:

• Se já existe um ponteiro para o nó após o qual se deve inserir, a inserção é feita em O(1), pois basta alterar alguns ponteiros.
• Se for necessário encontrar primeiro a posição de inserção, o tempo de busca dependerá do tamanho da lista (O(n)), e a própria inserção será O(1).

Exemplo de inserção após um nó dado:

 type Node struct {
    value int
    prev  *Node
    next  *Node
}

func insertAfter(node *Node, newNode *Node) {
    newNode.prev = node
    newNode.next = node.next
    if node.next != nil {
        node.next.prev = newNode
    }
    node.next = newNode
}