Quelle est la complexité temporelle de l'ajout d'un nouvel élément à la fin d'une liste chaînée simple?

La complexité temporelle de l’ajout d’un nouvel élément à la fin d’une liste chaînée simple dépend de la présence d’un pointeur vers le dernier élément (queue).

• Si le pointeur vers la queue existe, l’ajout se fait en O(1), car on peut accéder directement au dernier élément et y ajouter un nouveau.
• S’il n’y a pas de pointeur, il faut parcourir toute la liste de la tête à la fin, ce qui prend O(n) temps, où n est le nombre d’éléments dans la liste.

Exemple avec un pointeur vers la queue :

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
    }
}

Ici, l’ajout se fait en temps constant O(1).