Listes

Le type abstrait LISTE

Une liste est une façon d'organiser des données, ce que l'on appelle une structure de données, destinée à pouvoir accéder librement à chacune de ces données.

Une liste est aussi appelée une collection, ou une séquence d'éléments, chaque élément contenant une donnée.

Les éléments sont repérés selon leur rang ( = indice ) dans la liste.
L’ordre des éléments dans une liste est fondamental : ce n’est pas un ordre sur les valeurs des éléments, mais un ordre sur les places des éléments.

Que faut-il pour faire fonctionner une liste ?

Hormis les données elle-mêmes, il faut disposer de certaines opérations qui permettent de manipuler la structure de données :

• création d'une liste vide
• accès à un élément quelconque de la liste
• modification d'un élément
• insertion d'un élément à n'importe quelle position de la liste
• suppression d'un élément à n'importe quelle position de la liste
• savoir si la liste est vide
• ..............

Tout dépend de ce dont l'utilisateur a besoin pour faire fonctionner son code !

Comment coder une liste ?

Les listes peuvent être représentées en mémoire de différentes façons; vous en verrez deux :

• par un tableau : chaque élément de la liste peut être désigné par sa place dans la séquence, à l’aide de son indice.
  Pour accéder à un élément déterminé, on utilise le nom de la variable qui contient la liste et on lui accole entre deux crochets, l’index numérique qui correspond à sa position.

  

• par une liste chaînée : Chaque maillon est un objet dans lequel on stocke l’élément et une information pour trouver le suivant (voire aussi le précédent dans des versions plus évoluées).
  On n'a un accès direct qu'au premier maillon d'une liste chaînée, mais il faut parcourir tous les maillons précédents pour accéder à un élément donné.

  

Un peu de vocabulaire

Implémentation par tableau de taille fixe

Principe

Dans cette implémentation, une liste est représentée en mémoire par un tableau, c'est à dire une succession de cases mémoires contiguës ( = les unes à la suite des autres ), la n^ième case du tableau correspondant au n^ième élément de la liste.

Ce tableau est généralement statique, c'est à dire d'une dimension fixée à sa création : il ne peut pas être "rallongé" ou "raccourci" de manière simple.

Les éléments stockés dans une liste sous forme de tableau doivent être du même type, sauf si, au lieu de stocker directement l'élément, on stocke en réalité son adresse en mémoire ( c'est ce que fait par exemple Python ); la liste contient alors des références vers les éléments, et pas les éléments eux-mêmes.

Complexité des opérations

L'intérêt de l'utilisation d'un tableau est que l'accès à un de ses éléments se fait en temps constant ( complexité O(1) ), ce qui signifie que le temps d'accès ne dépend pas du nombre de données stockées, donc de la taille de la liste.

Ceci vient du fait que les éléments d'un tableau sont stockés en mémoire à des adresses contiguës les unes des autres, et qu'il suffit donc de connaître l'adresse en mémoire du début du tableau pour accéder par décalage ( "offset" ) de cette adresse à n'importe lequel de ses éléments ( et notamment son dernier ! ).

Avantages et inconvénients

Implémentation

Considérons par exemple un programmeur en langage de bas niveau comme le langage C, qui n'a pas ce type à sa disposition, uniquement des tableaux de taille fixe, et qui désire implémenter le TAD Liste.

Vous allez écrire quelques méthodes qui permettraient à ce programmeur de disposer de ces fonctionnalités.

Création d'une liste vide

Accès et modification des éléments de la liste

assert précondition, "Message d'erreur"
				

Ajouter un élément supplémentaire en fin de liste

Avec un tableau de taille fixe, il n'y a pas le choix dans la manière de procéder :

• on crée ailleurs en mémoire, là où il y a de la place, un nouveau tableau ayant un élément de plus que le précédent ( la taille passe de n à n+1 éléments );
• on recopie les n éléments du premier tableau dans le deuxième;
• enfin, on place le nouvel élément dans la dernière "case" du nouveau tableau.

