Mise en œuvre des collections : listes

Dans le cas des listes, le test d'appartenance (contains) ne peut se faire de manière plus efficace que par parcours des éléments, avec une complexité de O(n). Il est dès lors possible de le mettre directement en œuvre dans la classe AbstractList, au moyen d'une boucle for-each.

@Override
public boolean contains(E e) {
  for (E e1: this) {
    if (e1.equals(e))
      return true;
  }
  return false;
}

La classe AbstractList fournit une redéfinition de la méthode toString, qui produit une représentation textuelle de la liste à laquelle on l'applique. Celle-ci est constituée de la représentation textuelle des éléments de la liste, séparés par une virgule et entourés de crochets ([]).

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

Cette méthode permet en fait d'obtenir la représentation textuelle de n'importe quel objet de type Iterable.

Finalement, AbstractList définit deux méthodes permettant de vérifier la validité des index passés aux différentes méthodes :

• checkElementIndex vérifie que l'index qu'on lui passe est compris entre 0 (inclus) et la taille de la liste (exclue), et donc qu'il désigne bien un élément de celle-ci,
• checkPositionIndex vérifie que l'index qu'on lui passe est compris entre 0 (inclus) et la taille de la liste (incluse), et donc qu'il désigne bien une position d'insertion dans celle-ci.

Chacune de ces méthodes retourne l'index s'il est valide, et lève l'exception IndexOutOfBoundsException sinon. Ces méthodes étant destinées à être utilisées exclusivement par les sous-classes concrètes de AbstractList, elles sont protégées.

protected final int checkElementIndex(int i) {
  if (! (0 <= i && i < size()))
    throw new IndexOutOfBoundsException();
  return i;
}

protected final int checkPositionIndex(int i) {
  if (! (0 <= i && i <= size()))
    throw new IndexOutOfBoundsException();
  return i;
}

Lors de l'ajout d'un élément dans un tableau-liste, deux cas sont à distinguer : soit il reste de la place dans le tableau sous-jacent pour stocker le nouvel élément, soit il n'en reste pas.

Dans le second cas, le tableau sous-jacent doit être « redimensionné ». Bien entendu, comme il n'est pas possible de redimensionner un tableau en Java, cela doit se faire par copie dans un nouveau tableau, nommé newArray ci-dessous. Lorsque cela se produit, une question se pose : quelle taille donner au nouveau tableau ?

Une première idée serait de dimensionner le nouveau tableau pour qu'il puisse juste contenir le nouvel élément, c-à-d que sa taille soit celle de l'ancien augmentée d'une unité. Malheureusement, en procédant de la sorte, une nouvelle copie du tableau sous-jacent doit être faite à chaque ajout lors d'ajouts successifs, et la complexité de l'ajout est alors de O(n).

Dès lors, il faut dimensionner le nouveau tableau de manière à ce que plusieurs ajouts successifs puissent être faits avant qu'un nouveau redimensionnement ne soit nécessaire. Une manière de faire consiste à doubler la taille du tableau sous-jacent à chaque redimensionnement, garantissant ainsi que l'ajout a une complexité amortie de O(1). (La notion de complexité amortie ne sera pas examinée en détail ici.)

La méthode add ci-dessous met cette idée en œuvre. Elle utilise la méthode arraycopy pour déplacer ou copier les éléments du tableau sous-jacent. Cette méthode prend cinq paramètres qui sont, dans l'ordre : le tableau source, l'index de départ dans le tableau source, le tableau destination, l'index de départ dans le tableau destination et le nombre d'éléments à copier.

@Override
public void add(int i, E e) {
  checkPositionIndex(i);
  if (size < array.length) {
    System.arraycopy(array, i, array, i + 1, size - i);
  } else {
    @SuppressWarnings("unchecked")
    E[] newArray = (E[]) new Object[array.length * 2];
    System.arraycopy(array, 0, newArray, 0, i);
    System.arraycopy(array, i, newArray, i + 1, size - i);
    array = newArray;
  }
  array[i] = e;
  size += 1;
}

La suppression d'un élément dans un tableau-liste implique de déplacer d'une position vers le bas tous les éléments d'index supérieur. Là aussi, cela peut se faire au moyen d'une copie de ces éléments, effectuée par la méthode arraycopy.

Une fois les éléments déplacés, il est très important de mettre à null l'élément qui se trouve juste après le dernier élément appartenant à la liste. Cela garantit que le tableau sous-jacent ne référence jamais un élément qui se trouvait précédemment dans la liste mais ne s'y trouve plus, évitant ainsi de garder inutilement allouée la mémoire associée à un tel élément. Pour plus de détails à ce sujet, voir la règle 6 (Eliminate obsolete object references) du livre Effective Java.

@Override
public void remove(int i) {
  checkElementIndex(i);
  System.arraycopy(array, i + 1, array, i, size - i - 1);
  array[--size] = null;
}

A noter que le tableau sous-jacent pourrait aussi être redimensionné à la baisse lors d'une suppression, s'il est devenu trop grand par rapport au nombre d'éléments présents. Cela n'a pas été fait ici dans un souci de simplicité.

Les opérations d'accès (get) et de modification (set) sont très simple à mettre en œuvre, car elles correspondent à de simples accès au tableau sous-jacent. Il est toutefois important de bien valider les index reçus au moyen de la méthode checkElementIndex, car ceux-ci pourraient très bien être valides pour le tableau sous-jacent mais invalides pour le tableau-liste !

@Override
public E get(int i) {
  return array[checkElementIndex(i)];
}

