Une liste, ou liste chaînée est un type concret implémenté sous la forme de suite de cellules élémentaires ou paires. Une cellule est une structure contenant deux champs couramment appelés la tête et la queue. Une liste est donc une séquence.
Alors qu'il est possible de considérer une cellule comme un type abstrait nous préférons le considérer comme une simple structure dont la valeur des champs sont directement modifiables et récupérables. Ainsi, étant donnée une cellule c, on écrit c.tête pour le champs tête et c.queue pour le champs queue. Cette notation est valable à la fois dans une expression normale et comme destination d'une affectation.
À la possibilité de modifier et de récupérer la valeur d'un champ d'une cellule, il faut rajouter la possibilité de créer une nouvelle cellule à partir de deux valeurs existantes. Cette opération s'appelle traditionnellement cons.
Afin d'utiliser des cellules élémentaires pour créer une liste, il suffit maintenant de les chaîner par le champ queue et d'utiliser le champ tête de chaque cellule de la chaîne pour tenir les éléments de la liste.
Il nous reste de représenter la liste vide, à savoir la liste sans aucun élément. Cela se fait traditionnellement par une valeur spéciale, que nous allons appeler NIL. Le champ queue de la dernière cellule d'une liste non vide contient donc cette valeur.