tab = tab + [element] # un nouveau tableau 'tab' est en fait créé...    
                

Suppression du dernier élément

Conclusion

Ces opérations, de même que celle qui permettent d'insérer et de supprimer un élément à n'importe quel indice, peuvent être très coûteuses en temps dans le cas de grandes listes car on a besoin de "déplacer" ( en fait, recopier ailleurs en mémoire ) pratiquement tous les n éléments de la liste ( exactement : n-1 éléments ) : ce sont donc des opérations de complexité O(n).
Dès que l'on a à modifier souvent le début ( ou la fin ) d'une liste ( et surtout si la liste est très grande ! ), ce n'est donc pas l'implémentation la plus adaptée.

Implémentation par tableau dynamique : le type list de Python

Principe

Un tableau dynamique est un tableau dont la taille peut varier ("allongement" ou "raccourcissement" ), et ce de manière "automatique".

Dans le cas des tableaux Python ( type Python list, attention encore une fois à la confusion ! ), on dispose en particulier des méthodes suivantes :

• tableau.append(element) : ajoute un élément en fin de tableau.
  
• element = tableau.pop() ; retire le dernier élément du tableau et le renvoie
• tableau.insert(indice, element) : insertion à n'importe quel indice
• element = tableau.pop(indice) : suppression à n'importe quel indice et renvoi de l'élément

Complexité des opérations

La gestion d'un tableau dynamique est une affaire de compromis entre d'une part, la rapidité d'accès à un élément d'un tableau de taille fixe, et d'autre part l'avantage d'avoir une taille de tableau variable.

Python gère cela de cette façon :

• à la création d'un tableau, il réserve en mémoire une taille qu'il estime "suffisamment grande" pour les usages les plus courants; le fonctionnement est alors celui d'un tableau de taille fixe.
• si ce tableau arrive à être plein, alors il réserve en mémoire un espace plus grand, et déplace tous les éléments du premier tableau dans ce nouvel espace ( en supprimant ensuite l'ancien )

Il va sans dire que, si le tableau plein contient un très grand nombre d'éléments, ces opérations de copie peuvent prendre du temps : c'est une opération en O(n).

Cependant, cela se produit très rarement comparé aux opérations de remplissage de tableau; on considère alors ( en fait, il y a toute une "cuisine" là-derrière faite de compromis entre le choix de la taille de tableau à partir de laquelle il faudra redimensionner, et occupation de la mémoire ) que l'ajout ( append ) et le retrait ( pop ) du dernier élément d'un tableau dynamique Python se fait en moyenne en temps constant. C'est une garantie qu'offre d'ailleurs le langage ( et d'autres également ).

Par contre, comme dit plus haut, l'instruction tableau = tableau + [element] réserve à chaque ajout d'un élément un nouvel espace mémoire et recrée donc un nouveau tableau, ce qui est donc beaucoup moins efficace !

Pour plus d'informations à ce sujet, vous pouvez consulter cette page.

Les listes chaînées

Principe

Les éléments d'une liste chaînée sont appelés cellules ou maillons, et contiennent non pas une seule information, mais deux :

• une première, appelée element, valeur ou historiquement car, contient l'information stockée dans la cellule ( un entier, une chaîne de caractères, etc...)
• la deuxième, nommée suivant ou cdr, contient un lien vers la cellule suivante sous la forme d'une liste des cellules suivantes ( attention, "liste" au sens de "liste chaînée", et pas "liste Python" ! ).

On a donc ici affaire à une chaîne de cellules, ce qui justifie la dénomination courante de liste chaînée.

Notons qu’il s’agit donc d’une structure linéaire, qu’on peut parcourir en partant du début, mais sans aucun accès direct à un élément autre que le premier.

Voici la représentation schématique d’une liste chaînée comportant, dans cet ordre, les trois éléments 1, 2 et 4 :

