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

Временная сложность операции вставки элемента в двусвязный список зависит от того, есть ли у нас указатель на позицию вставки:

• Если указатель на узел, после которого нужно вставить элемент, уже есть, то вставка выполняется за 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
}