Cum se determină complexitatea temporală a operației de inserare a unui element într-o listă dublu înlănțuită?

Complexitatea temporală a operației de inserare a unui element într-o listă dublu înlănțuită depinde de faptul dacă avem sau nu un pointer către poziția de inserare:

• Dacă deja există un pointer către nodul după care trebuie să inserăm, inserarea se face în O(1), deoarece trebuie doar să schimbăm câțiva pointeri.
• Dacă trebuie mai întâi să găsim poziția de inserare, timpul de căutare va depinde de dimensiunea listei (O(n)), iar inserarea în sine va fi O(1).

Exemplu de inserare după un nod dat:

 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
}