Wie ist die zeitliche Komplexität beim Hinzufügen eines neuen Elements am Ende einer einfach verketteten Liste?

Die zeitliche Komplexität beim Hinzufügen eines neuen Elements am Ende einer einfach verketteten Liste hängt davon ab, ob die Liste einen Zeiger auf das letzte Element (Schwanz) hat.

• Wenn ein Zeiger auf den Schwanz vorhanden ist, erfolgt das Hinzufügen in O(1), da direkt auf das letzte Element zugegriffen und ein neues hinzugefügt werden kann.
• Wenn kein Zeiger vorhanden ist, muss die gesamte Liste vom Kopf bis zum Ende durchlaufen werden, was O(n) Zeit in Anspruch nimmt, wobei n die Anzahl der Elemente in der Liste ist.

Beispiel mit Zeiger auf den Schwanz:

class Node {
    var value: Int
    var next: Node?
    init(value: Int) {
        self.value = value
    }
}

class LinkedList {
    var head: Node?
    var tail: Node?

    func append(_ value: Int) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
}

Hier erfolgt das Hinzufügen in konstanter Zeit O(1).