Implémentation d'un séquence impérative sous forme de liste

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.

Pseudo-code

On suppose que l'objet en-tête accepte les opérations suivantes :

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)

Exemple de code