Quartz 4

Notes S12

9 min read

Notes S12

Mise en œuvre des collections : listes

public interface SList<E> extends Iterable<E> {
  int size();
  boolean isEmpty();
  void add(int i, E e);
  void remove(int i);
  boolean contains(E e);
  E get(int i);
  E set(int i, E e);
  Iterator<E> iterator();
}

étend Iterable, permet de parcourir avec foreach

3. Liste abstraite (SAbstractList)

La classe héritable SAbstractList fournit des mises en œuvre par défaut des méthodes de l’interface SList qu’il est possible d’exprimer en fonction d’autres méthodes de cette même interface. Par exemple, isEmpty s’exprime trivialement en terme de size :

public abstract class SAbstractList<E>
    implements SList<E> {
 
  @Override
  public boolean isEmpty() {
    return size() == 0;
  }

3.1. Test d’appartenance

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 SAbstractList, 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;
}

3.2. Représentation textuelle

La classe SAbstractList 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() {
  StringJoiner j = new StringJoiner(", ", "[", "]");
  for (E e: this)
    j.add(e.toString());
  return j.toString();
}

ou forEach(e -> j.add(e.toString()))

3.3. Vérification d’index

  • checkElementIndex vérifie que l’index 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 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 retourne l’index s’il est valide, et lève IndexOutOfBoundsException sinon. Ces méthodes sont protected car destinées uniquement aux sous-classes.

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;
}

4. Tableau-liste (SArrayList)

Les tableaux-listes (tableaux dynamiques) stockent les éléments dans un tableau sous-jacent, agrandi par copie si nécessaire.

  • Force : accès à un élément par index en O(1).
  • Faiblesse : insertion à une position quelconque en O(n) (déplacement des éléments suivants). Insertion en fin de liste : complexité amortie O(1).

La classe possède deux attributs : size (nombre d’éléments) et array (le tableau sous-jacent, dont la taille = capacité). La capacité initiale est fixée à 10.

public final class SArrayList<E> extends SAbstractList<E> {
  private int size = 0;
 
  @SuppressWarnings("unchecked")
  private E[] array = (E[]) new Object[10];
 
  @Override
  public int size() {
    return size;
  }
}

4.1. Ajout et suppression

Ajout : si le tableau est plein, on le double en taille (garantit une complexité amortie O(1) pour les ajouts successifs). On utilise System.arraycopy pour déplacer les éléments.

@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;
}

Suppression : on décale les éléments d’index supérieur vers le bas. Important : mettre à null la case libérée après le dernier élément pour éviter de garder en mémoire un objet devenu inutile (cf. Effective Java, règle 7 — Eliminate obsolete object references).

@Override
public void remove(int i) {
  checkElementIndex(i);
  System.arraycopy(array, i + 1, array, i, size - i - 1);
  array[--size] = null; // ← évite la fuite mémoire
}

4.2. Accès et modification

Opérations simples : accès direct au tableau sous-jacent. Il est crucial de valider les index avec checkElementIndex car un index pourrait être valide pour le tableau mais invalide pour la 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;
}

4.3. Itération

La méthode iterator() retourne un objet implémentant Iterator<E>. Trois façons de l’écrire :

4.3.1. Itérateur imbriqué statiquement (SALIterator1)

Classe private static imbriquée dans SArrayList. N’a pas accès aux membres de la classe englobante → on lui passe le tableau-liste en argument du constructeur.

L’attribut canRemove garantit que remove() ne peut être appelé qu’après next() et pas deux fois de suite.

private static final class SALIterator1<E>
    implements Iterator<E> {
  private final SArrayList<E> list;
  private int nextI = 0;
  private boolean canRemove = false;
 
  public SALIterator1(SArrayList<E> list) {
    this.list = list;
  }
 
  @Override
  public boolean hasNext() {
    return nextI < list.size;
  }
 
  @Override
  public E next() {
    if (!hasNext()) throw new NoSuchElementException();
    canRemove = true;
    return list.array[nextI++];
  }
 
  @Override
  public void remove() {
    if (!canRemove) throw new IllegalStateException();
    canRemove = false;
    list.remove(--nextI);
  }
}
 
@Override
public Iterator<E> iterator() {
  return new SALIterator1<>(this);
}

4.3.2. Itérateur intérieur (SALIterator2)

