Listes Chaînées, présentation
Tableaux
- Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
- Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
| Type Python | Type | Opération | Exemple | Complexité |
|---|---|---|---|---|
| N’existe pas | Tableau | Accès à un élément | tab[i] |
|
| Modification d’un élément | tab[i] = x |
|||
| Effacement d’un élément | retire(tab, i) |
|||
| Insertion d’un élément | insere(tab, x, i) |
|||
| Recherche d’un élément | est_dans(tab, x) |
- La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.
Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.
Pourquoi la recherche d’un élément dans un tableau quelconque (non trié donc) est en ?
- Écrire le prédicat
est_dansde spécification :
-
Écrire un jeu de tests.
-
(Facultatif) Écrire le prédicat
est_dans_recde spécification :
- Quelle est la complexité des algorithmes précédents en fonction de , la taille du tableau ?
Pourquoi l’insertion d’un élément dans un tableau est en ?
Dans cette partie, on imagine que le tableau a cette allure :
| 1 | 1 | 2 | 3 | 4 | 5 | vide | vide | vide |
|---|
Si on introduit, en position 1, la valeur 7. Le tableau est alors :
| 7 | 1 | 1 | 2 | 3 | 4 | 5 | vide | vide |
|---|
Cette opération n’est possible, sans crainte de perdre des données, que si toutes les cellules du tableau ne contiennent pas des données. Toute fonction permettant l’insertion de valeurs doit donc avertir un utilisateur dans le cas contraire.
Remarque : Dans le code ci-dessous, les cellules seront considérées vides si elles contiennent la valeur None.
- Écrire la fonction
inseredont la spécification est :
- (Facultatif) Écrire la fonction
insere_recdont la spécification est :
- Quelle est la complexité des algorithmes précédents en fonction de , la taille du tableau ?
Structure de liste chaînée
Les listes chaînées constituent une structure de données :
- de longueur modifiable ;
- plus efficace que les tableaux lorsqu’il s’agit d’ajouter ou de retirer un élément (il n’est pas nécessaire de faire de la place en déplaçant les éléments) ;
- qui servira de brique à l’élaboration d’autres structures de données.
Une liste chaînée permet de représenter une liste ; chaque élément de cette liste est une cellule contenant :
- la valeur de l’élément à stocker ;
- l’adresse mémoire de la cellule représentant l’élément suivant.
Remarque : le symbole marque la fin de la liste dans les schémas.
Comment implémenter une cellule ?
En langage Python, on peut implémenter une cellule à l’aide d’une classe, de listes ou de tuples.
- Définir la classe
Celluledont la spécification est :
La dernière cellule d’une liste chaînée devra pointer vers l’objet None qui représente donc une cellule vide.
-
Instancier 3 objets
c1,c2,c3, de typeCellule, dont les valeurs sont 1, 2, 3. Tous ces objets sont pour l’instant isolés (ils ne pointent vers aucune autre cellule si ce n’est la cellule videNone). -
Créer la liste
lstà l’aide de ces trois objets. -
Comment aurait-on pu créer la liste
lsten une seule instruction ?
Les listes chaînées sont des structures fondamentalement récursives
Une liste chaînée est :
- soit la liste vide (objet
None) ; - soit constituée de son premier élément (objet de type
Cellule) et du reste des éléments qui forment aussi une liste. Une liste chaînée est donc une structure récursive.
Une liste chaînée est-elle forcément homogène
Tout au long de ce document nous allons uniquement envisager des listes chaînées de nombres entiers. Rien n’impose, cependant, à l’attribut valeur de la classe Cellule d’être un entier. Chaque cellule peut même posséder des attributs valeur de type différent. Les listes chaînées peuvent donc être hétérogènes.
Quelques opérations sur les listes chaînées
Le point de vue envisagé dans la suite de ce document est celui de la programmation impérative : nous allons définir des fonctions qui vont modifier la liste chaînée.
Nous créerons une classe enveloppe dans un prochain document, de façon à ce notre liste chaînée ait la même interface qu’une liste Python.
Longueur d’une liste chaînée
- Écrire la fonction
longueurdont la spécification est :
- Écrire la fonction
longueur_iterdont la spécification est :
- Déterminer la complexité du calcul de la longueur d’une liste.
Affichage de tous les éléments d’une liste
- Écrire la fonction
affichage_elements_listedont la spécification est :
- Définir la fonction
list_to_strdont la spécification est :
Valeur du n-ième élément d’une liste
- Écrire la fonction
n_ieme_elementdont la spécification est :
- Écrire la fonction
n_ieme_element_iterdont la spécification est :
- Déterminer la complexité de la recherche du n-ième élément d’une liste.
Modification de la valeur d’une cellule sans modifier la structure de la liste
- Écrire la fonction
modifier_n_ieme_elementdont la spécification est :
Ajout d’une valeur à la fin de la liste
- Écrire la fonction
ajout_fin_listedont la spécification est :
- Quelle est la complexité de la fonction
ajout_fin_liste?
Ajout d’une valeur au début de la liste
- Écrire la fonction
ajout_debut_listedont la spécification est :
- Quelle est la complexité de cette fonction ?
Retrait du dernier élément d’une liste
- Écrire la fonction
retrait_dernier_elementdont la spécification est :
- Quelle est la complexité de cette fonction ?
Retrait du premier élément d’une liste
- Écrire la fonction
retrait_premier_elementdont la spécification est :
- Quelle est la complexité de cette fonction ?
Retrait du n-ième élément d’une liste
- Écrire la fonction
retrait_n_ieme_elementdont la spécification est :
- Quelle est la complexité de cette fonction ?
Concaténation de deux listes
On appelle concaténation de deux listes l’opération consistant à mettre bout à bout les deux listes.
- Écrire la fonction
concatenerdont la spécification est :
- Écrire la fonction
copiedont la spécification est :
- Se servir de la fonction
copiepour écrire la fonctionconcatener_avec_copie_integraledont la spécification est :
- Quelle est la complexité de la fonction
concatener? Même question pour la fonctionconcatener_avec_copie_integrale.
Renverser une liste
- Écrire la fonction
renverserdont la spécification est :
Remarque. Cette fonction doit s’appuyer sur les fonctions concatener ou concatener_avec_copie_integrale.
Remarque. Cet algorithme est particulièrement inefficace.
Conclusion
- Une liste chaînée est une structure de données utile pour représenter une séquence finie d’éléments.
- Chaque élément est contenu dans une cellule, qui fournit, en plus de la valeur, un moyen pour accéder à la cellule suivante.
- Les éléments d’une liste chaînée ne sont pas situés dans des emplacements contigüs en mémoire.
- Les opérations sur les listes chaînées se programment sous la forme de parcours qui suivent ces liaisons, en utilisant la récursivité ou des boucles.
Une liste chaînée est un type abstrait de données qui doit, au minimum, fournir les fonctions suivantes :
insère: insère un élément dans la liste ;supprime: supprime et renvoie l’élément de position spécifié de la liste ;longueur: renvoie le nombre d’éléments de la liste ;est_vide: détermine si la liste est vide ou pas ;nième_élément: retourne la valeur du nième élément depuis le début.
| Action | Liste chaînée | Tableau | Tableau dynamique |
|---|---|---|---|
| Accès à un élément | |||
| Insertion/suppression du 1er élément | (si place) | ||
| Insertion à la fin | (si place) | (si place) (si pas de place) |
|
| Suppression du dernier élément | |||
| Insertion/suppression au milieu | (si place) |
Quelques exemples d’utilisation des listes chaînées
-
Les logiciels de visualisation d’images utilisent parfois une liste chaînée pour afficher les images précédentes et suivantes à l’aide des boutons « précédent » et « suivant ».
-
Des navigateurs Web peuvent utiliser une liste chaînée pour accéder aux pages à l’aide des boutons « précédent » et « suivant ».
-
Les boutons « précédent » et « suivant » des lecteurs de musique peuvent utiliser une liste chaînée doublement/circulaire.
-
Les tracés et les formes sur le canevas, de MS-Paint sont connectés via une liste chaînée.
-
Le balayage « gauche/droite » sur Tinder utilise une liste doublement chaînée.
-
On peut garder la trace des tours dans un jeu multi-joueurs à l’aide d’une liste chaînée circulaire.
-
Les lignes de code dans un IDE peuvent être enregistrées dans une liste doublement chaînée.