Cours

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 d’un 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:

L’interface d’un tableau #

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

L'interface d’une structure de donnée est l’ensemble des opérations de base permettant d’interagir avec celle-ci. Le programmeur peut (et doit utiliser exclusivement) les opérations définies par l’interface pour interagir avec une structure de donnée.

  • il s’agit d’un ensemble de données homogènes (c’est-à-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 d’un 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 n’importe 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 qu’implé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]
    
  • À l’inverse, on peut retirer le dernier élément du tableau (s’il existe):

    >>> tableau.pop()
    34
    >>> tableau
    [-1, 1, 2, 3, 5, 8, 13, 21]
    
  • Mieux encore: il est possible d’insé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 l’interface d’un tableau, mais plutôt d’une liste. Les tableaux du langage python sont en fait un type hybride ayant à la fois les caractéristiques d’un tableau mais aussi d’une liste. D’ailleurs, en python, les tableaux s’appellent 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 d’utilisation en tant que tableau pur, ou bien en tant que liste pure.

Examinons à présent l’interface d’une liste.

L’interface d’une liste #

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

  • il s’agit d’un ensemble de données homogènes (c’est-à-dire du même type) rangée de manière séquentielle;
  • La taille d’une, encore appelée longueur, est variable: elle peut changer au cours de la durée de vie de la liste;
  • Il est possible d’insérer et de supprimer des éléments en tête de liste;
  • Il est possible d’insérer et de supprimer des éléments en queue de liste;
  • Il est possible d’insérer et de supprimer des éléments à n’importe quelle position de la liste;
  • Il est possible de parcourir tous les éléments de la liste, du premier jusqu’au 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é à l’exécution (qui est imperceptible pour des tableaux/listes ne contenant que peu de données, mais devient non négligeable lorsque l’on travaille sur des données pouvant atteindre plusieurs mégaoctets, voire gigaoctets).

Coûts cachés de l’utilisation des tableaux/listes #

Le coût d’un 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 l’indique, un nombre constant d’opérations, indépendemment de la taille des données en entrée.

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

    • Lire ou changer une valeur de rang $i$ dans un tableau;

      Il suffit à l’interpré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 d’un tableau;

      En python la taille du tableau est stockée conjointement aux valeurs qu’il contient, il suffit dont de lire le contenu d’une variable (cachée pour l’utilisateur);

    • 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 d’opérations nécessaires à son exécution est proportionnel à la taille des données en entrée. La constante de proportionnalité n’est 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 d’exécution: c’est ce que signifie proportionnalité.

    Des exemples d’algorithmes à 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 l’intégralité du tableau (d’où le coût linéaire), avec éventuellement un décalage.

      Examinez ce code python tutor qui met artificiellement en évidence les opérations nécessaires pour «ajouter» un élément en tête d’un tableau. Tout ceci est bien évidemment invisible lorsque l’on utilise tableau.insert(0, valeur), mais le coût est néanmoins là. Le fait qu’il 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 n’a 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 qu’il 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 d’opérations nécessaires à son exécution est proportionnel au carré de la taille des données. Il faut retenir que lorsque l’on double la taille des données pour un tel algorithme, le temps d’exécution est multiplié par $2^2 = 4$; de même, si on multiplie la taille des données par 3, le temps d’exécution est multiplié par 9.

    Les seuls algorithmes quadratiques rencontrés pour l’instant 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 d’un des algorithmes définissant l’interface d’un tableau ou d’une liste dépend de l’implé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 qu’elle satisfasse à une interface donnée, et les coûts peuvent être très variables d’une opération à l’autre.

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 d’autres manières d’implémenter les listes, avec des coûts différents. La liste chaînée en est une des nombreuses possibilités.

Interface d’une 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 l’interface 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;

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

Implémentation(s) d’une liste chaînée #

