Algorithmes et structures de données en Java : guide pratique

Algorithmes et structures de données en Java : guide pratique

La maîtrise des algorithmes et des structures de données est une étape clé pour devenir développeur Java. Ce n'est pas seulement de la théorie : comprendre comment fonctionnent les listes, les tables de hachage et les algorithmes de tri influence directement les performances et l'évolutivité de votre code. Dans cet article, nous allons explorer les principales structures de données et algorithmes en Java avec des exemples pratiques qui vous aideront à écrire des programmes plus efficaces.

1. Tableaux dynamiques : ArrayList

ArrayList est une implémentation de tableau dynamique en Java. Contrairement à un tableau classique, sa taille augmente automatiquement lors de l'ajout de nouveaux éléments. C'est l'une des structures de données les plus utilisées.

Opérations de base

\n
• Ajout d'un élément : add(element) — O(1) en moyenne, O(n) lors de l'extension du tableau.
\n
• Récupération d'un élément par index : get(index) — O(1).
\n
• Suppression d'un élément : remove(index) — O(n), car nécessite le décalage des éléments.
\n

import java.util.ArrayList;\n\npublic class ArrayListExample {\n    public static void main(String[] args) {\n        ArrayList<Integer> numbers = new ArrayList<>();\n        \n        numbers.add(10);\n        numbers.add(20);\n        numbers.add(30);\n        \n        System.out.println("Élément à l'index 1 : " + numbers.get(1)); // 20\n        \n        numbers.remove(0); // Supprime le premier élément\n        System.out.println("Taille après suppression : " + numbers.size()); // 2\n    }\n}\n

Quand l'utiliser : Lorsque vous avez besoin d'un accès rapide par index et que vous ajoutez fréquemment des éléments à la fin de la liste.

2. Tables de hachage : HashMap

HashMap est une structure de données qui stocke des paires "clé-valeur". Elle utilise une fonction de hachage pour une recherche rapide. En Java, HashMap est l'une des collections les plus performantes pour les opérations de recherche, d'insertion et de suppression.

Comment ça fonctionne ?

Chaque clé est convertie en un code de hachage qui détermine le "seau" (bucket) où la valeur sera stockée. En cas de collisions (lorsque différentes clés produisent le même hachage), une liste chaînée ou un arbre rouge-noir (depuis Java 8) est utilisé.

Exemple d'utilisation

import java.util.HashMap;\n\npublic class HashMapExample {\n    public static void main(String[] args) {\n        HashMap<String, Integer> studentGrades = new HashMap<>();\n        \n        studentGrades.put("Alice", 90);\n        studentGrades.put("Bob", 85);\n        studentGrades.put("Charlie", 92);\n        \n        // Recherche d'une note\n        int aliceGrade = studentGrades.get("Alice");\n        System.out.println("Note d'Alice : " + aliceGrade); // 90\n        \n        // Vérification de l'existence d'une clé\n        if (studentGrades.containsKey("David")) {\n            System.out.println("David est dans la liste");\n        } else {\n            System.out.println("David n'est pas trouvé");\n        }\n        \n        // Parcours de toutes les entrées\n        for (String name : studentGrades.keySet()) {\n            System.out.println(name + " : " + studentGrades.get(name));\n        }\n    }\n}\n

Complexité des opérations : En moyenne O(1) pour l'insertion, la recherche et la suppression. Dans le pire des cas (avec un grand nombre de collisions) — O(n).

3. Algorithmes de tri en Java

Le tri est l'une des opérations fondamentales. Java fournit des méthodes intégrées, mais comprendre leur fonctionnement interne est essentiel pour écrire un code efficace.

Tri rapide (QuickSort)

C'est l'un des algorithmes de tri les plus rapides. Il fonctionne selon le principe "diviser pour régner" : il choisit un élément pivot et divise le tableau en deux parties — les éléments plus petits et plus grands que le pivot.

public class QuickSort {\n    public static v