Le champ suivant de la dernière cellule renvoie vers une liste vide, conventionnellement nommée nil et représentée ci-dessus par un hachurage.

Bien que dans la figure ci-dessus les maillons soient présentés comme s’ils se suivaient en mémoire, il est très probable que ceux-ci soient éparpillés au travers des millions d’octets de la mémoire vive ( ils ne sont donc pas contigus )

Dans cette implémentation, une liste ( mais pas les valeurs stockées ! ) est donc définie entièrement par les champs valeur et suivant de sa première cellule ( que l'on appelle la tête de la liste ). C'est donc une définition récursive d'une liste : elle est égale à sa première valeur + la suite des éléments de la liste , qui elle-même est définie comme une valeur + une suite, etc....

La liste ci-dessus pourrait ainsi être définie par l'opération : liste = maillon(1, maillon(2, maillon(4, nil))).

Avantages et inconvénients

Une classe Liste

Choix de l'implémentation

La POO est bien adaptée à la création d'une liste chaînée. Pour implémenter le type LISTE sous forme de liste chaînée en POO, on peut utiliser deux classes distinctes :

1. une classe Maillon d'attributs valeur et suivant; cette classe ne contient qu'un constructeur et aucune méthode :

   
   class Maillon:
   
       def __init__(self, valeur, suivant = None): # création d'un maillon qui ne pointe par défaut vers aucun autre
           self.valeur = valeur
           self.suivant = suivant # suivant est de type Maillon !		
   					

   Le paramètre suivant contient le lien vers l'objet de type Maillon suivant dans la chaîne, ou None si il s'agit du dernier maillon.

   Si on ne fournit pas d'argument suivant au constructeur, il est remplacé par défaut par None, ce qui permet donc de définir automatiquement le dernier maillon d'une liste.

2. une classe Liste très simple :

   
   class Liste:
   
       def __init__(self, tete = None): # création liste, vide par défaut si aucun maillon n'est fourni en argument
           self.tete = tete # stockage de sa tête. Le paramètre 'tete' est bien entendu de type Maillon !  
   			

   Le seul attribut de la liste est donc son maillon de tête : initialement, ce peut être l'élément None ( liste vide ) par défaut, ou un maillon passé en paramètre..

   Cette tête peut ensuite être "allongée" pour rajouter d'autres éléments ( = d'autres maillons ) dans la liste, mais la seule information directement accessible est donc bien uniquement cette tête.

   Cependant, il ne faut pas croire que self.tete contient uniquement l'information du seul premier élément de la liste : elle contient en fait toute la structure de la liste, c'est à dire les éléments eux-mêmes mais aussi les "liens" vers les maillons successifs.

L'intérêt de cette implémentation à deux classes est de pouvoir créer des listes vides; en effet, un Maillon égal à None n'est pas la même chose qu'une Liste sans tête ( [] != [None] ) ...

Création d'une liste

Test si la liste est vide

Primitives sans parcours de la liste

Insertion au début

C'est un peu délicat dans l'ordre des opérations :

