Quelle est l'estimation de la complexité temporelle de l'opération de suppression d'un élément dans une liste simplement chaînée?

La complexité temporelle de la suppression d'un élément dans une liste chaînée simple dépend de si nous avons un pointeur sur l'élément à supprimer ou seulement sur la tête de la liste.

• Si vous devez supprimer un élément en ne connaissant que la tête de la liste, il faut d'abord parcourir la liste pour trouver l'élément et son nœud précédent. Cela prend O(n) en temps, où n est le nombre d'éléments dans la liste.
• Si nous avons un pointeur sur l'élément précédent (ou sur l'élément à supprimer lui-même, si c'est le premier), la suppression se fait en O(1), car il suffit de reconfigurer les liens.

Ainsi, en général, la suppression d'un élément dans une liste chaînée simple est une opération avec une complexité temporelle de O(n).