Abstraction du parcours dans les conteneurs

La manipulation de structures de données hétérogènes, telles que les tableaux contigus ou les listes chaînées, impose souvent d'adapter la logique de parcours. Sans une couche d'abstraction, le code client deviendrait fortement couplé à l'implémentation interne, nuisant à la maintenabilité et à la réutilisabilité. Le langage Java résout cette problématique en imposant des contrats communs via ses interfaces de collections.

Les classes concrètes ArrayList et LinkedList implémentent toutes deux l'interface List, elle-même dérivée de Collection. Cette hiérarchie garantit que les opérations fondamentales (add, remove, get, size) restent identifiables quel que soit le mécanisme de stockage sous-jacent. En programmant uniquement contre ces interfaces, le développeur peut intervertir les implémentations sans impacter la logique métier.

Le contrat d'itération uniforme

Au-delà des manipulations élémentaires, le parcours des éléments doit suivre un standard commun. C'est ici qu'intervient l'interface Iterable. En exigeatn la méthode iterator(), elle permet à tout conteneur de fournir un curseur de navigation indépendant de sa structure interne. L'interface Iterator expose ensuite trois opérations fondamentales :

• hasNext() : vérifie la présence d'éléments supplémentaires.
• next() : avance le curseur et retourne la valeur courante.
• remove() : supprime le dernier élément retourné du conteneur source.

Cette séparation des responsabilités permet d'écrire des boucles universelles :

Collection<String> repository = new ArrayList<>();
repository.add("alpha");
repository.add("beta");

for (String item : repository) {
    System.out.println(item);
}

Implémentation personnalisée d'un conteneur itérable

Pour comprendre les mécanismes internes, il est instructif de recréer un conteneur minimaliste doté de son propre itérateur. L'exemple suivant utilise un tableau générique redimensionnable et une classe interne dédiée au suivi de position.

import java.util.Arrays;
import java.util.NoSuchElementException;

public class SimpleStorage<T> {
    private Object[] storageBuffer;
    private int elementCount;

    public SimpleStorage() {
        this.storageBuffer = new Object[8];
        this.elementCount = 0;
    }

    public void insert(T value) {
        if (elementCount == storageBuffer.length) {
            storageBuffer = Arrays.copyOf(storageBuffer, storageBuffer.length * 2);
        }
        storageBuffer[elementCount++] = value;
    }

    public int count() {
        return elementCount;
    }

    public Cursor<T> createCursor() {
        return new TraversalCursor<>(this);
    }

    private static class TraversalCursor<T> implements java.util.Iterator<T> {
        private final SimpleStorage<T> parent;
        private int position;
        private int lastFetched;

        TraversalCursor(SimpleStorage<T> source) {
            this.parent = source;
            this.position = 0;
            this.lastFetched = -1;
        }

        @Override
        public boolean hasNext() {
            return position < parent.elementCount;
        }

        @SuppressWarnings("unchecked")
        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException("Aucun élément suivant disponible.");
            }
            lastFetched = position++;
            return (T) parent.storageBuffer[lastFetched];
        }

        @Override
        public void remove() {
            if (lastFetched < 0) {
                throw new IllegalStateException("Appelez next() avant remove().");
            }
            System.arraycopy(parent.storageBuffer, lastFetched + 1,
                             parent.storageBuffer, lastFetched,
                             parent.elementCount - lastFetched - 1);
            parent.storageBuffer[--parent.elementCount] = null;
            position = lastFetched;
            lastFetched = -1;
        }
    }
}

Analyses des implémentations standards

Dans l'API standard, l'itérateur d'ArrayList repose sur un suivi d'index direct. Cependant, une mécanique de sécurité cruciale y est intégrée : le compteur de modification structurelle. À chaque altération du conteneur (ajout, retrait), un compteur interne s'incrémente. L'itérateur conserve une copie de ce compteur au moment de son instanciasion. Si les valeurs divergent durant le parcours, une ConcurrentModificationException est levée. Ce comportement, appelé fail-fast, prévient les états incohérents lors de modifications concurrentes ou itératives non sécurisées.

