Les listes restreintes
Pile et File
Il existe 2 gestions particulières d'ensembles de données sur la base de la liste.
La 1ère est une gestion de pile où les seules opérations disponibles sont : empiler (insertion en tête de liste), depiler (extraction en tête de liste) et vide (prédicat précisant si la liste est vide ou non). Ces opérations assurent la possibilité de gestion de type LIFO (dernier entré, premier sorti).
La 2e est une gestion de file fournissant les opérations : enfiler (insertion en queue de liste), defiler (extraction en tête de liste) et vide. La gestion est de type FIFO (premier entré, premier sorti).
La gestion de pile peut être assurée facilement à l'aide d'un tableau puisque les entrées/sorties se font au sommet du tableau. Le seul inconvénient est de l'ordre de l'occupation de mémoire. Un tableau de taille moyenne peut être saturé à l'occasion d'un stockage important dans la pile. Un tableau de grande taille peut aboutir à une réservation de mémoire inutile dans 99 % des cas d'utilisation.
La gestion de file à l'aide de tableaux possède les mêmes inconvénients que la gestion de pile. De plus, la gestion de file, par son principe « premier sorti », s'accommode mal de l'utilisation de tableaux où la sortie du tableau entraîne une modification du rang des éléments du tableau. Toutefois, la gestion circulaire du tableau avec un indice de tête et un indice de queue permet de gérer cette modification sans nécessiter un décalage physique de tous les éléments de la liste.
La gestion des files et listes, reposant sur les listes chaînées, élimine les inconvénients de réservation de mémoire de taille fixe. Ceci entraîne bien évidemment un coût puisque, dans une liste, à chaque élément est associé au moins un pointeur.
Pour ces gestions particulières à base de listes, on parle communément de listes restreintes.