Quelle est la mesure de complexité de l'algorithme pour ajouter un élément au début d'une liste doublement chaînée?

L'ajout d'un élément au début d'une liste doublement chaînée s'effectue en temps constant, c'est-à-dire avec une complexité O(1).

Cela est dû au fait qu'une liste doublement chaînée possède un pointeur vers le premier élément (tête), et pour insérer un nouvel élément, il suffit de:

1. Créer un nouveau nœud.
2. Définir son pointeur next sur l'élément actuel en tête.
3. Définir le pointeur prev de l'élément actuel en tête sur le nouveau nœud.
4. Mettre à jour le pointeur de la tête de la liste vers le nouveau nœud.

Toutes ces opérations ne dépendent pas de la taille de la liste, donc la complexité est — O(1).