Java Language
Des listes

Introduction

Syntaxe

• ls.add (élément E); // Ajoute un élément
• ls.remove (élément E); // Supprime un élément
• for (élément E: ls) {} // Itère sur chaque élément
• ls.toArray (new String [ls.length]); // Convertit une liste de chaînes en un tableau de chaînes
• ls.get (int index); // Renvoie l'élément à l'index spécifié.
• ls.set (int index, E element); // Remplace l'élément à une position spécifiée.
• ls.isEmpty (); // Renvoie true si le tableau ne contient aucun élément, sinon il retourne false.
• ls.indexOf (objet o); // Renvoie l'index du premier emplacement de l'élément spécifié o ou, s'il n'est pas présent, renvoie -1.
• ls.lastIndexOf (objet o); // Renvoie l'index du dernier emplacement de l'élément spécifié o ou, s'il n'est pas présent, renvoie -1.
• ls.size (); // Renvoie le nombre d'éléments de la liste.

Remarques

List<String> list = new ArrayList<>();
list.add("world");
System.out.println(list.indexOf("world"));      // Prints "0"
// Inserting a new value at index 0 moves "world" to index 1
list.add(0, "Hello");
System.out.println(list.indexOf("world"));      // Prints "1"
System.out.println(list.indexOf("Hello"));      // Prints "0"

Trier une liste générique

La classe Collections propose deux méthodes statiques standard pour trier une liste:

• sort(List<T> list) applicable aux listes où T extends Comparable<? super T> , et
• sort(List<T> list, Comparator<? super T> c) applicable aux listes de tout type.

Appliquer le premier nécessite de modifier la classe des éléments de liste en cours de tri, ce qui n'est pas toujours possible. Cela peut également être indésirable car, bien qu'il fournisse le tri par défaut, d'autres ordres de tri peuvent être requis dans différentes circonstances, ou le tri n'est qu'une tâche ponctuelle.

Considérons que nous avons pour tâche de trier les objets qui sont des instances de la classe suivante:

public class User {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }
}

Pour utiliser Collections.sort(List<User> list) nous devons modifier la classe User pour implémenter l'interface Comparable . Par exemple

public class User implements Comparable<User> {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }

    @Override
    /** The natural ordering for 'User' objects is by the 'id' field. */
    public int compareTo(User o) {
        return id.compareTo(o.id);
    }
}

(À part: de nombreuses classes Java standard telles que String , Long , Integer implémentent l'interface Comparable . Cela rend les listes de ces éléments triables par défaut et simplifie l'implémentation de compare ou compareTo dans d'autres classes.)

Avec la modification ci-dessus, nous pouvons facilement trier une liste d'objets User fonction de l' ordre naturel des classes. (Dans ce cas, nous avons défini cela comme étant basé sur les valeurs d’ id ). Par exemple:

List<User> users = Lists.newArrayList(
    new User(33L, "A"),
    new User(25L, "B"),
    new User(28L, ""));
Collections.sort(users);

System.out.print(users);
// [B:25, C:28, A:33]

Cependant, supposons que nous voulions trier User objets User par name plutôt que par id . Supposons maintenant que nous n'avions pas été en mesure de changer la classe pour le faire mettre en œuvre Comparable .

C'est là que la méthode de sort avec l'argument Comparator est utile:

Collections.sort(users, new Comparator<User>() {
    @Override
    /* Order two 'User' objects based on their names. */
    public int compare(User left, User right) {
        return left.username.compareTo(right.username);
    }
});
System.out.print(users);
// [A:33, B:25, C:28]

Collections.sort(users, (l, r) -> l.username.compareTo(r.username));

users.sort((l, r) -> l.username.compareTo(r.username))

Créer une liste

Donner un type à votre liste

Pour créer une liste, vous avez besoin d'un type (n'importe quelle classe, par exemple String ). C'est le type de votre List . La List ne stockera que les objets du type spécifié. Par exemple:

List<String> strings;

Peut stocker "string1" , "hello world!" , "goodbye" , etc., mais il ne peut pas stocker 9.2 , cependant:

List<Double> doubles;

Peut stocker 9.2 , mais pas "hello world!" .

Initialiser votre liste

Si vous essayez d'ajouter quelque chose aux listes ci-dessus, vous obtiendrez une exception NullPointerException, car les strings et les doubles toutes deux nulles !

Il existe deux manières d’initialiser une liste:

