[MI] Listes Linéaires Chaînées (LLC) : Insertion au début de liste

Les listes linéaires chaînées sont la forme la plus simple pour une gestion dynamique de la mémoire (allocation et libération dynamiques). Dans cet article, je vais citer une utilisation très simple mais très utile.

Reprenons la déinfition la plus simple (par ici) :
"Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type, dont la représentation en mémoire de l'ordinateur est une succession de cellules faites d'un contenu et d'un pointeur vers une autre cellule. De façon imagée, l'ensemble des cellules ressemble à une chaîne dont les maillons seraient les cellules."
Ainsi, la déinfition précise qu'il y a, obligatoirement, un chaînage entre les éléments de la liste, mais la définition ne précise pas comment ce chaînage est créé : contrairement aux tableaux qui dépendent de la bonne utilisation des indices, nous avons plus de liberté et de possibilités avec les listes linéaires chaînées.
Dans cet article, nous allons créer une liste basée sur l'insértion au début. Chaque nouveau noeud devient le premier noeud de la liste. Cette technique qui semble très simple est très efficace pour "inverser" l'ordre des éléments en entrée (ou dans une autre structure) sans à refaire un autre passage (l'inversion s'effectue pendant la lecture même - et n'oublions pas que ne connaissons pas le nombre des éléments)
Le code suivant montre l'implémentation de cette technique :

Program LLCInsererTete;

Type

{
 Déclaration d'une liste linéaire chaînée d'entier
}

Liste = ^Cellule;
Cellule = Record
 val : Integer;
 suiv : Liste;
End;

Procedure InsererTete(var L: Liste; val : Integer);
Var
 P : Liste;
Begin

 { Nous créons une nouvelle cellule }
 New(P);
 P^.val := val;
 P^.suiv := L;

 { La nouvelle cellule devient la tête de la liste }
 L := P;

End;

Var
 L, Q : Liste;
 n : Integer;

Begin

 L := Nil;

 WriteLn('Donnez une liste d''entiers (0 pour terminer)');
 ReadLn(n);
 While(n <> 0) Do
 Begin
  InsererTete(L, n);  
  ReadLn(n);
 End;
 
 Q := L;
 While (Q <> Nil) Do
 Begin
  WriteLn(Q^.val);
  Q := Q^.suiv;
 End;

End.

Une exécution de ce code avec la saisi des valeur 25, 14, 89 et 0 (pour terminer la lecture) permet d'avoir le résultat suivant :

Pour les 1MI, nous avions un problème un peu plus détaillé. La liste à créer doit prendre ses valeurs à partir d'un tableau tout en gardant l'ordre des éléments. Notez bien la boucle For définie :

For i := N Downto 1 Do
  InsererTete(L, T[i]);

Cette boucle permet de parcourir le tableau à partir de sa dernière case.
Le code suivant est le code complet (mais simple - pas de mise en forme ):

Program LLCInsererTete;

Const 
 N = 10;

Type

Liste = ^Cellule;
Cellule = Record
 val : Integer;
 suiv : Liste;
End;

Tableau = Array [1..N] of Integer;

Procedure InsererTete(var L: Liste; val : Integer);
Var
 P : Liste;
Begin

 New(P);
 P^.val := val;
 P^.suiv := L;
 L := P;

End;

Procedure CreerListe(var L : Liste; T : Tableau);
Var
 i : Integer;
Begin

 For i := N Downto 1 Do
  InsererTete(L, T[i]);

End;

Var
 L, Q : Liste;
 T : Array [1..10] of Integer;
 i : Integer;

Begin

 L := Nil;
 For i:= 1 to N Do
  ReadLn(T[i]);
 
 CreerListe(L, T);

 Q := L;
 While (Q <> Nil) Do
 Begin
  WriteLn(Q^.val);
  Q := Q^.suiv;
 End;

End.

Pour télécharger ces codes ainsi qu'une version avec un affichage amélioré, c'est par ici.