Listes simplement chaînées

Une liste est idéale pour l'accumulation d'éléments dont le nombre est initialement inconnu. Le cas typique est la lecture à partir d'un flot. Une erreur classique de débutant est d'accumuler à la fin de la liste, comme ceci (à ne pas faire) :

(with-open-file (stream "data")
  (do ((acc nil)
       (val (read stream nil) (read stream nil)))
      ((null val) acc)
    (setf acc (append acc (list val)))))

Le problème principal de cette version est que sa complexité est $O(n^2)$ où $n$ est le nombre d'éléments lus. Ceci est dû au fait que la complexité de append est $O(m)$ où $m$ est la taille de la liste et que l'opération est effectuée $n$ fois. De plus, avec append, la liste courante est copiée à chaque appel, ce qui génère $O(n^2)$ cellules à récupérer par le ramasse-miettes.

Pour éviter ces deux problèmes, il faut accumuler au début de la liste, ce qui construit la liste en sens inverse. Pour finir, on renverse la liste. Ainsi, ajouter un élément ne coûte que $O(1)$. Ajouter $n$ éléments coûte donc $O(n)$ ainsi que le renversement de la liste, ce qui donne un coût total de $O(n)$. Mais le renversement génère toujours $n$ cellules à récupérer. Ce problème peut être évité si l'on utilise nreverse (la version destructive) au lieu de reverse. Cela fonctionne, car aucun partage des cellules n'est possible. La version idiomatique utilise push et nreverse comme ceci :

(with-open-file (stream "data")
  (do ((acc nil)
       (val (read stream nil) (read stream nil)))
      ((null val) (nreverse acc))
    (push val acc)))

Avec une liste simplement chaînée, il est possible de rajouter des éléments à la fin avec une complexité de $O(1)$ à condition de maintenir un pointeur sur la dernière cellule. Les opérations habituelles (ajouter au début, supprimer au début) sont toujours possibles avec une complexité de $O(1)$. Voici une première version pour laquelle nous allons maintenir deux variables globales *start* et *end*, valant initialement nil. La seule différence avec la liste normale est que le pointeur sur le dernier élément doit être maintenu, ce qui complique toutes les opérations. Voici l'opération pour ajouter en début de liste :

(defun add-front (x)
  (if (null *start*)
      (setf *start* (list x)
            *end* *start*)
      (push x *start*)))

Dans cette version, nous avons utilisé l'opérateur if au lieu de cond. En effet, setf permettant d'effectuer plusieurs affectations séquentiellement, un progn n'est pas nécessaire. Par contre la disymétrie résultant de l'utilisation de setf et de list dans la partie alors et de push dans la partie sinon n'est pas très élégante. Voici une version améliorée :

(defun add-front (x)
  (push x *start*)
  (when (null *end*)
    (setf *end* *start*)))

Cette version est meilleure pour plusieurs raisons :

• elle est plus brève,
• la disymétrie a disparu,
• l'opération principale est faite au début,
• l'opération principale est faite à un seul endroit.

L'opération suivante permet d'ajouter un élément à la fin :

(defun add-end (x)
  (if (null *end*)
      (setf *start* (list x)
            *end* *start*)
      (setf (cdr *end*) (list x)
            *end* (cdr *end*))))

Voici une première version de l'opération de suppression d'un élément en début de liste :

(defun remove-front ()
  (assert *start*)
  (if (null (cdr *start*))
      (setf *start* nil
            *end* nil)
      (pop *start*)))

Cette version peut être améliorée de la même manière que add-front :

(defun remove-front ()
  (assert *start*)
  (pop *start*)
  (when (null *start*)
    (setf *end* nil)))

Finalement, les deux opérations suivantes permettent de récupérer respectivement le premier et le dernier élément :

(defun first-elem ()
  (assert *start*)
  (car *start*))

(defun last-elem ()
  (assert *end*)
  (car *end*))

Mais les deux opérations d'insertion sont compliquées par le test qui vérifie si la liste est vide et l'opération de suppression doit vérifier si, après la suppression, la liste est vide. Ce test pose problème surtout pour la performance, mais le code est aussi plus compliqué. L'utilisation d'une sentinelle peut améliorer considérablement la situation. L'idée est de maintenir une cellule de plus dans la liste. Cette cellule fait physiquement partie de la liste, mais logiquement elle n'existe pas. La liste vide sera donc initialisée comme ceci :

(setf *start* (list nil)
      *end* *start*)

Ensuite, il faut décider si la cellule supplémentaire sera au début ou à la fin de la liste. Nous avons choisi le début. La convention est donc que *start* pointe sur la cellule avant celle contenant le premier élément et *end* pointe sur la cellule contenant le dernier élément, s'il y en a un.

Les opérations pour récupérer le premier et le dernier élément deviennent alors :

(defun first-elem ()
  (assert (cdr *start*))
  (cadr *start*))

(defun last-elem ()
  (assert (cdr *start*))
  (car *end*))

Pour ajouter un élément au début de la liste, il faut maintenant faire attention. Le nouvel élément doit prendre la place du car de la première cellule (la sentinelle) et une nouvelle sentinelle doit être ajoutée :

(defun add-front (x)
  (setf (car *start*) x)
  (push nil *start*))

Le cas spécial a disparu, ce qui simplifie le code. La fonction pour ajouter un élément à la fin de la liste en est considérablement simplifiée :

(defun add-end (x)
  (push x (cdr *end*))
  (pop *end*))

Finalement, voici la fonction pour supprimer l'élément du début de la liste :

(defun remove-front ()
  (assert (cdr *start*))
  (pop *start*))