Hoe wordt de tijdcomplexiteit van de bewerking van het invoegen van een element in een dubbel gekoppelde lijst bepaald?

De tijdscomplexiteit van de operatie om een element in een dubbel gekoppelde lijst in te voegen, hangt af van of we een pointer naar de invoegpositie hebben:

• Als er al een pointer is naar de knoop waarna het element moet worden ingevoegd, wordt de invoeging in O(1) uitgevoerd, omdat slechts enkele pointers hoeven te worden gewijzigd.
• Als eerst de invoegpositie moet worden gevonden, hangt de zoektijd af van de grootte van de lijst (O(n)), en de daadwerkelijke invoeging is O(1).

Voorbeeld van invoegen na een gegeven knoop:

 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
}