¿Cómo se determina la complejidad temporal de la operación de insertar un elemento en una lista doblemente enlazada?

La complejidad temporal de la operación de inserción de un elemento en una lista doblemente enlazada depende de si tenemos un puntero a la posición de inserción:

• Si ya hay un puntero al nodo después del cual se debe insertar el elemento, la inserción se realiza en O(1), ya que basta con cambiar algunos punteros.
• Si primero hay que encontrar la posición de inserción, el tiempo de búsqueda dependerá del tamaño de la lista (O(n)), y la inserción en sí será O(1).

Ejemplo de inserción después de un nodo 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
}