@Override
public E set(int i, E e) {
  E oldE = array[checkElementIndex(i)];
  array[i] = e;
  return oldE;
}

La méthode iterator doit retourner un itérateur permettant de parcourir les éléments du tableau-liste, et cet itérateur doit être un objet implémentant l'interface Iterator. Il faut dès lors écrire une classe implémentant cette interface et capable d'itérer sur les éléments du tableau-liste.

Cette classe peut s'écrire de plusieurs manières, et trois d'entre elles sont présentées ci-dessous. La première utilise une classe imbriquée statique, concept déjà examiné dans ce cours, tandis que les deux autres, plus simples, utilisent de nouveaux concepts du langage Java, introduits ci-dessous.

L'ajout et la suppression d'un élément dans une liste chaînée implique la mise à jour des liens du ou des nœuds voisins de celui à insérer ou supprimer.

Pour l'ajout, deux cas sont à considérer : si le nouvel élément doit être placé en tête de liste, alors le nouveau nœud lui correspondant doit devenir la nouvelle tête de liste ; sinon, il faut tout d'abord obtenir le prédécesseur du nœud à insérer (pred ci-dessous) puis ajuster son lien vers son successeur pour le faire référencer le nouveau nœud. Dans les deux cas, il faut penser à incrémenter la taille de la liste.

@Override
public void add(int i, E e) {
  if (checkPositionIndex(i) == 0) {
    head = new Node<>(head, e);
  } else {
    Node<E> pred = getNode(i - 1);
    pred.next = new Node<>(pred.next, e);
  }
  size += 1;
}

La suppression est très similaire à l'ajout, et les deux mêmes cas sont à distinguer.

@Override
public void remove(int i) {
  if (checkElementIndex(i) == 0) {
    head = head.next;
  } else {
    Node<E> pred = getNode(i - 1);
    pred.next = pred.next.next;
  }
  size -= 1;
}

L'accès à l'élément à un index donné, ou sa modification, consistent à obtenir le nœud à cet index puis à extraire ou modifier son élément. Etant donné l'existence de la méthode getNode, cela se fait très simplement.

@Override
public E get(int i) {
  return getNode(checkElementIndex(i)).elem;
}

@Override
public E set(int i, E e) {
  Node<E> node = getNode(checkElementIndex(i));
  E oldE = node.elem;
  node.elem = e;
  return oldE;
}

Si l'on ignore dans un premier temps sa méthode remove, et considère simplement qu'elle lève l'exception UnsupportedOperationException, l'itérateur sur les listes simplement chaînées est facile à écrire. Son seul état est le nœud next dont l'élément doit être retourné par le prochain appel à la méthode du même nom. Un tel itérateur non modifiable est retourné par la méthode (fictive) unmodifiableIterator ci-dessous :

public Iterator<E> unmodifiableIterator() {
  return new Iterator<E>() {
    private Node<E> next = head;

    @Override
    public boolean hasNext() {
      return next != null;
    }

    @Override
    public E next() {
      if (!hasNext())
        throw new NoSuchElementException();

      E elem = next.elem;
      next = next.next;
      return elem;
    }
  };
}

L'ajout de la méthode remove complique passablement l'itérateur, car conserver uniquement une référence sur le prochain nœud (next) ne suffit plus. En effet, la méthode remove doit supprimer le dernier élément retourné par next, et dès lors il faut en tout temps avoir accès au prédécesseur du prédécesseur du nœud next !

Pour ce faire, la version complète — c-à-d avec la méthode remove — de l'itérateur maintient non pas une mais trois références vers des nœuds, qui sont :

• pred, qui désigne le nœud précédent le nœud courant,
• curr, qui désigne le nœud courant, c-à-d celui dont l'élément a été retourné par le dernier appel à next,
• next, qui désigne comme précédemment le nœud suivant, c-à-d celui dont l'élément sera retourné par le prochain appel à next.

Ces trois nœuds sont consécutifs dans la liste : pred précède directement curr, qui précède directement next. Dès lors, curr est null lorsque next désigne le premier nœud de la liste, et pred est null lorsque soit next, soit curr désignent le premier nœud de la liste.

Ces trois références doivent être mise à jour correctement dans la méthode next. Cela fait, la méthode remove est relativement simple à écrire et ressemble passablement à la méthode remove de la classe SLinkedList.

@Override
public Iterator<E> iterator() {

  return new Iterator<E>() {
    private Node<E> pred = null, curr = null, next = head;
    private boolean canRemove = false;

    @Override
    public boolean hasNext() {
      return next != null;
    }

    @Override
    public E next() {
      if (!hasNext())
        throw new NoSuchElementException();
      canRemove = true;

      E elem = next.elem;
      pred = curr;
      curr = next;
      next = next.next;
      return elem;
    }

    @Override
    public void remove() {
      if (!canRemove)
        throw new IllegalStateException();
      canRemove = false;

      if (pred == null)
        head = head.next;
      else
        pred.next = pred.next.next;
      curr = pred;
      pred = null;
      size -= 1;
    }
  };

}

Il faut noter que, dans la méthode remove, la mise à jour du lien du prédécesseur pourrait s'écrire de manière plus simple, en tirant parti de l'exitence de la référence next :

if (pred == null)
  head = next;       // au lieu de head.next
else
  pred.next = next;  // au lieu de pred.next.next

Cela n'a pas été fait plus haut afin que la similarité entre la méthode remove de l'itérateur et celle de la classe SLinkedList soit plus évidente.