Les listes chaînées


Les tableaux/listes de python

En première, nous avons apris à utiliser les tableaux, une structure de donnée séquentielle disponible directement pour le programmeur avec une syntaxe adaptée.

Commençons par faire le point sur cette structure.

Quelques rappels sur les tableaux/listes de python

En python, on peut définir un tableau grâce à la syntaxe suivante:

>>> tableau = [1, 1, 2, 3, 5, 8, 13, 21]

On peut à la fois accéder et modifier un élément de rang donné:

>>> tableau[6]
13

>>> tableau[0] = -1
>>> tableau
[-1, 1, 2, 3, 5, 8, 13, 21]

Enfin, il est possible de connaître la longueur dun tableau:

>>> len(tableau)
8

Ce sont là les seules opérations élémentaires que doit satisfaire une structure de donnée appelée tableau. Précisons un peu cette notion:

Linterface dun tableau

Dun point de vue abstrait, un tableau est une structure de donnée répondant aux critères suivants:

Linterface dune structure de donnée est lensemble des opérations de base permettant dinteragir avec celle-ci. Le programmeur peut (et doit utiliser exclusivement) les opérations définies par linterface pour interagir avec une structure de donnée.

  • il sagit dun ensemble de données homogènes (cest-à-dire du même type) rangée de manière séquentielle;
  • La taille du tableau, encore appelée longueur, est fixe et connue au moment de la création du tableau;
  • on peut lire toutes les valeurs dun tableau en connaissant son rang. Les rangs sont des entiers compris entre 0 et \(N-1\), où \(N\) est la longueur du tableau;
  • on peut modifier nimporte quelle valeur du tableau de rang donné;
  • on peut connaître la longueur du tableau;
  • un tableau vide est un tableau de longueur 0.

On constate que les tableaux tels quimplémentés en python répondent bien à ces critères.

Mais on a aussi vu en Première que les tableaux du langage python peuvent faire bien plus. Notamment (et la liste est loin dêtre exhaustive):

  • On peut ajouter des éléments à la fin du tableau (changeant par la même la taille du tableau dynamiquement en cours de programme):

    >>> tableau.append(34)
    >>> tableau
    [-1, 1, 2, 3, 5, 8, 13, 21, 34]
  • À linverse, on peut retirer le dernier élément du tableau (sil existe):

    >>> tableau.pop()
    34
    >>> tableau
    [-1, 1, 2, 3, 5, 8, 13, 21]
  • Mieux encore: il est possible dinsérer (ou de retirer) des éléments de rang quelconque du tableau:

    
    >>> tableau.insert(2, 7)
    >>> tableau
    [-1, 1, 7, 2, 3, 5, 8, 13, 21, 34]
    >>> 

Ces fonctions ne font pas partie de linterface dun tableau, mais plutôt dune liste. Les tableaux du langage python sont en fait un type hybride ayant à la fois les caractéristiques dun tableau mais aussi dune liste. Dailleurs, en python, les tableaux sappellent des listes.

Dans ce cours, nous parlerons de tableau/liste pour désigner ce type hybride du langage python. Nous nous astreindrons cependant à toujours bien distinguer les cas dutilisation en tant que tableau pur, ou bien en tant que liste pure.

Examinons à présent linterface dune liste.

Linterface dune liste

Une liste est un type de valeur satisfaisant aux critères suivants:

  • il sagit dun ensemble de données homogènes (cest-à-dire du même type) rangée de manière séquentielle;
  • La taille dune, encore appelée longueur, est variable: elle peut changer au cours de la durée de vie de la liste;
  • Il est possible dinsérer et de supprimer des éléments en tête de liste;
  • Il est possible dinsérer et de supprimer des éléments en queue de liste;
  • Il est possible dinsérer et de supprimer des éléments à nimporte quelle position de la liste;
  • Il est possible de parcourir tous les éléments de la liste, du premier jusquau dernier;
  • une liste vide ne contient aucun élément, sa longueur est nulle.

Les tableaux/listes de python répondent à tous ces critères (et bien plus encore). Cependant, nous allons voir que certaines fonctions de ces interfaces (à la fois pour les tableaux mais aussi les listes) ont un coût caché à lexécution (qui est imperceptible pour des tableaux/listes ne contenant que peu de données, mais devient non négligeable lorsque lon travaille sur des données pouvant atteindre plusieurs mégaoctets, voire gigaoctets).

