Kaip nustatoma įdėjimo į dvipusį sąrašą operacijos laiko sudėtingumas?

Dvigubai susietos sąrašo elemento įterpimo operacijos laiko sudėtingumas priklauso nuo to, ar turime nuorodą į įterpimo vietą:

• Jei jau turime nuorodą į mazgą, po kurio reikia įterpti elementą, įterpimas atliekamas per O(1), nes pakanka pakeisti keletą nuorodų.
• Jei pirmiausia reikia rasti įterpimo vietą, paieškos laikas priklausys nuo sąrašo dydžio (O(n)), o pats įterpimas — O(1).

Pavyzdys, kaip įterpti po nurodyto mazgo:

 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
}