Comme son nom l’indique, la liste chaînée est implémentée à l’aide d’une 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 d’une 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 qu’il 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, c’est une très mauvaise idée: ce faisant, on intégrerait dans nos futurs algorithmes les détails de l’implémentation de notre liste chaînée (notamment le fait qu’elle soit immuable ou bien variable), nous compliquant par la même toute velléité de modifications futures de ces détails. C’est 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 l’implémentation qui ne changerait pas l’interface elle-même, offrant par la même une grande souplesse et une grande sécurité au programmeur.

Il est très intéressant d’examiner 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 l’ordre 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 l’opération équivalente sur les tableaux/liste de python, qui nécessite de décaler toutes les valeurs suivantes lorsqu’on l’on 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, n’allons pas croire que la liste chaînée est le nouvel eldorado qui va remplacer les tableaux/listes de python: d’autres 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 n’est que question de compromis, et le fait d’utiliser une liste chaînée en lieu et place d’un tableau/liste de python dépend en fait du contexte et de l’algorithme que l’on souhaite implémenter.

Utilisation d’une liste chaînée #

Les autres opérations de l’interface d’une liste peuvent être implémentées pour les listes chaînées en utilisant l’interface de base évoquée plus haut.

Longueur d’une liste chaînée #

Connaître la longueur d’une liste chaînée nécessite d’en parcourir tous les éléments jusqu’au dernier, car cette longueur n’est 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: l’une sera récursive, l’autre 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 d’une 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 d’une liste chaînée satisfait à cette définition récurrente, puisqu’elle 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 à l’aide 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 l’interface d’une liste chaînée (par exemple, on a remplacé est_vide(liste) par liste is None). En général, c’est une très mauvaise idée de faire cela, car on ne respecte pas le principe primordial de toujours passer par l’interface de notre structure de données, gravant dans le marbre (ou plutôt, nos algorithmes) les détails de l’implémentation. Il serait alors très difficile de modifier cette structure après coup, si cela s’avérait nécessaire.

    Il s’agit ici d’un choix conscient, et nous nous astreindrons par contre en dehors de l’utilisation de python tutor à toujours accéder à une structure de donnée à partir des fonctions définissant son interface (ou bien à partir de la structure d'objets 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 qu’il est très difficile (mais pas impossible) de parcourir une liste chaînée à l’envers: 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 d’une consommation accrue de la mémoire et d’une implémentation des opérations de base plus délicate. Nous ne l’étudierons pas cette année.

Concaténation d’une liste chaînée #

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

L’algorithme 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 d’algorithme 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 l’intérêt d’un algorithme itératif. L’alternative est de stocker les éléments de la première liste lors d’un parcours dans le sens direct, à l’aide par exemple d’un 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 d’algorithme lorsque nous étudierons la structure de pile (dans un prochain chapitre).

Le coût de l’algorithme récursif est linéaire: le temps d’exécution est proportionnel à la taille de la première liste. Notons que la seconde liste n’influe pas sur le coût.

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

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

  • Les listes l1 et l2 n’ont effectivement pas été modifiées par la concaténation.

  • La liste résultat partage une partie de son contenu avec l2. Cela permet d’optimiser l’usage de la mémoire, mais est très dangereux si on utilise des listes variables (où les cellules sont implémentées à l’aide de tableaux) et que l’on s’amuse à modifier la structure des listes après leur création. Nous verrons les conséquence de ces choix en exercice.

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

Retournement d’une liste chaînée #

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

Contrairement à la concaténation pour laquelle l’algorithme itératif souffrait d’une difficulté insurmontable (pour l’instant), le fait de devoir créer une liste «à l’envers» va nous obliger à parcourir notre liste dans le sens contraire de celui de l’algorithme de concaténation, c’est-à-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

L’algorithme récursif n’est pas trop compliqué à implémenter si on s’autorise à 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 à l’aide de python tutor.

  • L’algorithme itératif a un coût linéaire, puisqu’il nécessite un unique parcours de la liste.

  • L’algorithme 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 d’eux, 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 qu’il 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 n’est 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 qu’il est possible d’écrire une version récursive ayant un coût linéaire, comme la version itérative, au prix d’une implémentation un tout petit peu plus complexe.