ICS4U

Accueil > Structures de données et algorithmes >

📚 Quelques structures de données et des classes Java qui s’en servent

Survol et attentes

Peut-être vous avez trouvé la taille fixe d’un tableau limitant. Ou possiblement vous aurez préférez liez deux données ensemble au lieu de créer deux tableaux parallèles.

La bonne nouvelle est que des structures de données autres que les tableaux existent et, entre autres, résolvent ces deux problèmes.

Représentations internes

Un tableau est une séquence continue de cellules en mémoire pour le même type de donnée :

Pour accéder aux éléments du tableau, on spécifie le nom de la variable (qui donne l’adresse du tableau) puis l’index (le nombre de pas à partir du début du tableau). Cela nous donne un accès direct à chaque élément via son index.

Une liste est une structure de données où l’information vient avec un ou deux pointeurs. Avec un pointeur, le pointeur donne l’adresse du prochain élément dans la liste. Avec deux pointeurs, un des pointeurs donne aussi l’adresse de l’élément précédent.

Pour accéder aux éléments d’une liste, on doit faire une recherche ;(. Par contre c’est très simple et rapide d’ajouter ou de supprimer des valeurs : on modifie les pointeurs des éléments précédents et subséquents. Les informations peuvent aussi se trouver n’importe où en mémoire, pas nécessairement en cellules collées.

Une table de hachage associe une clé à une valeur. Toutes les valeurs se trouvent dans un tableau et la clé, qui peut être de n’importe quel type, est utilisée dans une fonction de hachage pour donner l’adresse en mémoire de la valeur.

On accède aux valeurs en donnant la clé, ce qui est pratique si on a plusieurs informations à associer et que l’ordre (l’index) dans le tableau n’est pas important. L’accès est direct, comme avec les tableaux.

Utilité

La classe ArrayList offre un tableau qui au une taille modifiable, ce qui surmonte la plus grande limitation des tableaux de base.

Déclarations des objets

Les classes Java définissent la structure des données et leur comportements, mais n’indique pas le type de valeurs qu’elles contiennent, contrairement à la notation pour les tableaux qui s’ajoutent directement au type.

Il faut donc spécifier le type d’Object entre des crochets pointus suivant le nom de l’objet. Le format est :

1
Structure<Type> nomDeVariable = new Structure<>();

Et voici quelques exemples :

1
2
3
4
5
ArrayList<Integer> values = new ArrayList<>();
LinkedList<String> pages = new LinkedList<>();

// associer le nom au numéro de téléphone
HashMap<String,Long> phoneBook = new HashMap<>();

Notez que values contient des nombres entiers, mais on a utilisé Integer comme type et non int. C’est parce qu’il faut passer une classe. Pour chaque type primitif, il y a une classe “enveloppe” associée (p. ex. int -> Integer, long -> Long) qui lui offre certaines valeurs et comportements additionnels tout en augmentant son intégration dans le reste du code Java.

Notez aussi que pour la déclaration du HashMap, il fallait passer deux types : le premier pour la clé et le deuxième pour la valeur.

Objectifs d’apprentissage

À la fin de cette leçon vous devrez être en mesure de :

• Décrire la structure interne d’un tableau, d’une liste et d’une table de hachage, notamment en identifiant les avantages et les cas d’utilisation typiques de chacune.
• Reconnaître les différentes méthodes pour ajouter, enlever et accéder aux éléments d’un ArrayList et d’un HashMap et de traverser les valeurs de chacun.

Critères de succès

• Je suis capable d’utiliser des ArrayList et HashMap dans mes programmes pour simplifier la gestion de collections de données ou optimiser les performances.

Notes

Notes additionnelles sur les structures de données Java

Exercices

ArrayList

• CSAwesome - chapitre 7 : sections 1 à 3 (bases) et 4 (problèmes)

HashMap

• vidéo (Coding With John)
• exemples interactifs (W3Schools)
• problèmes (CodingBat : sections Map-1 et Map-2)