Option 1: Utiliser une classe qui implémente List

List est une interface, ce qui signifie qu’elle n’a pas de constructeur, plutôt que des méthodes qu’une classe doit remplacer. ArrayList est la plus couramment utilisée List , bien que LinkedList est également commune. Donc, nous initialisons notre liste comme ceci:

List<String> strings = new ArrayList<String>();

ou

List<String> strings = new LinkedList<String>();

List<String> strings = new ArrayList<>();

List<String> strings = new LinkedList<>();

Option 2: Utiliser la classe Collections

La classe Collections fournit deux méthodes utiles pour créer des listes sans variable List :

• emptyList() : renvoie une liste vide.
• singletonList(T) : crée une liste de type T et ajoute l'élément spécifié.

Et une méthode qui utilise une List existante pour remplir des données dans:

• addAll(L, T...) : ajoute tous les éléments spécifiés à la liste passée en tant que premier paramètre.

Exemples:

import java.util.List;
import java.util.Collections;

List<Integer> l = Collections.emptyList();
List<Integer> l1 = Collections.singletonList(42);
Collections.addAll(l1, 1, 2, 3);

Opérations d'accès positionnel

L'API de liste a huit méthodes pour les opérations d'accès positionnel:

• add(T type)
• add(int index, T type)
• remove(Object o)
• remove(int index)
• get(int index)
• set(int index, E element)
• int indexOf(Object o)
• int lastIndexOf(Object o)

Donc, si nous avons une liste:

List<String> strings = new ArrayList<String>();

Et nous voulions ajouter les chaînes "Hello world!" et "Au revoir le monde!" à cela, nous le ferions en tant que tel:

strings.add("Hello world!");
strings.add("Goodbye world!");

Et notre liste comprendrait les deux éléments. Maintenant, disons que nous voulions ajouter "Programme de démarrage!" en tête de liste. Nous ferions ceci comme ceci:

strings.add(0, "Program starting!");

REMARQUE: le premier élément est 0.

Maintenant, si nous voulions supprimer le "Monde Au revoir!" ligne, nous pourrions le faire comme ceci:

strings.remove("Goodbye world!");

Et si nous voulions supprimer la première ligne (qui dans ce cas serait "Programme en cours!", Nous pourrions le faire comme ceci:

strings.remove(0);

Remarque:

1. L'ajout et la suppression d'éléments de liste modifient la liste, ce qui peut entraîner une ConcurrentModificationException si la liste est itérée simultanément.

2. L'ajout et la suppression d'éléments peuvent être O(1) ou O(N) selon la classe de liste, la méthode utilisée et si vous ajoutez / supprimez un élément au début, à la fin ou au milieu de la liste.

Afin de récupérer un élément de la liste à une position spécifiée, vous pouvez utiliser le E get(int index); méthode de l'API List. Par exemple:

strings.get(0);

renverra le premier élément de la liste.

Vous pouvez remplacer n'importe quel élément à une position spécifiée en utilisant l' set(int index, E element); . Par exemple:

strings.set(0,"This is a replacement");

Cela définira la chaîne "Ceci est un remplacement" comme premier élément de la liste.

Remarque: La méthode set remplacera l'élément à la position 0. Il n'ajoutera pas la nouvelle chaîne à la position 0 et poussera l'ancienne à la position 1.

Le int indexOf(Object o); renvoie la position de la première occurrence de l'objet passé en argument. S'il n'y a pas d'occurrences de l'objet dans la liste, la valeur -1 est renvoyée. Dans la suite de l'exemple précédent, si vous appelez:

strings.indexOf("This is a replacement")

le 0 devrait être renvoyé lorsque nous définissons la chaîne "Ceci est un remplacement" dans la position 0 de notre liste. Dans le cas où il y a plus d'une occurrence dans la liste quand int indexOf(Object o); est appelé alors comme mentionné, l'index de la première occurrence sera renvoyé. En appelant int lastIndexOf(Object o) vous pouvez récupérer l'index de la dernière occurrence dans la liste. Donc, si nous ajoutons un autre "Ceci est un remplacement":

strings.add("This is a replacement");
strings.lastIndexOf("This is a replacement");

Cette fois, le 1 sera renvoyé et non le 0;

Itérer sur les éléments d'une liste

Pour l'exemple, disons que nous avons une liste de type String qui contient quatre éléments: "bonjour", "comment", "sont", "vous?"

La meilleure façon de parcourir chaque élément est d'utiliser une boucle for-each:

public void printEachElement(List<String> list){
    for(String s : list){
        System.out.println(s);
    }
}

Qui imprimerait:

hello,
how
are
you?

Pour les imprimer tous dans la même ligne, vous pouvez utiliser un StringBuilder:

public void printAsLine(List<String> list){
    StringBuilder builder = new StringBuilder();
    for(String s : list){
        builder.append(s);
    }
    System.out.println(builder.toString());
}

Imprimera:

hello, how are you?

Vous pouvez également utiliser l'indexation d'élément (comme décrit dans Accès à l'élément à partir d'Index de ArrayList ) pour itérer une liste. Attention: cette approche est inefficace pour les listes liées.

Suppression d'éléments de la liste B présents dans la liste A

Supposons que vous ayez 2 listes A et B, et que vous voulez supprimer de B tous les éléments que vous avez dans A la méthode dans ce cas est

 List.removeAll(Collection c);

#Exemple:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));
    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);

    numbersB.removeAll(numbersA);
    System.out.println("B cleared: " + numbersB);
    }

