Jak określa się złożoność czasową operacji wstawiania elementu do listy dwukierunkowej?

Złożoność czasowa operacji wstawiania elementu do listy dwukierunkowej zależy od tego, czy mamy wskaźnik na pozycję wstawienia:

• Jeśli wskaźnik na węzeł, po którym trzeba wstawić element, już istnieje, to wstawienie wykonuje się w czasie O(1), ponieważ wystarczy zmienić kilka wskaźników.
• Jeśli najpierw trzeba znaleźć pozycję wstawienia, czas wyszukiwania będzie zależał od rozmiaru listy (O(n)), a samo wstawienie — O(1).

Przykład wstawiania po zadanym węźle:

 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
}