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

Algorithmes et structures de données en Java : de la théorie à la pratique

La compréhension des algorithmes et des structures de données est le fondement sur lequel repose la carrière de tout développeur Java. Sans ces connaissances, il est difficile d'écrire un code efficace, évolutif et maintenable. Dans cet article, nous allons analyser les structures de données et les algorithmes clés que vous utiliserez quotidiennement, et montrer leur implémentation en Java avec des exemples pratiques.

1. Structures de données de base dans Java Collections Framework

Java propose un framework de collections puissant qui inclut les structures de données essentielles. Examinons les trois plus populaires.

ArrayList — tableau dynamique

ArrayList est une implémentation de tableau dynamique. Il s'étend automatiquement lors de l'ajout de nouveaux éléments, ce qui en fait un excellent choix pour les listes dont la taille n'est pas connue à l'avance.

import java.util.ArrayList;

public class ArrayListExample {    public static void main(String[] args) {        ArrayList<String> fruits = new ArrayList<>();        fruits.add("Pomme");        fruits.add("Banane");        fruits.add("Orange");

        System.out.println("Deuxième élément : " + fruits.get(1)); // Banane        fruits.remove(0);        System.out.println("Taille après suppression : " + fruits.size()); // 2                for (String fruit : fruits) {            System.out.println(fruit);        }    }}

Complexité des opérations : accès par index — O(1), insertion/suppression au milieu — O(n).

HashMap — table de hachage

HashMap stocke des paires «clé-valeur» et permet un accès quasi instantané aux données par clé.

import java.util.HashMap;

public class HashMapExample {    public static void main(String[] args) {        HashMap<String, Integer> ages = new HashMap<>();        ages.put("Anne", 25);        ages.put("Jean", 30);        ages.put("Marie", 28);

        System.out.println("Âge d'Anne : " + ages.get("Anne")); // 25                // Vérification de l'existence d'une clé        if (ages.containsKey("Jean")) {            System.out.println("Jean trouvé !");        }                // Parcours de toutes les entrées        for (String name : ages.keySet()) {            System.out.println(name + " : " + ages.get(name) + " ans");        }    }}

Complexité des opérations : insertion, recherche, suppression — en moyenne O(1).

LinkedList — liste doublement chaînée

LinkedList est composée de nœuds, chacun stockant des références vers l'élément précédent et suivant. Idéale pour les insertions et suppressions fréquentes au début ou à la fin de la liste.

import java.util.LinkedList;

public class LinkedListExample {    public static void main(String[] args) {        LinkedList<Integer> queue = new LinkedList<>();                // Utilisation comme file (FIFO)        queue.addLast(1);        queue.addLast(2);        queue.addLast(3);                System.out.println("Premier dans la file : " + queue.getFirst()); // 1        queue.removeFirst();        System.out.println("Après suppression : " + queue); // [2, 3]                // Utilisation comme pile (LIFO)        queue.push(10); // ajout au début        queue.push(20);        System.out.println("Sommet de la pile : " + queue.pop()); // 20    }}

Complexité des opérations : insertion/suppression au début/à la fin — O(1), accès par index — O(n).

2. Algorithmes de tri en Java

Le tri est l'une des tâches les plus courantes. Examinons deux implémentations classiques.

Tri à bulles (Bubble Sort)

Algorithme simple mais lent. Utilisé à des fins pédagogiques.

public class BubbleSort {    public static void bubbleSort(int[] arr) {        int n = arr.length;        boolean swapped;                for (i