TNSI : La Structure de Données Listes⚓︎
Le Type Abstrait de Données Liste ⚓︎
Définition⚓︎
Listes
Une 
ou 
, est un Type Abstrait de Données (TAD) représentant un conteneur/collection fini d'
-
Tous accessibles (contrairement aux Piles et aux Files), mais de plusieurs manières, selon l'implémentation choisie :
- soit par Accès Séquentiel (l'un derrière l'autre, avec la notion de successeur ou suivant), au minimum.
- soit par Accès Direct / Accès Aléatoire , ou Random Access , c'est -à-dire via un indice, lorsqu'il y en a un
L'ordre des éléments a donc une importance
Primitives⚓︎
Pte
Une Liste dispose usuellement des opérations/primitives suivantes :
- Primitives de Base :
creerListeVide()/createEmptyList: crée une Liste VideestVide()/isEmpty(): renvoie si la liste est vide, ou pastete()/head()/shift(): récupére l'élément en tête de la liste, en le supprimant de la listeajouteTete()/unShift(): ajoute un élément en tête de la listeretirerQueue()/dequeue()/pop()/tail(): récupére l'élément situé en queue de la ListeajouteQueue()/enqueue()/push(): ajoute un élément en queue de la Listelongueur()/length(): renvoie la longueur de la liste
- Primitives auxilliaires, fréquemment rencontrées
inserer(L,e,i)/Create(L,e,i): insère un élémentedans la ListeLà la positionisupprimer(L,i)/Delete(L,i): supprime l'élément en positionide la listeLmodifier(L,e,i)/Update(L,e,i): modifie l'élément à la positionidans la ListeL, en le nouvele
- La définition du type abstrait
listen'est PAS normalisée, notamment pour les opérations/primitives des listes : il peut donc y avoir quelques variations sur ce sujet. Néanmoins, le principe reste fondamentalement le même. - Généralement, les éléments seront de même type de données (dans les langages à typage statique: Java/C++,), mais la structure de données liste ne l'impose pas (donc certains langages à typage dynamique : Python, .. autorisent des éléments de types différents)
- Positions Tête /Queue : Selons les contextes et les auteurs, la Tête et la Queue peuvent être inversées.
- La modélisation linéaire d'une Liste se prête bien à la représentation d'éléments qui arrivent et/ou partent dans le temps. Dans ce contexte :
- La Tête représente souvent le Premier élément arrivé
- La Queue représente souvent le Dernier élément arrivé (comme quand on on arrive dernier pour accéder à une ressource, et qu'on se place à la queue)
- La structure abstraite de liste est à la base de nombreuses autres structures, notamment les Piles et les Files, les Files de priorité, etc..
La Structure de Données Listes⚓︎
Implémentations des Listes⚓︎
Pte
Les Listes sont également des Structures de Données lorsque les primitives sont implémentées.
Il existe plusieurs implémentations d'une Liste :
Avec un Tableau Dynamique⚓︎
On peut représenter une liste de \(n\) éléments par un Tableau Dynamique \(L[0..(n-1)]\), lui même implémenté par la donnée de :
- la taille \(n\) du tableau (un entier) On ne détaillera pas ici son stockage en mémoire, mais on pourrait par exemple imaginer, très simplement, de placer l'entier \(n\) en début du tableau dynamique, et décaler les \(n\) cellules vers la droite (ce qui donnerait un tableau à \(n+1\) valeurs)
- \(n\) Cellules Contiguës, de
L[0]àL[n-1], contenant chacune l'adresse mémoire de l'élément contenu dans la cellule. Chaque Cellule étant de plus référencée par son indice.
- Pour lire l’élément d’indice \(i\), il suffit donc d’aller chercher son adresse dans la \((i+1)\)-ème cellule et pour cela d’ajouter \(i\) à l’adresse de début de tableau. Cela se fait en temps constant \(O(1)\).
- Pour modifier l'élément d'indice \(i\), il suffit de faire pointer la cellule correspondante sur un autre objet ce qui se fait aussi en temps constant \(O(1)\).
- Pour insérer un élément à l'indice \(i\) à la liste, il faut modifier \(n\) (ce dont nous ne parlerons pas) et ajouter une cellule au tableau (à la fin):
- Si la cellule qui suit directement les \(n\) cellules consécutives est "libre", pas de problème, on y met le pointeur qui désigne l’élément ajouté, ce qui se fait en \(O(1)\).
- Si ce n’est pas le cas, on doit alors déplacer tout le tableau vers une zone libre plus grande, où on pourra le prolonger, ce qui nécessite la recopie intégrale des \(n\) cellules et se fait en \(O(n)\).
Remarque Pour que cela arrive le moins souvent possible, on utilise d’habitude le procédé suivant : au départ, on prévoit en général plus de place que les \(n\) cases initiales, au cas où on voudrait prolonger la liste. Puis lors de chaque déplacement forcé, on s’arrange pour doubler la place mémoire disponible et la réserver. Cela réduit le nombre de déplacements et le coût d’ajout de \(p\) éléments est alors en \(O(max(n,p))\). Par exemple, si on part d’une liste vide et on ajoute un à un, \(n\) éléments à la liste, cela fait un nombre maximal de recopies de cases \(\displaystyle \approx n+\frac n2+ \frac n4··· = O(n)\), et la complexité del’opération globale a le même ordre de grandeur que s’il n’y avait pas eu de déplacement ! En pratique, on lisse le coût des déplacements et on fait l’approximation que les ajouts se font en temps constant.
- pour supprimer un élément de la liste, on doit modifier \(n\), et déplacer d'un cran vers la gauche tous les éléments situés à droite de l'élément à supprimer. Cela se fait en \(O(n)\) dans le pire des cas.
-
L'Implémentation par défaut de Python est
CPython qui est un interpréteur debytecode écrit en langage C. -
Pour info, il existe néanmoins d'autres implémentations de Python:
- IronPython (pour dévelopement avec/pour le framework .NET),
- Jython (écrit en Java, exécutables dans la Jython Virtual Machine),
- PyPy (écrit en Python, qui peut donc s'auto-interpréter!)
En pratique: Cela veut dire qu'une même notion du langage Python peut être implémentée différemment, selon l'implémentation de Python choisie. A Noter :
- Les types de données Python peuvent prêter à confusion : Le type de données
listest implémenté (en CPython) par un Tableau Dynamique, et non PAS par une Structure de Données Liste (Chaînée), comme le nomlistpourrait le laisser croire trompeusement. - Il est donc normal que les résultats trouvés ci-dessus soient en cohérence totale avec la Documentation Officielle de Python concernant la Complexité pour les
list, que l'on trouvera sur cette page de la Documentation officielle. Cf. le ticket Stackoverflow suivant qui justifie pourquoi, sur la Documentation Officielle, la complexité de l'ajout est toujours en \(O(1)\) dans le pire des cas amortis (mais PAS en \(O(1)\)).
Avec une Liste Chaînée (Simple)⚓︎
Listes Chaînées
Une
- Tous les éléments sont appelés des
Cellules , ou Maillons , ou Noeuds , ou Nodes , et se composent de deux choses :- une valeur
- un lien, en fait un pointeur/référence, vers l'élément suivant / successeur
- On suppose également connue la référence vers la première Cellule appelée
Tête (et seulement cette référence)
Une Liste Chaînée est une autre implémentation possible pour une liste. on dit que les Cellules sont chaînées (entre elles)
Le symbole queue), lorsque le suivant n'existe pas.
En Python, on utilise souvent None pour implémenter ce symbole.
Le code Python-OOP suivant implémente une Classe Cellule d'une Liste Chaînée :
class Cellule:
"""Une Cellule d'une Liste Chaînée"""
def __init__(self,v,s):
self.valeur = v
self.suivante = s
On peut alors créer une instance de la liste |•|1|2|3|4|⟂| précédente grâce à :
uneListe = Cellule(1, Cellule(2, Cellule(3, Cellule(4,None))))
Plus précisément, on a créé ici 4 objets de la Classe Cellule, que l'on peut visualiser comme suit :
Par la suite on s'autorisera le dessin simplifié suivant :
Listes Chaînées Doubles⚓︎
Listes Chaînées Doubles
Définition : Une , ou , est une Liste Chaînée contenant des références :
- vers le premier élément (la
tête) de la liste (de même que les Listes Chaînées Simples) - et aussi, vers le dernier élément (la
queue) de la liste
Autres Variantes⚓︎