13.1 Listes

Etudions la mise en oeuvre d’une interface simplifiée pour les 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();
}

Liste abstraite

On peut déjà mettre en oeuvre des fonctions qui ne devraient pas changer selon l’implémentation de différentes listes, notamment

• isEmpty()

boolean isEmpty() {
	return size() == 0;
}

• contains()

boolean contains(E e) {
	for (E el : this) {
		if (el.equals(e)) return true;
	}
	return false;
}

• toString()

public String toString() {
  StringJoiner j = new StringJoiner(", ", "[", "]");
  for (E e: this)
    j.add(e.toString());
  return j.toString();
}

On peut également implémenter des préconditions pour vérifier si les index passés sont valides

Tableau-liste

Ces listes se basent sur le contenu d’un tableau. Par contre, vu que le tableau contiendra des cases vides, il faut stocker la taille indépendamment.

private int size = 0;
 
private E[] array = (E[]) new Object[10];
 
public int size() {
	return size;
}

On doit par contre vérifier que l’on ait assez de capacité pour pouvoir insérer des choses dans le tableau

public void add(int i, E e) {
	checkPositionIndex(i); // vérifier si l'index est valide
	
	if (size < array.length) {
		System.arraycopy(array, i, array, i + 1, size - i);
	} else {
		E[] newArray = (E[]) new Object[array.length * 2];
		System.arraycopy(array, 0, newArray, 0, i);
		System.arraycopy(array, i, newArray, i + 1, size - 1);
		array = newArray;
	}
	array[i] = e;
	size++;
}

Pour enlever un élément, on doit ensuite déplacer les éléments se situant plus loin dans le tableau plus bas.

public void remove(int i) {
	checkElementIndex(i); // Vérifier s'il y a qqch à l'index
	System.arraycopy(array, i + 1, array, i, size - i - 1);
	array[--size] = null;
}

Et on peut facilement accéder aux éléments du tableau

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

Et également facilement modifier un élément

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

Itération

Pour pouvoir itérer, il faut implémenter l’accès au éléments du tableau. Pour simplifier l’implémentation, on imbrique statiquement une mise en oeuvre de l’itérateur

private static final class SALIterator1<E> implements Iterator<E> {
  private final SArrayList<E> list;
  private int nextI;
  private boolean canRemove;
 
  public SALIterator1(SArrayList<E> list) {
    this.list = list;
    this.nextI = 0;
    this.canRemove = false;
  }
 
  @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);
  }
}

Ainsi on peut retourner un itérateur si demandé.

public Iterator<E> iterator() {
	return new SALIterator1<>(this);
}

On pourrait également retourner une classe anonyme d’itérateur.

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();
      SArrayList.this.remove(--nextI);
      canRemove = false;
    }
  };
}

Liste chaînée

Ou LinkedList en java — ne stocke pas les éléments dans un tableau, mais contient des nœuds reliés entre eux. ⇒ Ils sont donc liés par des références les uns aux autres.

On a trois différentes manières d’implémenter ces listes:

1. Liste simple — chaque noeud fait référence au prochain
2. Liste doublement chaînée — chaque noeud référence le noeud suivant et précédent
3. Liste circulaire — le premier et dernier noeud sont reliés entre eux

Cette implémentation contient donc une classe imbriquée statique qui représente les noeuds:

private static final class Node<E> {
	private Node<E> next;
	private E element;
	
	public Node(Node<E> next, E element) {
		this.next = next;
		this.element = element;
	}
}

L’ajout et la suppression sont plutôt triviaux, car il ne faut jamais re-allouer le tableau pour qu’il ait plus de taille.