Classe intérieure = classe imbriquée non statique. Chaque instance est associée à une instance de la classe englobante → accès direct à size, array, etc. Plus besoin de passer le tableau-liste en paramètre. La référence vers la classe englobante existe implicitement et est accessible via SArrayList.this.

private final class SALIterator2
    implements Iterator<E> {
  private int nextI = 0;
  private boolean canRemove = false;
 
  @Override
  public boolean hasNext() {
    return nextI < size; // accès direct à size de SArrayList
  }
 
  @Override
  public E next() {
    if (!hasNext()) throw new NoSuchElementException();
    canRemove = true;
    return array[nextI++]; // accès direct à array
  }
 
  @Override
  public void remove() {
    if (!canRemove) throw new IllegalStateException();
    canRemove = false;
    SArrayList.this.remove(--nextI); // référence explicite à l'englobante
  }
}
 
@Override
public Iterator<E> iterator() {
  return new SALIterator2();
}

4.3.3. Itérateur intérieur anonyme

SALIterator2 n’étant utilisé qu’en un seul endroit, on peut en faire une classe anonyme directement dans iterator(). Comportement rigoureusement identique, écriture plus concise :

@Override
public Iterator<E> iterator() {
  return new Iterator<E>() {
    private int nextI = 0;
    private boolean canRemove = false;
 
    @Override
    public boolean hasNext() {
      return nextI < size;
    }
 
    @Override
    public E next() {
      if (!hasNext()) throw new NoSuchElementException();
      canRemove = true;
      return array[nextI++];
    }
 
    @Override
    public void remove() {
      if (!canRemove) throw new IllegalStateException();
      canRemove = false;
      SArrayList.this.remove(--nextI);
    }
  };
}

5. Liste chaînée (SLinkedList)

Les éléments ne sont pas dans un tableau mais référencés par des nœuds chaînés entre eux.

  • Liste simplement chaînée : chaque nœud pointe vers son successeur.
  • Liste doublement chaînée : chaque nœud pointe vers ses deux voisins.
  • Liste circulaire : le dernier nœud pointe vers le premier.

Force : insertion/suppression en O(1) si on a déjà une référence sur le nœud voisin.

Faiblesse : accès par index en O(n) (il faut parcourir depuis la tête).

SLinkedList possède deux attributs : size et head (premier nœud, ou null si la liste est vide).

La classe Node (privée, imbriquée statiquement) représente un nœud : elem pour la valeur, next pour le nœud suivant (null si dernier).

java

public final class SLinkedList<E> extends SAbstractList<E> {
  private int size = 0;
  private Node<E> head = null;
 
  @Override
  public int size() { return size; }
 
  // Méthode privée : obtenir le nœud à l'index i en O(n)
  private Node<E> getNode(int i) {
    Node<E> n = head;
    for (int j = 0; j < i; ++j)
      n = n.next;
    return n;
  }
 
  private static final class Node<E> {
    private Node<E> next;
    private E elem;
 
    public Node(Node<E> next, E elem) {
      this.next = next;
      this.elem = elem;
    }
  }
}

5.1. Ajout et suppression

Ajout : deux cas — insertion en tête (nouveau nœud devient head) ou ailleurs (on cherche le prédécesseur et on recâble les liens).

@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;
}

Suppression : même logique.

@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;
}

5.2. Accès et modification

Grâce à getNode, ces méthodes sont simples :

@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;
}

5.3. Itération

Sans remove : l’état de l’itérateur est simplement le nœud next courant.

Avec remove : plus compliqué. Il faut pouvoir supprimer le dernier élément retourné, donc connaître son prédécesseur. L’itérateur maintient trois références :

  • pred : nœud précédant curr
  • curr : nœud dont l’élément a été retourné par le dernier appel à next()
  • next : nœud dont l’élément sera retourné par le prochain appel à next()

curr est null tant que next() n’a pas encore été appelé. pred est null lorsque curr ou next désigne le premier nœud

@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;  // ou head = next
      else
        pred.next = pred.next.next;  // ou pred.next = next
      curr = pred;
      pred = null;
      size -= 1;
    }
  };
}

Récapitulatif des complexités

OpérationSArrayListSLinkedList
get(i)O(1)O(n)
set(i, e)O(1)O(n)
add(i, e)O(n) / O(1) amorti en finO(n) (pour trouver le nœud)
remove(i)O(n)O(n)
contains(e)O(n)O(n)

Graph View