Il est possible d'implémenter une séquence fonctionnelle sous la forme de liste chaînée, mais afin de préserver l'identité de la séquence lors d'une insertion ou d'une suppression en début de la séquence, il faut introduire un objet en-tête.
On suppose que la liste a au moins autant d'éléments que la position
liste insérer-liste(objet obj, liste l, entier position) si position = 0 alors renvoyer cons(obj, l) sinon queue(l) <- insérer-liste(obj, queue(l), position - 1) renvoyer l
void insérer(objet obj, séquence s, entier position) assert(position <= taille(s)) éléments(s) <- insérer-liste(obj, éléments(s), position) taille(s) <- taille(s) + 1
liste supprimer-liste(liste l, entier position) si position = 0 alors renvoyer queue(l) sinon queue(l) <- supprimer-liste(queue(l), position - 1) renvoyer l
void supprimer(sequence s, entier position) assert(position < taille(s)) éléments(s) <- supprimer-liste(éléments(s), position) taille(s) <- taille(s) - 1
objet récupérer-liste(liste l, entier position) si position = 0 alors renvoyer tête(l) sinon renvoyer récupérer(queue(l), position - 1)
récupérer(séquence s, entier position) assert(position < taille(s) renvoyer récupérer-liste(éléments(s), position)
Versions itératives avec sentinelle (la première cellule de la liste est la sentinelle) :
insérer-liste(objet obj, liste l, entier position) répéter position fois l <- queue(l) queue(l) <- cons(obj, queue(l))
void insérer(objet obj, séquence s, entier position) assert(position <= taille(s)) insérer-liste(obj, éléments(s), position) taille(s) <- taille(s) + 1
supprimer-liste(objet obj, liste l, entier position) répéter position fois l <- queue(l) queue(l) <- queue(queue(l))
void supprimer(sequence s, entier position ) assert(position < taille(s)) supprimer-liste(éléments(s), position) taille(s) <- taille(s) - 1
objet récupérer-liste(liste l, entier position) répéter position fois l <- queue(l) renvoyer tête(queue(l))
récupérer(séquence s, entier position) assert(position < taille(s) renvoyer récupérer-liste(éléments(s), position)