Как се определя времевата сложност на операцията по вмъкване на елемент в двусвързан списък?

Времевата сложност на операцията за вмъкване на елемент в двусвързания списък зависи от това дали имаме указател към позицията за вмъкване:

• Ако вече имаме указател към възела, след който трябва да се вмъкне елемент, вмъкването се извършва за O(1), тъй като е достатъчно да се променят няколко указателя.
• Ако трябва първо да намерим позицията за вмъкване, времето за търсене ще зависи от размера на списъка (O(n)), а самото вмъкване — O(1).

Пример за вмъкване след даден възел:

 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
}