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

La complexité temporelle de l'ajout d'un élément à la fin d'une liste doublement chaînée dépend du fait que la liste possède ou non un pointeur vers le dernier élément (queue).

• S'il y a un pointeur vers la queue, l'ajout d'un élément à la fin se fait en O(1), car on peut accéder directement au dernier élément et y ajouter le nouveau.

• S'il n'y a pas de pointeur vers la queue, il faut parcourir toute la liste de la tête au dernier élément, ce qui prend O(n) temps, où n est le nombre d'éléments dans la liste.

Dans la plupart des implémentations de listes doublement chaînées, pour optimiser les opérations d'ajout à la fin, on maintient un pointeur vers la queue, donc l'opération est généralement considérée comme O(1).