Jak se určuje časová složitost operace vložení prvku do oboustranně spojovaného seznamu?

Časová složitost operace vložení prvku do obousměrně spojovaného seznamu závisí na tom, zda máme ukazatel na pozici vložení:

• Pokud již máme ukazatel na uzel, za kterým je třeba vložit prvek, je vložení provedeno v O(1), protože stačí změnit několik ukazatelů.
• Pokud je třeba nejdříve najít pozici vložení, doba hledání závisí na velikosti seznamu (O(n)), a samotné vložení je O(1).

Příklad vložení za daný uzel:

 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
}