Coûts cachés de lutilisation des tableaux/listes

Le coût dun algorithme, encore appelé complexité, est la relation entre la taille des données en entrée et le nombre détapes nécessaires à son exécution. Jusquà présent (depuis le début de la Première), nous avons rencontré 3 types de coûts:

  • Un algorithme à coût constant demande, comme son nom lindique, un nombre constant dopérations, indépendemment de la taille des données en entrée.

    Des exemples dalgorithmes à coût constant pour les tableaux/listes du langage python:

    • Lire ou changer une valeur de rang \(i\) dans un tableau;

    Il suffit à linterpréteur python de calculer la position en mémoire de la valeur recherchée, puis de la lire. Le coût ne dépend pas de la taille du tableau;

    • Connaître la longueur dun tableau;

    En python la taille du tableau est stockée conjointement aux valeurs quil contient, il suffit dont de lire le contenu dune variable (cachée pour lutilisateur);

    • Savoir si un tableau est vide ou non;

    Il suffit de tester si la longueur est nulle, le coût est donc constant.

  • Un algorithme à un coût linéaire lorsque le nombre dopérations nécessaires à son exécution est proportionnel à la taille des données en entrée. La constante de proportionnalité nest en général pas précisée (et elle peut être relativement grande selon les algorithmes), mais ce qui est important de retenir est que, par exemple, si on double la taille des données, on double le temps dexécution: cest ce que signifie proportionnalité.

    Des exemples dalgorithmes à coût linéaire pour les tableaux/listes du langage python:

    • Ajouter un élément à une position quelconque du tableau: il y a un double coût caché, car il peut arriver que python doive réserver un nouvel emplacement mémoire (plus grand) pour ajouter un élément, nécessitant alors de recopier lintégralité du tableau (doù le coût linéaire), avec éventuellement un décalage.

    Examinez ce code sur lexcellent site python tutor qui met artificiellement en évidence les opérations nécessaires pour «ajouter» un élément en tête dun tableau. Tout ceci est bien évidemment invisible lorsque lon utilise tableau.insert(0, valeur), mais le coût est néanmoins là. Le fait quil faille recopier \(N-1\) éléments pour une liste de taille \(N\) ne change rien au fait que le coût est bien linéaire.

    • Retirer un élément à une position quelconque du tableau: en général on na pas besoin de réserver un nouvel emplacement en mémoire, mais il faut néanmoins déplacer tous les éléments à droite de lélément supprimé pour boucher le trou: dans le pire des cas, on déplace \(N-1\) éléments, où \(N\) est la taille du tableau. On a donc bien un coût linéaire.

    Voici encore une mise en évidence de ce quil est nécessaire de faire, toujours avec python tutor. On observe bien le coût proportionnel à la longueur de la liste.

  • Un algorithme à un coût quadratique lorsque le nombre dopérations nécessaires à son exécution est proportionnel au carré de la taille des données. Il faut retenir que lorsque lon double la taille des données pour un tel algorithme, le temps dexécution est multiplié par \(2^2 = 4\); de même, si on multiplie la taille des données par 3, le temps dexécution est multiplié par 9.

    Les seuls algorithmes quadratiques rencontrés pour linstant sont les algorithmes de tri par insertion et tri par sélection étudiés en première. Aucun des algorithmes des interfaces des tableaux ou des listes ne nécessitent un coût quadratique.

Attention, le coût dun des algorithmes définissant linterface dun tableau ou dune liste dépend de limplémentation particulière de cette structure de donnée. Il existe presque tout le temps de multiples façons de définir une structure de donnée afin quelle satisfasse à une interface donnée, et les coûts peuvent être très variables dune opération à lautre.

Une nouvelle implémentation du type abstrait liste: la liste chaînée

Les listes en python sont en fait implémentées comme des tableaux dont la taille peut être modifiée dynamiquement (mais avec un coût caché, comme évoqué précédemment).

Il existe dautres manières dimplémenter les listes, avec des coûts différents. La liste chaînée en est une des nombreuses possibilités.

Interface dune liste chaînée

Une liste chaînée est une succession de cellules, chacune contenant à la fois une des valeurs de la liste, et un pointeur vers la cellule suivante:

Liste chaînée

Nous avons ici une variable L1 pointant sur une première cellule contenant la valeur 12, elle-même pointant sur la seconde cellule contenant la valeur 99, etc. La dernière cellule ne pointe sur rien, marquant ainsi la fin de la liste chaînée.

On peut représenter une liste chaînée vide de la manière suivante:

Liste chaînée vide

Comme nous allons le voir très bientôt, la liste chaînée est une implémentation du type liste optimisée pour linterface suivante:

  • Placer et enlever un élément en tête de liste;
  • Parcourir les éléments de la liste de manière séquentielle;
  • Déterminer si une liste est vide ou non;

Dautres opérations de linterface dune liste (longueur, insertion à une position quelconque, accéder ou modifier un élément de rang quelconque, etc) sont réalisables, en utilisant linterface basique ci-dessus. Le coût est cependant en général plus important.

Implémentation(s) dune liste chaînée

Comme son nom lindique, la liste chaînée est implémentée à laide dune séquence déléments composés de deux composantes:

  • La valeur de cette élément;
  • Un pointeur vers lélément suivant;

Dans ce cours, nous appelerons un tel élément une cellule. Il existe deux manière simples de représenter une cellule en python: un tuple (valeur, pointeur) ou bien un tableau [valeur, pointeur]. Dans le premier cas, on aura une liste immuable (qui ne peut pas être modifiée une fois créée), dans le second une liste variable (dont la structure et/ou les valeurs peuvent être modifiés après la création). Les deux possibilités ont leurs avantages et leurs inconvénients, comme nous le verrons dans les exercices.

Voici une implémentation possible dune liste chaînée (immuable) en python:

def liste_vide():
   """
   Renvoie une liste vide.
   """

   return None # On décide de représenter la liste vide par None

def cellule(valeur, suivante):
   """
   Crée une nouvelle cellule, composée d'une 'valeur' et d'un pointeur vers
   la cellule 'suivante'.
   """

   # return [valeur, suivante] pour une cellule variable plutôt qu'immuable.
   return (valeur, suivante)

def tête(une_cellule):
   """
   Renvoie la valeur (i.e. le premier élément) d'une cellule.
   """

   return une_cellule[0]

def queue(une_cellule):
   """
   Renvoie la cellule suivante (c'est-à-dire celle sur lequel pointe le second élément
   de la cellule).
   """

   return une_cellule[1]

def est_vide(liste_chaînée):
   """
   Renvoie un booléen indiquant si la liste est vide ou non.
   """
   return liste_chaînée is None

On peut alors créer une liste chaînée représentant la liste "N", "S", "I" par la syntaxe (un peu lourde, mais nous ferons mieux en TD) suivante:

>>> l1 = cellule("N", cellule("S", cellule("I", liste_vide())))
>>> l1
("N", ("S", ("I", None)))

Remarquons quil serait tout à fait possible de créer directement la liste chaînée par la syntaxe:

>>> ("N", ("S", ("I", None)))
("N", ("S", ("I", None)))

Cependant, cest une très mauvaise idée: ce faisant, on intégrerait dans nos futurs algorithmes les détails de limplémentation de notre liste chaînée (notamment le fait quelle soit immuable ou bien variable), nous compliquant par la même toute velléité de modifications futures de ces détails. Cest pour cette raison que les informaticiens professionnels se réfugient toujours derrière une interface: que celle-ci soit fonctionnelle comme ici, ou bien utilisant de la programmation orientée objet (comme nous le verrons au chapitre suivant), elle permet de rendre possible toute modification de limplémentation qui ne changerait pas linterface elle-même, offrant par la même une grande souplesse et une grande sécurité au programmeur.

Il est très intéressant dexaminer ce que donne python tutor sur cet exemple. Un point très important: la liste chaînée est crée à partir du dernier élément, et on enchaîne les éléments précédents dans lordre inverse. On retrouvera ce schéma dans la plupart des algorithmes sur les listes chaînées.

Complexité des opérations de base

Comme on peut le constater, aucune des fonctions précédentes ne comporte de boucle: le coût sera alors constant.

Insistons sur un point particulier de cette affirmation: ajouter une nouvelle cellule en tête de liste est à coût constant: il suffit de créer cette cellule (ce qui prend un peu de temps, mais ce temps ne dépend pas du nombre de cellules déjà créées auparavant).

