Suppressions de valeurs

La structure de donnée utilisée ici est la liste. On considérera que :

• la création d'une liste vide se fait en $\mathcal{O}(1)$ opérations,
• l'ajout d'un élément en fin de liste se fait en $\mathcal{O}(1)$ opérations,
• lire un élément d'une liste se fait en $\mathcal{O}(1)$ opérations.

Suppression d'une valeur

Écrire un algorithme permettant de résoudre le problème suivant :

• Données : Une liste L et une valeur val.
• Rendre : Une liste L_2, restriction de L aux valeurs différentes de val.

Quel est sa complexité ?

Suppression d'une valeur in-place

Écrire un algorithme permettant de supprimer une valeur d'une liste :

1. sans créer de liste annexe
2. de façon optimale

Pour cet exercice, on ne se préoccupe pas de l'ordre des éléments dans la liste.