Les Listes

Comme la pile et la file, une liste est un type abstrait de données contenant des éléments accessibles de manière séquentielle. Par convention, ces éléments sont tous de même type (tous des entiers, ou tous des caractères, etc...).

Une liste est une structure de données récursive. Elle est :

• soit vide ;
• soit sous la forme d'un couple constitué d'un élément (la tête) et d'une liste (la queue).

Exemples

1. L1 = ()
L1 est la liste vide.

2. L2 = (5, ())
L2 est la liste constituée de l'élément 5 et de la liste vide.

3. L3 = (8, (5, ()))
L3 est la liste constituée de l'élément 8 et de la liste L2.

4. La liste constituée des éléments 2, 3, 8, 5 dans cet ordre est :
   L4 = (2, (3, (8, (5, ()))))

Attention

Il ne faut pas confondre le TAD « liste » avec le type list de Python. Ce dernier est plus proche de la notion abstraite de « tableau » (cf. cours de 1ère).

Interface d'une liste

Une interface minimale de liste comporte cinq opérations.
Ces opérations permettent ensuite de définir toutes les autres (longueur d'une liste, appartenance à une liste, insertion et suppression d'éléments, etc...).

Méthode/Opérations	Description
L = Liste()	Initialisation d'une liste vide
est_vide(L)	Renvoie True si la liste L est vide, False sinon.
inserer_en_tete(elt, L)	« Ajoute » un nouvel élément en tête de la liste, c'est-à-dire renvoie le couple (elt, L)
tete(L)	Renvoie la valeur de l'élément en tête (le premier élément du couple)
queue(L)	Renvoie la liste située en queue (le second élément du couple)