Cela est à mettre en contraste avec lopération équivalente sur les tableaux/liste de python, qui nécessite de décaler toutes les valeurs suivantes lorsquon lon ajoute ou élimine lélément de tête, induisant un coût linéaire (voir le lien python tutor donné un peu plus tôt dans ce cours).

Cependant, nallons pas croire que la liste chaînée est le nouvel eldorado qui va remplacer les tableaux/listes de python: dautres opérations sont nettement plus coûteuses sur les listes chaînées que sur ces derniers, comme nous allons le voir dès à présent. Tout nest que question de compromis, et le fait dutiliser une liste chaînée en lieu et place dun tableau/liste de python dépend en fait du contexte et de lalgorithme que lon souhaite implémenter.

Utilisation dune liste chaînée

Les autres opérations de linterface dune liste peuvent être implémentées pour les listes chaînées en utilisant linterface de base évoquée plus haut.

Longueur dune liste chaînée

Connaître la longueur dune liste chaînée nécessite den parcourir tous les éléments jusquau dernier, car cette longueur nest stockée nulle part en mémoire dans notre implémentation. Le coût sera alors linéaire (alors que pour les tableaux/listes de python, le coût est constant).

On propose deux implémentations de cette fonction: lune sera récursive, lautre utilisera un algorithme itératif (utilisant classiquement une boucle). On va voir que les listes chaînées sont une structure de donnée très adaptés aux algorithmes récursifs, car la définition même dune liste chaînée est récursive: une liste chaînée est une cellule (la tête de liste) ayant une valeur et pointant sur une liste chaînée (appelée queue de liste). Même la dernière cellule dune liste chaînée satisfait à cette définition récurrente, puisquelle pointe sur la liste vide.


# On apposera toujours le suffixe _rec pour désigner une fonction récursive, afin de les 
# distinguer des fonctions itératives.
def longueur_rec(liste_chaînée):
   """
   Renvoie la longueur d'une liste chaînée. La liste vide a une longueur nulle.
   """

   if est_vide(liste_chaînée):
      # Condition d'arrêt
      return 0
   else:
      # Appel récursif
      return 1 + longueur_rec(queue(liste_chaînée))

def longueur(liste_chaînée):
   """
   Renvoie la longueur d'une liste chaînée. La liste vide a une longueur nulle.
   """

   position = liste_chaînée
   longueur = 0
   while not est_vide(position):
      position = queue(position)
      longueur += 1 # On incrémente longueur de 1

   return longueur

Vous pouvez tester ces deux implémentations à laide de python tutor.

Remarque importantes:

  • Afin de ne pas alourdir la compréhension des algorithmes, on a fait le choix ici de ne pas utiliser sur python tutor les fonctions définissant linterface dune liste chaînée (par exemple, on a remplacé est_vide(liste) par liste is None). En général, cest une très mauvaise idée de faire cela, car on ne respecte pas le principe primordial de toujours passer par linterface de notre structure de données, gravant dans le marbre (ou plutôt, nos algorithmes) les détails de limplémentation. Il serait alors très difficile de modifier cette structure après coup, si cela savérait nécessaire.

    Il sagit ici dun choix conscient, et nous nous astreindrons par contre en dehors de lutilisation de python tutor à toujours accéder à une structure de donnée à partir des fonctions définissant son interface (ou bien à partir de la structure dobjets lorsque nous aurons étudié cette notion au prochain chapitre).

  • La boucle while qui permet de parcourir la liste chaînée du premier élément au dernier est fondamentale: nous la retrouverons dans la plupart des algorithmes itératifs sur les listes chaînées. Elle porte sur une variable qui prend successivement pour valeur toutes les cellules de la liste.
  • Remarquons quil est très difficile (mais pas impossible) de parcourir une liste chaînée à lenvers: cette structure de donnée est clairement optimisée pour un parcours de gauche à droite. La structure de liste doublement chaînée permet de palier à cet inconvénient, au prix dune consommation accrue de la mémoire et dune implémentation des opérations de base plus délicate. Nous ne létudierons pas cette année.

Concaténation dune liste chaînée

Lalgorithme de concaténation est un peu plus délicat à réaliser. Il sagit, à partir de deux listes chaînées, den créer une troisième qui sera le résultat de la concaténation des deux premières.

