Fonctions de base sur les listes

Chaque fonction récursive suit la définition d'une liste : une liste vide (base), ou un premier élément suivi d'un reste (hérédité).

static int somme(Liste l) {
    if (vide(l)) return 0;                       // somme(()) = 0
    return premier(l) + somme(reste(l));
}
static int sommeIt(Liste l) {
    int s = 0;
    for (Liste c = l; !vide(c); c = reste(c)) s = s + premier(c); // s = somme des éléments vus
    return s;
}
static boolean dans(int x, Liste l) {
    if (vide(l)) return false;                   // () ne contient rien
    return x == premier(l) || dans(x, reste(l));
}
static boolean dansIt(int x, Liste l) {
    for (Liste c = l; !vide(c); c = reste(c)) if (premier(c) == x) return true;
    return false;
}
static Liste copie(Liste l) {
    if (vide(l)) return null;
    return new Liste(premier(l), copie(reste(l)));
}
static Liste inverse(Liste l) {
    Liste r = null;                              // r = miroir de la partie déjà parcourue
    for (Liste c = l; !vide(c); c = reste(c)) r = new Liste(premier(c), r);
    return r;
}

Pour inverse, l'astuce est l'accumulateur $r$ : ajouter un élément en tête coûte un temps constant, donc la boucle est en $\Theta (n)$. La version naïve « inverser le reste puis ajouter le premier en fin de liste » parcourt à chaque étape la liste déjà construite : elle est en $\Theta (n^2)$.

l = (0 2 1 2)
somme = 5 / 5
dans(1) = true, dans(5) = false
inverse = (2 1 2 0), copie = (0 2 1 2)