Comment déterminer la complexité temporelle de la suppression d'un élément situé au milieu d'une liste chaînée?

La complexité temporelle de la suppression d'un élément du milieu d'une liste chaînée dépend de si vous avez un accès direct à cet élément et à son nœud précédent.

• Si vous avez un pointeur vers l'élément lui-même et vers le nœud précédent (par exemple, dans une liste doublement chaînée), la suppression se fait en O(1), car il suffit de reconfigurer les liens.
• Si vous avez seulement la valeur ou un pointeur vers l'élément sans accès au précédent, il faut d'abord parcourir la liste depuis le début jusqu'à cet élément, ce qui prend O(n), où n est le nombre d'éléments avant celui à supprimer.

Ainsi, en général, la suppression du milieu d'une liste chaînée est considérée comme une opération avec une complexité temporelle de O(n) si vous n'avez pas d'accès direct au nœud précédent.