Aller au contenu

Opérations sur les listes chaînées

Initialiser une liste vide

Une liste « vide » ne pointe vers rien :

Liste chaînée

Complexité

Cette opération se réalise en temps constant, c'est-à-dire en O(1).

Insérer en tête de liste chaînée

  1. On crée la liste L : Liste chaînée

  2. On crée un maillon qui pointe vers le lien de L : Liste chaînée

  3. On fait pointer le lien de L vers le maillon : Liste chaînée

  4. On recommence. On crée un maillon qui pointe vers le lien de L : Liste chaînée

  5. On fait pointer le lien de L vers le maillon : Liste chaînée

  6. etc...

Complexité

Pour chaque insertion en tête de liste, la complexité en temps est constante, c'est-à-dire en O(1).

Parcourir les éléments d'une liste chaînée

On considère une liste L : Liste chaînée

Pour parcourir les éléments (maillons) de cette liste :

  1. On crée une variable temp qui pointe vers le le lien de L, c'est-à-dire vers le premier maillon : Liste chaînée

  2. On utilise le lien de chaque maillon pour que temp pointe vers le maillon suivant : Liste chaînée

  3. On s'arrête lorsque le lien du maillon pointe vers None (on est au dernier maillon) ou bien lorsqu'on est à la position désirée (on peut utiliser pour cela une variable « indice » pour chaque maillon) : Liste chaînée

Complexité

Dans le pire des cas, il faut parcourir les n maillons de la liste donc la complexité en temps est linéaire, c'est-à-dire en O(n).

Insérer un élément en n'importe quelle position

  1. On reprend le parcours précédent pour « s'arrêter » au maillon après lequel on souhaite insérer : Liste chaînée

  2. On crée un maillon à insérer dont le lien pointe vers le lien du maillon sur lequel on s'est arrêté : Liste chaînée

  3. On redéfinit le lien du maillon sur lequel on s'est arrêté pour qu'il pointe vers le nouveau maillon : Liste chaînée

  4. On obtient la liste : Liste chaînée

Complexité

Une fois en « bonne » position, la complexité de l'insertion est constante en O(1).
Par contre, pour se rendre à la bonne position, le coût est linéaire (cf. le paragraphe sur le parcours des éléments).

Supprimer un élément

  1. On reprend le parcours pour se placer au maillon situé avant celui à supprimer : Liste chaînée

  2. On pointe ensuite le maillon à supprimer et on mémorise (si besoin) la valeur qu'il contient : Liste chaînée

  3. On redéfinit le lien du maillon sur lequel on s'est arrêté pour qu'il pointe vers le lien du maillon à supprimer : Liste chaînée

  4. On obtient la liste : Liste chaînée

Complexité

Une fois en « bonne » position, la complexité la suppression est constante en O(1).
Par contre, pour se rendre à la bonne position, le coût est linéaire (cf. le paragraphe sur le parcours des éléments).