Trier la liste chaînée en Java

Rashmi Patidar 12 octobre 2023
Trier la liste chaînée en Java

Une liste chaînée en Java est une structure de données ou une collection qui permet aux utilisateurs de créer un tableau dynamique dans la mémoire. La liste ne contient aucune taille prédéfinie. Il crée des nœuds dynamiquement et stocke la valeur et la référence au nœud suivant dans une seule adresse mémoire. Les éléments de la liste conservent les valeurs dans l’ordre séquentiel, ou la liste conserve l’ordre d’insertion dans lequel les éléments sont insérés.

Le tri est défini comme la méthode d’organisation des éléments d’une structure de données dans un ordre défini. L’arrangement peut être soit dans l’ordre croissant ou décroissant, selon les besoins. Notez qu’il peut y avoir différentes approches pour trier la collection de listes.

Ci-dessous se trouve le bloc de code pour trier les éléments du tableau.

import java.text.Collator;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("ab");
    list.add("bb");
    list.add("aA");
    list.add("bB");
    System.out.println(list);
    list.sort(new Comparator<String>() {
      @Override
      public int compare(String s1, String s2) {
        return Collator.getInstance().compare(s1, s2);
      }
    });
    System.out.println(list);
  }
}

Dans le bloc de code ci-dessus, une liste est instanciée à l’aide du mot-clé new. Le mot-clé instancie la liste chaînée des types de données String et appelle le constructeur en interne. Ensuite, l’instance de liste appelle la méthode add pour remplir les éléments de la liste. La valeur est imprimée pour vérifier l’ordre d’insertion.

La méthode sort est présente dans l’interface List. La fonction trie la liste en fonction d’un comparateur donné en paramètre. Le comparateur s’habitue à comparer la liste des éléments passés.

Le point à considérer est de trier les valeurs passées et de s’assurer qu’elles doivent être du même type. Si les valeurs ne sont pas du même type ou lorsque les éléments ne sont pas comparables, la classe lève ClassCastException.

L’implémentation interne du tri se fait à l’aide de la commande merge sort qui est assez efficace et fait la comparaison dans le temps log n. Ainsi, une instance new Comparator est formée qui remplace la méthode compare. L’implémentation est une manière traditionnelle de remplacer une méthode et de fournir l’implémentation.

Au lieu de cela, une implémentation simple utilisant les fonctions lambda Java 8 peut être utilisée. L’interface est une interface fonctionnelle et a une seule méthode à appeler. Le lambda prend directement le nombre de paramètres présents dans l’interface. La représentation Java 8 à une ligne du code ci-dessus est illustrée ci-dessous.

list.sort((o1, o2) -> Collator.getInstance().compare(o1, o2));

L’instruction réelle pour comparer les éléments de la liste est la classe collator. Cette classe est de nature abstraite et définit les prototypes des méthodes. L’implémentation est présente dans la classe abstraite qui les étend.

La classe collator compare la chaîne sensible aux paramètres régionaux. La méthode getInstance obtient l’instance avec la valeur Locale par défaut actuelle. La fonction compare compare les valeurs basées sur le Collator et renvoie +1, -1 ou 0, en fonction des valeurs supérieures à, inférieures ou égales.

La sortie du code ci-dessus est illustrée ci-dessous. La deuxième ligne représente la sortie sous une forme arrangée. Selon la séquence ASCII des caractères sur le clavier, les lettres majuscules se situent dans la plage supérieure (A-Z) que les petits alphabets (a-z). Ainsi, la liste résultante dans la deuxième ligne imprime d’abord la petite casse bb puis bB car elle a un alphabet en majuscule.

[ab, bb, aA, bB][aA, ab, bb, bB]
Rashmi Patidar avatar Rashmi Patidar avatar

Rashmi is a professional Software Developer with hands on over varied tech stack. She has been working on Java, Springboot, Microservices, Typescript, MySQL, Graphql and more. She loves to spread knowledge via her writings. She is keen taking up new things and adopt in her career.

LinkedIn

Article connexe - Java Linked List

Article connexe - Java List