• on crée un nouveau maillon
• on fait pointer son champ suivant vers la ( l'ancienne ) tête de la liste
• on remplace cette tête par le nouveau maillon.

Suppression au début

Primitives nécessitant de parcourir la liste : version itérative

Pour ces primitives, il va être nécessaire de parcourir les éléments de la liste, soit en totalité, soit jusqu'à un certain élément.

Conformément à leur définition, les listes sont des structures récursives. Par conséquent, les opérations sur les listes s’expriment naturellement par des algorithmes récursifs.
En même temps, les listes ont des structures linéaires, parfaitement adaptées à un parcours itératif...
Vous allez donc dans un premier temps proposer des implémentations des méthodes suivantes de manière itérative, puis vous en donnerez ensuite une version récursive.

Nombre d'éléments dans la liste

L'idée est de compter les éléments un par un en "traversant" la liste maillon après maillon, tant qu'on n'a pas atteint la fin de la liste : méthode len: maillon ← tete de la liste tant que l'on n'a pas atteint la fin de la liste: incrémenter un compteur maillon ← suite de la liste renvoyer la valeur du compteur

Pour "avancer d'un maillon" dans la liste, il suffit de "remplacer" le maillon courant par la suite de la liste ( c'est à dire son champ suivant ) !

Lister les éléments de la liste...

Ou comment afficher le contenu de la liste ?

Accès à un élément de la liste, et/ou affectation de valeur

Insertion à la fin

Dans ce cas :

• on "traverse" toute la liste
• on crée un nouveau maillon
• on fait "pointer" le champ suivant du dernier maillon de la liste vers le nouveau.

Insertion en n'importe quelle position

Alors là, il faut vraiment bien réfléchir aux liens à mettre à jour...Voila le principe :

• on parcourt la liste jusqu'à atteindre la position où insérer le nouvel élément;
• on créé un nouveau maillon
• on fait pointer le champ suivant du nouveau maillon vers la suite de la liste
• on fait pointer le champ suivant de l'élément courant vers le nouveau maillon

Suppression d'élément

Version récursive

On exploite ici le caractère récursif d'une liste chaînée.
Par exemple, pour le calcul du nombre d'éléments :

• Cas général : len(liste) = 1 + len(suite de la liste)
• Cas de base : quand on est arrivés en fin de liste ( ou si la liste est vide ! ), 'liste' est nil; on renvoie alors 0

D'où l'algorithme :

	
fonction len(maillon: initialisé à la tête de la liste):
	si maillon est nil:  # on est arrivés en fin de liste
		renvoyer 0
	sinon:
		renvoyer 1 + len(maillon.suivant)						
			

Dans cette version, la méthode len prend donc un paramètre; on doit donc à son premier appel lui passer le premier maillon de la liste ( sa tête ) comme argument.

Pour un utilisateur, l'interface de cette fonction n'est donc pas très judicieuse...on peut remédier à cela en implémentant cette fonctionnalité sous la forme de deux fonctions :

• une qui réalise le traitement demandé, et qui sera "cachée" à l'utilisateur
• une deuxième qui fera partie de l'interface de la classe, c'est à dire qui sera celle effectivement "disponible" pour l'utilisateur, et que celui-ci appellera.

class List:

	def _len(self, maillon): # méthode "privée" ( le caractère underscore "_", non obligatoire, signale à l'utilisateur que cette fonction est "privée", donc à ne pas utiliser depuis l'extérieur )
		.....                # code de la méthode de traitement		
		
	def __len__(self):         # méthode "publique" appelée par l'utilisateur
		return _len(self.tete) # appel de la méthode "privée", et renvoi de son résultat	
			

On peut ainsi appeler simplement la méthode len sans lui passer aucun paramètre, ce qui est son utilisation "normale" et attendue de la part d'un utilisateur !

Quelques exercices autour des listes chaînées

Vous avez ( sûrement...) fait les exercices suivants avec des listes Python...vous allez maintenant les faire avec des listes chaînées !

Test d'appartenance

Liste Python → Liste chaînée

Occurrence(s) d'une valeur

Renverser une liste

Concaténer deux listes

Insérer dans l'ordre

Tri insertion

Conclusion sur les implémentations du TAD LISTE

Une comparaison de la complexité en temps des trois implémentations de listes que vous avez vues :

Selon le critère pour lequel un algorithme donné doit être le plus efficace, on choisira donc telle ou telle implémentation.

Ouverture à d'autres langages : LISP

Le langage LISP a été inventé au MIT à la fin des années 50 par John McCarthy. On l'a beaucoup utilisé dans le domaine de l'intelligence artificielle, et il est encore employé de nos jours, notamment comme langage d'extension dans l'éditeur de texte Emacs ou l'outil de CAO AutoCAD.

De nombreux "dialectes" de ce langage existent; ils ont été "unifiés" au sein de Common Lisp, qui sera la version que nous utiliserons ici.

Le terme Lisp a été forgé à partir de l'anglais « list processing » (« traitement de listes ») : en effet, tout est manipulation de listes en Lisp !

Syntaxe de base

LISP manipule des expressions sous forme :

• soit d'éléments uniques ( appelé "atomes" dans le langage )
• soit de listes parenthésées d'éléments; le séparateur d'élément est l'espace.
  

Dans ce deuxième cas, Lisp considère toujours le premier élément comme une fonction, et évalue toujours le résultat de l'expression.

L'évaluation des expressions se fait de manière préfixe, c'est à dire les opérateurs de calcul en premier, puis les données :

>>> 3 ; une simple valeur
3

>>> nil ; l'équivalent de None ou de False
NIL

>>> t ; l'équivalent de True
T

>>> "Que de parenthèses..." ; une chaîne de caractère(s)
"Que de parenthèses..."

>>> (+ 2 3 8) ; somme de 3 nombres
11

>>> (- 5 6) ; différence
-1

>>> (* 6 8) ; produit
48

>>> (* 2 (cos 0) (+ 4 6))) ; expression plus complexe
20
			

>>> '(1 5 6 78 9 41) ; définition d'une liste sans évaluation
(1 5 6 78 9 41)
				

Au sein d'un programme, on peut utiliser l'instruction write pour afficher le résultat de l'évaluation d'une expression :

(write (/ 36 6)) ; affichage du résultat de l'évaluation de la division de 36 par 6
			

Même si on peut souvent s'en passer, Lisp permet l'affectation de variables avec la fonction setf :

(setf a 45) ; affectation de la valeur 45 à la variable 'a'
(setf l '(12 4 6 98 7 35)) ; affectation d'une liste à la variable 'l'
			

Lisp n'est pas sensible à la casse : liste et LISTE désigneront donc la même variable.

La structure de données de liste en Lisp

L'implémentation des listes en Lisp correspond à des listes chaînées ( même si en interne, c'est plutôt une structure d'arbre qui est utilisée ).

Une liste peut être :

• soit la liste vide (nil)
• soit un élément (car ou first), suivi de la suite de la liste (cdr ou rest) terminé par nil.

>>> (first '(56 12 7 8 95))
56

>>> (rest '(56 12 7 8 95))
(12 7 8 95)

>>> '()
NIL
			

LISP dispose de la fonction cons pour construire une liste à partir d'un élément et d'une autre liste :

>>> (cons 1 '(2 3 4))
(1 2 3 4)
			
			

Structure conditionnelle

Lisp dispose de l'équivalent du if...else... , mais pas du elif ( il est donc nécessaire d'"imbriquer" logiquement différentes expressions conditionnelles )

(if (condition)
	(résultat renvoyé si la condition est vraie)
	(résultat renvoyé si elle est fausse)
)
			

Exemples de condition :

(if (= a 3) ; si a est égale à 3
	...
)

(if (/= c 45) ; si c est différente de 45
	...
)

(if (null l) ; si la liste l est vide ( = égale à nil )
	...
)

			

Définition de fonctions

Le mot-clé à utiliser est defun, suivi du nom de la fonction, puis de la liste du (ou des) paramètre(s) entre parenthèses :

(defun ma-fonction(a b)
	expression 1
	expression 2
	....
)
			

L'appel de la fonction se fera avec une expression analogue à celle vue ci-dessus :

(ma-fonction 15 23) ; appel seul de la fonction

(write (ma-fonction 15 23)) ; appel et affichage du résultat renvoyé 
			

Il est à noter que, comme chaque expression est évaluée par Lisp, c'est le résultat de la dernière expression évaluée qui est renvoyé en sortie de fonction : pas besoin de 'return'...

(defun plus-grand(a b)
	(if (> a b)
		a ; résultat renvoyé si la condition est vraie
		b ; résultat renvoyé si elle est fausse
	)
)
			

Quelques fonctions avec des listes en LISP...

Des fonctions simples

Des fonctions sur les listes