Liste chaînée

L'implémentation de la pile, dans le chapitre précédent, pose un problème au niveau de la gestion de la mémoire : une pile occupe, lorsqu'elle est vide, autant de mémoire que si elle contenait MAX éléments. Cela nous oblige à trouver un compromis entre le nombre maximal d'éléments qu'une pile peut contenir et la quantité de mémoire qu'occupe une pile à tout moment de son utilisation. Il semblerait plus judicieux qu'une pile occupe une quantité de mémoire proportionnelle au nombre d'éléments qu'elle contient.

On préférerait que chaque appel à la procédure empile augmente la taille mémoire de la pile, et que chaque appel à la procédure dépile la diminue. C'est ce que permet le principe de la liste chaînée.

Principe de la liste chaînée

Une liste chaînée est une structure de donnée permettant, comme les tableaux, de stocker plusieurs valeurs de même type, mais qui soit de taille variable, contrairement aux tableaux. On la nomme ainsi car elle est similaire à une chaîne composée de maillon : chaque maillon est relié au maillon suivant, de sorte qu'en ne tenant que le premier maillon, on peut accéder (en « déroulant » la chaîne) à tous les maillons de la chaîne. Par ailleurs, on peut facilement agrandir ou rétrécir la chaîne en lui ajoutant ou retirant des maillons.

La construction d'une liste chaîne suppose donc la définition de la structure suivante :

from algo import *

class Tmaillon(Struct):
    valeur = str
    suivant = SAME

On voit que chaque maillon porte une valeur (ici de type entier, mais on pourrait bien sûr utiliser n'importe quel type), et pointe vers un autre maillon grâce à son champ suivant 1. Le nombre de maillons dans la liste sera égal au nombre de valeurs à stocker. Le dernier maillon n'aura pas de suivant; pour représenter cela, on donnera à son champ suivant la valeur None, qui représente en Python l'absence de valeur. Pour manipuler la liste, il suffit de garder une référence vers son premier maillon. Cela est illustré dans la figure ci-dessous.

Une liste chaînée contenant quatre éléments.

1

La constante SAME est utilisée pour indiquer que le type du champ est le même que celui du type qui contient le champs. Ce mécanisme est nécessaire en Python car on ne peut pas référence le type Tmaillon avant que sa déclaration ne soit terminée.

La liste chaînée est donc une alternative aux tableaux, modulaire et extensible en terme d'occupation mémoire. Elle présente en revanche les inconvénients suivants :

• À nombre d'éléments égal, une liste chaînée occupe plus de mémoire qu'un tableau, car elle a besoin de stocker également les pointeurs « suivant ».

• Pour accéder à un élément d'une liste chaînée, on est obligé de parcourir tous les maillons jusqu'au maillon recherché. Le temps d'accès est donc d'autant plus grand que l'élément recherché est « loin » dans la liste, alors que dans un tableau, tous les éléments peuvent être accédé immédiatement.

Ces inconvénients sont cependant à relativiser puisque :

• le surcoût en mémoire peut être compensé par le fait qu'on n'est plus obligé d'allouer à l'avance plus d'éléments que nécessaire ;

• le surcoût en temps dépend du type d'utilisation qu'on fera de la liste (cf. l'implémentation de la pile, ci-dessous).

Implémentation de Tpile à l'aide d'une liste chaîné

Nous pouvons donc proposer une deuxième implémentation du type abstrait Tpile, qui utilisera une liste chaînée plutôt qu'un tableau. L'avantage de cette implémentation sera que la pile n'occupera que la quantité de mémoire nécessaire au nombre d'éléments qu'elle contiendra, et que nous n'auront pas à limiter a priori le nombre maximum d'élément qu'elle pourra contenir.

Comme dans une pile, le seul élément auquel on est susceptible d'accéder est le sommet, on choisi de stocker les valeurs récentes en tête de liste et les valeurs anciennes en queue de liste. Ainsi, l'accès au sommet restera efficace, malgré le recours à la liste chaînée.

######## Tpile : Implémentation n°2 ########

from algo import *

class Tmaillon(Struct):
    valeur = str
    suivant = SAME

class Tpile(Struct):
    msommet = Tmaillon

def construit_pile():
    p = Tpile(msommet = None)
    return p

def pile_vide(p):
    v = (p.msommet == None)
    return v

def pile_pleine(p):
    # cette implémentation ne limite pas le nombre d'éléments
    # dont une pile n'est jamais pleine
    pp = False
    return pp

def empile(p, e):
    m = Tmaillon(valeur=e, suivant=p.msommet)
    p.msommet = m

def sommet(p):
    s = p.msommet.valeur
    return s

def depile(p):
    p.msommet = p.msommet.suivant

On remarque que Cette implémentation a la même complexité algorithmique que la précédente : toutes les opérations sont en temps constant (même si le fait d'allouer la mémoire au fur et à mesure des besoins, plutôt qu'une fois pour toute à la création de la pile, risque de la rendre un peu moins performante, en valeur absolue, que la précédente).

Notons aussi que, dans la procédure depile, on ne fait rien du maillon qui est retiré de la liste chaînée. En Python (et dans la majorité des langages modernes), il sera automatiquement libéré de la mémoire (par un mécanisme nommé "ramasse miette"). Dans d'autres langages comme le C, il est de la responsabilité du programme de libérer explicitement la mémoire occupée par un maillon lorsqu'il n'est plus utilisé.