cela va imprimer

A: [1, 3, 4, 7, 5, 2]

B: [13, 32, 533, 3, 4, 2]

B effacé: [13, 32, 533]

Recherche d'éléments communs entre 2 listes

Supposons que vous ayez deux listes: A et B, et que vous devez trouver les éléments qui existent dans les deux listes.

Vous pouvez le faire en invoquant simplement la méthode List.retainAll() .

Exemple:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));

    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);
    List<Integer> numbersC = new ArrayList<>();
    numbersC.addAll(numbersA);
    numbersC.retainAll(numbersB);

    System.out.println("List A : " + numbersA);
    System.out.println("List B : " + numbersB);
    System.out.println("Common elements between A and B: " + numbersC);

}

Convertir une liste d'entiers en une liste de chaînes

List<Integer> nums = Arrays.asList(1, 2, 3);
List<String> strings = nums.stream()
    .map(Object::toString)
    .collect(Collectors.toList());

C'est:

1. Créer un flux à partir de la liste
2. Mapper chaque élément en utilisant Object::toString
3. Collectez les valeurs de String dans une List aide de Collectors.toList()

Créer, ajouter et supprimer un élément d'une liste de tableaux

ArrayList est l'une des structures de données intégrées à Java. C'est un tableau dynamique (où la taille de la structure de données n'a pas besoin d'être déclarée en premier) pour stocker des éléments (objets).

Il étend la classe AbstractList et implémente l'interface List . Un ArrayList peut contenir des éléments en double où il maintient l'ordre d'insertion. Il convient de noter que la classe ArrayList n'est pas synchronisée, il faut donc faire attention lors de la gestion de la concurrence avec ArrayList . ArrayList permet un accès aléatoire car le tableau fonctionne sur la base de l'index. La manipulation est lente dans ArrayList raison du décalage qui se produit souvent lorsqu'un élément est supprimé de la liste de tableaux.

Un ArrayList peut être créé comme suit:

List<T> myArrayList = new ArrayList<>();

Où T ( Generics ) est le type qui sera stocké dans ArrayList .

Le type de ArrayList peut être n'importe quel objet. Le type ne peut pas être un type primitif (utilisez plutôt leurs classes wrapper ).

Pour ajouter un élément à ArrayList , utilisez la méthode add() :

myArrayList.add(element);

Ou pour ajouter un élément à un certain index:

myArrayList.add(index, element); //index of the element should be an int (starting from 0)

Pour supprimer un élément de ArrayList , utilisez la méthode remove() :

myArrayList.remove(element);

Ou pour supprimer un élément d'un certain index:

myArrayList.remove(index); //index of the element should be an int (starting from 0)

Remplacement sur place d'un élément List

Cet exemple concerne le remplacement d'un élément List tout en veillant à ce que l'élément de remplacement soit à la même position que l'élément remplacé.

Cela peut être fait en utilisant ces méthodes:

• set (int index, type T)
• int indexOf (type T)

Considérons un ArrayList contenant les éléments "Programme démarrant!", "Bonjour tout le monde!" et "Au revoir le monde!"

List<String> strings = new ArrayList<String>();
strings.add("Program starting!");
strings.add("Hello world!");
strings.add("Goodbye world!");

Si nous connaissons l'indice de l'élément que nous voulons remplacer, nous pouvons simplement utiliser set comme suit:

strings.set(1, "Hi world");

Si nous ne connaissons pas l'index, nous pouvons le rechercher en premier. Par exemple:

int pos = strings.indexOf("Goodbye world!");
if (pos >= 0) {
    strings.set(pos, "Goodbye cruel world!");
}

Remarques:

1. L'opération set ne provoquera pas une ConcurrentModificationException .
2. L'opération set est rapide ( O(1) ) pour ArrayList mais lente ( O(N) ) pour une LinkedList .
3. Une recherche indexOf sur une ArrayList ou LinkedList est lente ( O(N) ).

Rendre une liste non modifiable

La classe Collections fournit un moyen de rendre une liste non modifiable:

List<String> ls = new ArrayList<String>();
List<String> unmodifiableList = Collections.unmodifiableList(ls);

Si vous souhaitez une liste non modifiable avec un élément, vous pouvez utiliser:

List<String> unmodifiableList = Collections.singletonList("Only string in the list");

Déplacement d'objets dans la liste

La classe Collections vous permet de déplacer des objets dans la liste en utilisant différentes méthodes (ls est la liste):

Inverser une liste:

Collections.reverse(ls);

Rotation des positions des éléments dans une liste

La méthode rotate nécessite un argument entier. C'est le nombre de points à déplacer le long de la ligne. Un exemple de ceci est ci-dessous:

List<String> ls = new ArrayList<String>();
ls.add(" how");
ls.add(" are");
ls.add(" you?");
ls.add("hello,");
Collections.rotate(ls, 1);

for(String line : ls) System.out.print(line);
System.out.println();

Cela va imprimer "bonjour, comment vas-tu?"

Mélanger les éléments dans une liste

En utilisant la même liste ci-dessus, nous pouvons mélanger les éléments dans une liste:

Collections.shuffle(ls);

On peut aussi lui donner un objet java.util.Random qu'il utilise pour placer aléatoirement des objets dans les taches:

Random random = new Random(12); 
Collections.shuffle(ls, random);

Liste d'implémentation des classes - Avantages et inconvénients

L'interface List est implémentée par différentes classes. Chacun d'entre eux a sa propre façon de le mettre en œuvre avec différentes stratégies et de fournir des avantages et des inconvénients différents.

Classes implémentant la liste

Ce sont toutes les classes public de Java SE 8 qui implémentent l'interface java.util.List :

1. Classes abstraites:
   • AbstractList
   • AbstractSequentialList
2. Classes de béton:
   • ArrayList
   • AttributeList
   • CopyOnWriteArrayList
   • LinkedList
   • Liste de rôles
   • RoleUnresolvedList
   • Empiler
   • Vecteur

Avantages et inconvénients de chaque mise en œuvre en termes de complexité temporelle

ArrayList

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList est une implémentation de tableau redimensionnable de l'interface List. En stockant la liste dans un tableau, ArrayList fournit des méthodes (en plus des méthodes implémentant l'interface List ) pour manipuler la taille du tableau.

Initialiser ArrayList d'Integer avec la taille 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- AVANTAGES:

Les opérations size, isEmpty, get , set , iterator et listIterator s'exécutent en temps constant. Ainsi, obtenir et définir chaque élément de la liste a le même coût :

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- LES INCONVÉNIENTS:

Étant implémenté avec un tableau (structure statique), l'ajout d'éléments sur la taille du tableau a un coût important, car une nouvelle allocation doit être effectuée pour tout le tableau. Cependant, à partir de la documentation :

L'opération d'ajout s'exécute dans un temps constant amorti, c'est-à-dire que l'ajout de n éléments nécessite l'heure O (n)

Supprimer un élément nécessite O (n) temps.

AttributeList

En venant

CopyOnWriteArrayList

En venant

LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList est implémentée par une liste à double liaison, une structure de données liée qui consiste en un ensemble d’enregistrements liés de manière séquentielle appelés nœuds.

Iitialize LinkedList d'Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- AVANTAGES:

L'ajout ou la suppression d'un élément au début de la liste ou à la fin a un temps constant.

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS: De la documentation :

Les opérations indexées dans la liste traverseront la liste depuis le début ou la fin, selon ce qui est le plus proche de l'index spécifié.

Opérations telles que:

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

Liste de rôles

En venant

RoleUnresolvedList

En venant

Empiler

En venant

Vecteur

En venant