Listes Chaînées

Traditionnellement, la majorité des dialectes de Lisp ont été implantés avec des listes chainées. D'ailleurs, s'il fallait décrire le fonctionnement des fonctions les plus illustres du langage: car et cdr, la façon la plus simple serait de le faire de la façon suivante:

Si l'une des principales qualités de ce type de conteneur est la possibilité d'insérer des éléments en temps constant, l'un de ses défauts est la difficulté d'accéder un élément particulier, puisqu'il faut chaque fois faire un parcours depuis le début pour se positionner sur la case voulue.

Or nombre d'algorithmes requiert un accès direct aux éléments pour fonctionner de façon efficace, comme la multiplication de matrices par exemple. Cependant, les tableaux présentent quelques défauts. Par exemple, l'insertion d'un élément au milieu d'un tableau implique le déplacement des éléments suivants pour laisser une cellule libre. De plus, si l'opérateur car peut être implanté de façon direct en accédant à l'élément en position 0, l'implantation de cdr exige un peu plus de réflexion.

En effet, si l'on veut conserver une aussi grande efficacité qu'avec les listes chaînées, on ne peut se contenter de renvoyer de créer une nouvelle liste qui contiendra tous les éléments à partir de la position 1. Dans un parcours de liste, ce genre de manipulation s'avérerait horriblement coûteux.

Double Pointeurs

Il est clair qu'une implantation directe d'une table en C++, ne donnera pas le résultat escompté.