Wie wird die zeitliche Komplexität der Operation zum Einfügen eines Elements in eine doppelt verkettete Liste bestimmt?

Die zeitliche Komplexität der Operation zum Einfügen eines Elements in eine doppelt verkettete Liste hängt davon ab, ob wir einen Zeiger auf die Einfügeposition haben:

• Wenn bereits ein Zeiger auf den Knoten vorhanden ist, nach dem das Element eingefügt werden soll, erfolgt die Einfügung in O(1), da nur einige Zeiger geändert werden müssen.
• Wenn die Einfügeposition zuerst gefunden werden muss, hängt die Suchzeit von der Größe der Liste ab (O(n)), und die eigentliche Einfügung ist O(1).

Beispiel für das Einfügen nach einem gegebenen Knoten:

 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
}