Retirer les doublons

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

public class Exo3Doublons {
    // Version 1 : quadratique, avec contains sur la liste résultat.
    static List<String> sansDoublonsNaif(List<String> l) {
        List<String> r = new ArrayList<>();
        for (String s : l) {
            if (!r.contains(s)) r.add(s);
        }
        return r;
    }
    // Version 2 : un LinkedHashSet garde l'ordre d'insertion et ignore les doublons.
    static List<String> sansDoublons(List<String> l) {
        return new ArrayList<>(new LinkedHashSet<>(l));
    }
    public static void main(String[] args) {
        List<String> l = List.of("rouge", "vert", "rouge", "bleu", "vert", "jaune");
        System.out.println(sansDoublonsNaif(l));
        System.out.println(sansDoublons(l));
    }
}

[rouge, vert, bleu, jaune]
[rouge, vert, bleu, jaune]

• Si les $n$ éléments sont distincts, le $k$-ième appel à contains examine les $k-1$ éléments déjà retenus : $0+1+\cdots +(n-1)=n(n-1)/2$ comparaisons. Pour $n=100000$, cela fait environ $5\times 10^9$ comparaisons.
• Un ensemble ignore les doublons ; le LinkedHashSet conserve en plus l'ordre de première insertion, et son contains est en temps constant en moyenne. Un HashSet perdrait l'ordre (son parcours est imprévisible), un TreeSet rangerait les mots par ordre alphabétique.