Série 5 – Listes : corrigé

La méthode set est triviale à définir pour les tableaux-listes puisqu'il suffit, après avoir vérifié la validité de l'index, de modifier l'entrée correspondante du tableau sous-jacent.

public void set(int i, E newElem) {
    checkIndex(i);
    array[i] = newElem;
}

La principale difficulté de la méthode toString est d'éviter de placer une virgule après le dernier élément. Pour ce faire, on peut simplement utiliser la méthode hasNext de l'itérateur à l'intérieur de la boucle de parcours des éléments, après avoir obtenu le prochain élément au moyen de next.

Pour construire la chaîne de caractère, on utilise — comme le suggère l'énoncé — le bâtisseur de chaîne fourni par Java, StringBuilder. Ce bâtisseur joue exactement le même rôle que les bâtisseurs du projet, c-à-d qu'il permet de construire petit-à-petit une instance d'une classe immuable, ici String. A noter que la méthode que nous appelons habituellement build dans le projet est simplement toString pour ce bâtisseur.

@Override
public String toString() {
    StringBuilder b = new StringBuilder("[");
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        b.append(it.next());
        if (it.hasNext())
            b.append(",");
    }
    return b.append("]").toString();
}

Cette méthode toString n'utilise qu'une seule méthode de la classe qui la contient, à savoir iterator. Dès lors, elle est utilisable pour n'importe quelle liste, et même n'importe quelle classe implémentant l'interface Iterable.

La manière la plus simple de savoir s'il est autorisé d'appeler la méthode remove consiste — comme suggéré dans l'énoncé — à ajouter un champ booléen nommé canRemove à l'itérateur. Ce champ est vrai si et seulement si il est autorisé d'appeler remove.

private static final class ALIterator<E> implements Iterator<E> {
    private final ArrayList<E> list;
    private int index;
    private boolean canRemove;

    public ALIterator(ArrayList<E> list) {
        this.list = list;
        this.index = 0;
        this.canRemove = false;
    }

    @Override
    public boolean hasNext() {
        return index < list.size();
    }

    @Override
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        canRemove = true;
        return list.get(index++);
    }

    @Override
    public void remove() {
        if (! canRemove)
            throw new IllegalStateException();
        list.remove(index - 1);
        canRemove = false;
    }
}

La méthode set des listes chaînées n'est pas beaucoup plus difficile à définir que celle des tableaux-listes, étant donné que la méthode nodeAtIndex permet d'obtenir un nœud à partir de son index.

public void set(int i, E newElem) {
    checkIndex(i);
    nodeAtIndex(i).value = newElem;
}

L'itérateur sur les listes chaînées ressemble à celui sur les tableaux-listes, si ce n'est qu'au lieu de représenter la position de l'itération au moyen d'un index, il utilise un nœud.

Au même titre que l'itérateur sur les tableaux-listes initialisait son index à 0 pour référencer le premier élément de la liste, l'itérateur sur les listes chaînées référence initialement le successeur du nœud d'en-tête. En effet, ce nœud est le premier à contenir une information utile.

Pour passer à l'élément suivant, cet itérateur se contente de suivre le lien du nœud courant vers son successeur.

Pour détecter la fin de l'itération, cet itérateur compare le nœud courant avec le nœud d'en-tête, et s'arrête (dans le sens où sa méthode hasNext retourne faux) dès que ce dernier est rencontré.

Finalement, pour savoir s'il est valide d'appeler remove, cet itérateur utilise exactement la même technique que l'itérateur sur les tableaux-listes. Pour effectuer la suppression, la méthode remove de l'itérateur appelle simplement la méthode privée removeNode de la classe LinkedList, qui est également utilisée par la méthode remove de cette classe-là.

private static final class LLIterator<E> implements Iterator<E> {
    private final LinkedList<E> list;
    private Node<E> next;
    private boolean canRemove;

    public LLIterator(LinkedList<E> list) {
        this.list = list;
        this.next = list.head.succ;
        this.canRemove = false;
    }

    @Override
    public boolean hasNext() {
        return next != list.head;
    }

    @Override
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        canRemove = true;
        E value = next.value;
        next = next.succ;
        return value;
    }

    @Override
    public void remove() {
        if (! canRemove)
            throw new IllegalStateException();
        list.removeNode(next.pred);
        canRemove = false;
    }
}

La méthode toString est exactement la même que celle pour les tableaux-listes. Idéalement, elle devrait d'ailleurs être placée dans une super-classe commune du même genre que la classe AbstractList de la bibliothèque Java.