05.5 Listes en Java

L’interface List<E> est générique, et étend de Collection<E>

L’interface List

On y ajoute des méthodes de consultation

• E get(int i)
• int indexOf(Object e)
• int lastIndexOf(Object e) On a également des méthodes d’ajout (à un certain index i)
• void add(int i, E e)
• boolean addAll(int i, Collection<E> c) Des méthodes de modification
• E remove(int i)
• E set(int i, E e)
• void replaceAll(UnaryOperator<E> op) (applique une formule aux éléments de la liste ?)

Sous liste

On peut obtenir une sous-liste via

• List<E> subList(int b, int e)

Elles ont muables, et offrent une vue de la sous liste (et non une copie !) → Toutes les modifications sur la super-liste sont “vues” par la sous-liste, ET VICE-VERSA

Tri, mélange

On a également des fonctions qui permettent de trier une liste:

• void sort(Comparator<E> c) Et de la mélanger (via Collections)
• <T> void shuffle(List<T> l, Random r)

Vues sur un tableau

La classe Arrays - méthode pour avoir une vue sur un tableau, sous forme de List

• <T> List<T> asList(T... a)

La vue est partiellement modifiable : ont peut changer des éléments, mais changer la taille cause une exception

Listes immuables

L’interface offre une méthode statique permettant de construire une liste immuable :

• <E> List<E> of(E... es)
• <E> List<E> copyOf(Collection<E> c) La classe Collections offre une méthode de construction de liste immuable :
• <T> List<T> unmodifiableList(List<T> l)

unmodifiableList produit une vue, qui peut avoir ses éléments changés

Règle des listes immuables

Il est mieux d’utiliser la méthode statique copyOf pour créer une liste immuable

Mise en oeuvre

On a donc deux types de listes

• Tableaux-listes ArrayList
• Listes chaînées LinkedList

Elles ont des complexités qui diffèrent

Opération	ArrayList	LinkedList
add	$O(n)$	$O(1)$
get	$O(1)$	$O(n)$

Itérateur

Un objet qui pointe à un élément d’une liste. Nous permet de faire une boucle sur les éléments d’une liste

Iterator<Integer> it = l.iterator();
while(it.hasNext()) {
	System.out.println(it.next());
}

L’avantage de l’objet Iterator est qu’il y a une méthode remove(), qui enlève le dernier élément parcouru

05.6 Piles Files et Deques