Voici une représentation restructurée de ce mécanisme :

private class ArrayScanner implements java.util.Iterator<E> {
    private int scanIndex;
    private int lastVisited;
    private int versionSnapshot;

    ArrayScanner() {
        this.scanIndex = 0;
        this.lastVisited = -1;
        this.versionSnapshot = AbstractList.this.modCount;
    }

    private void assertConsistency() {
        if (versionSnapshot != AbstractList.this.modCount) {
            throw new ConcurrentModificationException();
        }
    }

    public boolean hasNext() {
        return scanIndex != size();
    }

    public E next() {
        assertConsistency();
        try {
            E result = get(scanIndex);
            lastVisited = scanIndex++;
            return result;
        } catch (IndexOutOfBoundsException ex) {
            assertConsistency();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastVisited == -1) throw new IllegalStateException();
        assertConsistency();
        try {
            AbstractList.this.remove(lastVisited);
            if (lastVisited < scanIndex) scanIndex--;
            lastVisited = -1;
            versionSnapshot = AbstractList.this.modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

Pour LinkedList, la stratégie diffère radicalement. L'itérateur doit naviguer entre des nœuds interconnectés et supporter une bidirectionnalité. L'implémentation native utilise un nœud sentinelle pour simplifier les conditions de bord. Le constructeur optimise le positionnement initial en comparant l'index demandé à la moitié de la taille totale, réduisant ainsi la complexité de la recherche à O(N/2).

private class BidirectionalWalker implements java.util.ListIterator<E> {
    private Node<E> recentNode;
    private Node<E> forwardNode;
    private int currentIndex;
    private int versionSnapshot;

    BidirectionalWalker(int start) {
        if (start < 0 || start > size()) throw new IndexOutOfBoundsException();
        this.versionSnapshot = LinkedList.this.modCount;
        if (start < (size() >> 1)) {
            this.forwardNode = LinkedList.this.first;
            for (currentIndex = 0; currentIndex < start; currentIndex++) {
                this.forwardNode = this.forwardNode.next;
            }
        } else {
            this.forwardNode = LinkedList.this.last;
            for (currentIndex = size(); currentIndex > start; currentIndex--) {
                this.forwardNode = this.forwardNode.prev;
            }
        }
        this.recentNode = null;
    }

    public boolean hasNext() { return currentIndex < size(); }

    public E next() {
        if (!hasNext()) throw new NoSuchElementException();
        recentNode = forwardNode;
        forwardNode = forwardNode.next;
        currentIndex++;
        return recentNode.item;
    }

    public boolean hasPrevious() { return currentIndex > 0; }

    public E previous() {
        if (!hasPrevious()) throw new NoSuchElementException();
        forwardNode = recentNode;
        recentNode = (recentNode == null) ? LinkedList.this.last : recentNode.prev;
        currentIndex--;
        return recentNode.item;
    }

    public void remove() {
        if (recentNode == null) throw new IllegalStateException();
        Node<E> lastNext = recentNode.next;
        unlink(recentNode);
        if (forwardNode == recentNode) forwardNode = lastNext;
        else currentIndex--;
        recentNode = null;
        versionSnapshot = LinkedList.this.modCount;
    }

    private void unlink(Node<E> node) {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null) LinkedList.this.first = next;
        else prev.next = next;
        if (next == null) LinkedList.this.last = prev;
        else next.prev = prev;
        node.item = null;
        size--;
        modCount++;
    }
}

Le motif Iterator réussit son objectif principal : dissocier l'algorithme de navigation de la structure de stockage. Que les données soient contiguës en mémoire ou dispersées dans des objets liés, le client interagit uniquement avec un contrat prévisible. Cette abstraction reste un pilier fondamental de la concepiton logicielle orientée objet, notamment dans les écosystèmes de collections modernes.