Come si determina la complessità temporale dell'operazione di inserimento di un elemento in una lista doppiamente collegata?

La complessità temporale dell'operazione di inserimento di un elemento in una lista doppiamente collegata dipende dal fatto che abbiamo o meno un puntatore alla posizione di inserimento:

• Se abbiamo già un puntatore al nodo dopo il quale inserire, l'inserimento avviene in O(1), poiché basta modificare alcuni puntatori.
• Se dobbiamo prima trovare la posizione di inserimento, il tempo di ricerca dipenderà dalla dimensione della lista (O(n)), e l'inserimento stesso sarà O(1).

Esempio di inserimento dopo un nodo dato:

 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
}