Classiquement, une liste désigne un ensemble séquentiel, de taille variable et finie, d'objets.

Par exemple, les wagons d’un train forment une liste. Pour aller au wagon N°4 en partant de la locomotive, il faut obligatoirement traverser les wagons 1, 2 et 3 en séquence (à la suite). On doit en outre pouvoir ajouter ou enlever un ou plusieurs wagons au train !

En informatique, les listes reproduisent ce comportement intuitif — mais sont également (et surtout !) d'un intérêt théorique fondamental.

En effet, les listes, et plus particulièrement leur implémentation dynamique (cf. fiches ** et **), permettent une introduction aux autres TADs fonctionnant sur le même principe.

1. Définition du type abstrait "Liste" et généralités

Le TAD liste est l'un des TAD permettant de stocker et manipuler plusieurs éléments.

D'un point de vue abstrait, une liste est soit :

  • la liste vide ;
  • Un moyen d'accéder au 1er maillon et le reste de la liste.

Dans une liste non vide, chaque maillon (en anglais : link) contient en pratique :

  • Un élément;
  • Le moyen pour accéder au maillon suivant.

Remarquez que le TAD Liste est défini récursivement. La liste vide apparaît alors comme le marqueur du cas terminal de la définition récursive.

Une valeur spéciale, généralement notée nil, marque justement l'absence de maillon suivant (et donc la fin d'une liste) : c'est le symbole de la liste vide.

Exactement de la même manière qu'un train est repéré par sa locomotive :

Une liste est repérée par le lieu de son premier maillon, appelé la tête de liste.

L'accès est séquentiel : puisqu'on ne connaît que la tête de liste, i.e. le lieu du premier maillon (ou nil), l'accès au maillon en position n impose de passer par tous les n-1 maillons précédents.

Pour reprendre la métaphore du train, il n'y a pas de raccourci immédiat vers chacun des wagons, mais seulement une porte d'un wagon vers le suivant.

On donne ci-dessous une représentation visuelle d'une liste dont les éléments sont des nombres réels, et qui ici contient 3 maillons (donc 3 éléments : 1.0, 8.0 et 9.0 ).

La liste ( 1.0 8.0 9.0 ).

Sur ce schéma :

  • Le carré orange tout à gauche figure la variable liste : cette variable permet d'accéder à la tête de la liste (son premier maillon)
  • Chaque rectangle bicolore vert-orange est un maillon de la liste. Dans chaque maillon :
    • Le carré vert figure les éléments (ici, des réels) stockés dans la liste.
    • Le carré orange figure le moyen d'accéder au maillon suivant de la liste depuis le maillon courant.
  • Enfin, dans le dernier maillon de la liste, le carré noir figure la valeur nil : il n'y a plus de maillon suivant.

Pour atteindre le dernier maillon, contenant l'élément 9.0, il faut d'abord passer par celui contenant 1.0, puis par celui contenant 8.0.

2. Interface (minimale) en C définissant le type abstrait Liste

Pour compléter la définition du type abstrait Liste, il faut préciser les opérations qu'il supporte.

En C, il s'agit de préciser les contrats (prototypes + documentation) des fonctions qui manipulent la structure de donnée. C'est ce qu'on appelle l'interface de programmation ou API du type abstrait.

On précise ici de plus les coûts attendus pour chacune des opérations.

Dans le tableau suivant :

  • On suppose qu'il existe un type list_t ; on ne sait pas encore comment il est défini, mais peu importe.
  • le type des éléments stockés dans la liste est noté element_t

Interface minimale en C du type abstrait Liste :

prototype contrat coût attendu
(n est le nombre d'éléments de la liste)
list_t list_new() crée une nouvelle liste, vide. O(1) : coût constant
int list_is_empty(list_t l) teste si une liste est vide.
Retourne 1 (true) si la liste est vide, 0 (false) sinon.		 O(1) : coût constant
list_t list_add_first(element_t e, list_t l) ajoute l'élément e en tête de la liste l et retourne la nouvelle liste ainsi augmentée ; O(1) : coût constant
element_t list_first(list_t l) retourne l'élément en tête de la liste l.
PRECONDITION : liste non vide. 		O(1) : coût constant
list_t list_del_first(list_t l) Supprime la tête d'une liste non vide et retourne la nouvelle liste.
PRECONDITION : liste non vide. 		O(1) : coût constant
size_t list_length(list_t l) retourne le nombre d'éléments de la liste O(n)
list_t list_delete(list_t l) supprime une liste (et les éléments associés). Retourne une liste vide. O(n)
void list_print(list_t l) affiche les éléments de la liste dans le Terminal. O(n)

Ces fonctions sont au coeur de la définition du type abstrait Liste.

On les complète parfois, en fonction des besoins, par d'autres fonctions, telles que par exemple :

  • element_t list_get(list_t l, int i) : retourne l'élément d'index i (qui doit exister bien sûr)
  • list_t list_add_last(element_t e, list_t l) : ajoute l'élément e à la fin de la liste l et retourne la nouvelle liste ainsi augmentée ;
  • list_t list_del_last(list_t l) : supprime le dernier maillon d'une liste non vide et retourne la nouvelle liste ;
  • link_t list_find(element_t e, list_t l) : retourne le 1er maillon contenant l'élément e ou nil si la liste ne contient pas e;
  • list_t list_remove(element_t e, list_t l) : supprime toutes les occurences de l'élément e de la liste et retourne la liste ainsi modifiée
  • list_t list_copy(list_t l) : retourne une nouvelle liste, qui est une copie conforme de l
  • etc.

Plusieurs implémentations du TAD liste sont possibles.

  • Dans les fiches suivantes, on construit l'implémentation appelée "liste chaînées dynamique", qui a recours à l'allocation dynamique.
  • Des variantes sont proposées dans une dernière fiche.