Lalgorithme récursif est relativement simple. On va raisonner sur la première liste:

  • Si la première liste est vide, la concaténation est égale à la seconde;
  • Sinon, on concatène la queue de la première liste à la seconde liste (récursivement), puis on ajoute simplement une nouvelle cellule correspondant à la tête de la première liste au résultat.
def concaténation_rec(l1, l2):
   """
   Renvoie la concaténation de l1 et l2 (qui correspond à l1 + l2 avec les listes python).
   l1 et l2 ne sont pas modifiées par cette opération.
   """

   if est_vide(l1):
      # Condition d'arrêt
      return l2
   else:
      # Appel récursif
      t = tête(l1)
      q = queue(l1)
      return cellule(t, concaténation_rec(q, l2))

Nous ne donnerons pas dalgorithme itératif ici, car il nécessite de parcourir la première liste du dernier élément au premier. La méthode la plus simple pour réaliser cela est de procéder récursivement, ce qui tue lintérêt dun algorithme itératif. Lalternative est de stocker les éléments de la première liste lors dun parcours dans le sens direct, à laide par exemple dun tableau/liste python. Il est alors possible de parcourir aisément cette liste python dans le sens inverse. Nous verrons plus en détail ce genre dalgorithme lorsque nous étudierons la structure de pile (dans un prochain chapitre).

Le coût de lalgorithme récursif est linéaire: le temps dexécution est proportionnel à la taille de la première liste. Notons que la seconde liste ninflue pas sur le coût.

Évidemment, vous êtes invité à visualiser cela avec python tutor.

À la fin de lexécution de cet algorithme, on constate un phénomène très important:

  • Les listes l1 et l2 nont effectivement pas été modifiées par la concaténation.
  • La liste résultat partage une partie de son contenu avec l2. Cela permet doptimiser lusage de la mémoire, mais est très dangereux si on utilise des listes variables (où les cellules sont implémentées à laide de tableaux) et que lon samuse à modifier la structure des listes après leur création. Nous verrons les conséquence de ces choix en exercice.

    Retenez que, à condition dutiliser des listes immuables (avec des tuples par exemple), ce partage de donnée ne présente que des avantages et aucun inconvénient.

Retournement dune liste chaînée

Retourner une liste ne fait pas partie de son interface fondamentale, mais cest un problème néanmoins intéressant à implémenter.

Contrairement à la concaténation pour laquelle lalgorithme itératif souffrait dune difficulté insurmontable (pour linstant), le fait de devoir créer une liste «à lenvers» va nous obliger à parcourir notre liste dans le sens contraire de celui de lalgorithme de concaténation, cest-à-dire le sens direct: les listes chaînées sont parfaitement adaptées à cela.

def retournement(liste):
   résultat = liste_vide()
   while not est_vide(liste):
      résultat = cellule(tête(liste), résultat)
      liste = queue(liste)
   return résultat

Lalgorithme récursif nest pas trop compliqué à implémenter si on sautorise à utiliser la fonction de concaténation précédente:

def retournement_rec(liste):
   if est_vide(liste):
      # Condition d'arrêt
      return liste
   else:
      dernier = cellule(tête(liste), liste_vide())
      return concaténation_rec(retournement_rec(queue(liste)), dernier)

Examinez le comportement de ces deux algorithmes à laide de python tutor.

  • Lalgorithme itératif a un coût linéaire, puisquil nécessite un unique parcours de la liste.
  • Lalgorithme récursif par contre aura ici un coût quadratique: il nécessite à la fois un parcours des \(N\) éléments de la liste, mais pour chacun deux, un appel à la fonction de concaténation sur le reste de la liste. Le coût total sera alors

    \[ N + (N-1) + (N-2) + \cdots + 3 + 2 + 1\]

    dont on peut montrer en mathématique quil est égal à \(\frac{N(N+1)}2\). En développant cette expression on aura un terme en \(\frac12N^2\), ce qui rend le coût quadratique: cette version récursive nest pas très performante. Sur une liste de taille 1000, on aura grosso modo 500000 opérations, ce qui est prohibitif.

    On verra en TD quil est possible décrire une version récursive ayant un coût linéaire, comme la version itérative, au prix dune implémentation un tout petit peu plus complexe.