Hogyan határozzuk meg a művelet időbeli összetettségét egy kétszeresen láncolt lista elemének beszúrásakor?

A kétirányú láncolt lista egy elemének beszúrási műveletének időkomplexitása attól függ, hogy van-e mutató a beszúrás helyére:

• Ha már van mutató a csomópontra, amely után a elemet be kell szúrni, akkor a beszúrás O(1), mivel csak néhány mutatót kell módosítani.
• Ha először meg kell találni a beszúrás helyét, akkor a keresési idő a lista méretétől függ (O(n)), míg maga a beszúrás O(1).

Példa a megadott csomópont utáni beszúrásra:

 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
}