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

La complexité temporelle de l'opération d'ajout d'un élément à la fin d'une liste chaînée dépend de la présence d'un pointeur vers le dernier élément.

• S'il y a un pointeur vers la queue (tail), l'ajout se fait en O(1), car on peut ajouter immédiatement un nouvel élément après la queue.
• S'il n'y a pas de pointeur vers la queue, il faut parcourir toute la liste pour trouver le dernier élément, et la complexité sera alors O(n), où n est le nombre d'éléments dans la liste.

Exemple avec un pointeur vers la queue:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}