Les listes linéaires chaînées

Allocation statique

L'allocation de l'espace se fait tout à fait au début d'un traitement. En termes techniques, on dit que l'espace est connu à la compilation. C'est donc la notion de tableau.

Allocation dynamique

L'allocation de l'espace se fait au fur et à mesure de l'exécution du programme. Pour pouvoir faire ce type d'allocation, l'utilisateur doit disposer des deux opérations: Allouer et Libérer.

Une liste linéaire chaînée (LLC) est un ensemble de maillons (alloués dynamiquement)chaînés entre eux. Un élément d'une LLC est toujours une structure ( objet composé) avec deux champs : valeur et adresse.

A chaque maillon est associée une adresse.

Une LLC est caractérisée par l'adresse de son premier élément. Nil constitue l'adresse qui ne pointe aucun maillon.

Algorithmes sur les listes

De même que sur les vecteurs, on peut classer les algorithmes sur les LLCs comme suit :

a) parcours : accès par valeur, accès par position

b) mise à jour : insertion, suppression

c) algorithmes sur plusieurs LLCs : fusion, interclassement, éclatement,...

d) tri sur les LLCs.

Listes particulières

Listes bidirectionnelles : c'est une liste à double sens.

Listes circulaires : c'est une liste telle que le dernier élément pointe sur le premier.

On peut aussi définir des listes bidirectionnelles qui sont circulaires.

Modèle sur les listes linéaires chaînées

Afin de développer des algorithmes sur les LLCs, on construit une machine abstraite avec les opérations suivantes : Allouer, Libérer, Aff_adr, Aff_val, Suivant, Valeur définies comme suit :

Allouer(t, p) : allocation d'un espace de taille spécifiée par le type t. L'adresse de cet espace est rendue dans la variable pointeur p.

Liberer(p) : libération de l'espace pointé par p.

Valeur(p) : consultation du champ valeur du maillon d'adresse p.

Suivant(p) : consultation du champ adresse du maillon d'adresse p.

Aff-adr(p, q) : dans le champ adresse du maillon d'adresse p, on range l'adresse q.

Aff-val(p, val): dans le champ valeur du maillon d'adresse p, on range la valeur val.

On notera cet ensemble d'opérations M_llc. Cet ensemble est appelée modèle.

Modèle sur les listes linéaires chaînées bidirectionnelles

Un élément d'une liste linéaire chaînée bidirectionnelle est composé de trois champs : valeur, adresse gauche et adresse droite.

Le modèle est le suivant :

M_llcb = M_llc - {Affadr} + { Aff_adrg, Aff_adrd, Précédent }

Le modèle des LLCs est donc étendu par les opérations suivantes :

Précédent(p) : accès au champ adresse gauche du maillon d'adresse p.

Aff-adrg(p, q) : dans le champ adresse1 (adresse gauche) du maillon d'adresse p, on range l'adresse q.

Aff-adrd(p, q) : dans le champ adresse2 (adresse droite) du maillon d'adresse p, on range l'adresse q.