Comment détermine-t-on la complexité temporelle de l'opération d'insertion d'un élément dans une liste doublement chaînée?

La complexité temporelle de l'opération d'insertion d'un élément dans une liste doublement chaînée dépend de si nous avons un pointeur vers la position d'insertion:

• Si un pointeur vers le nœud après lequel insérer existe déjà, l'insertion se fait en O(1), car il suffit de modifier quelques pointeurs.
• Si nous devons d'abord trouver la position d'insertion, le temps de recherche dépendra de la taille de la liste (O(n)), et l'insertion elle-même sera O(1).

Exemple d'insertion après un nœud donné:

 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
}