Structures de données Java

Java fournit un riche ensemble de structures de données pour gérer et organiser les données.

Le paquet java.util de Java fournit des implémentations de nombreuses de ces structures de données, et vous pouvez choisir la classe appropriée selon vos besoins.

Voici quelques structures de données Java courantes :

Tableaux

Les tableaux sont une structure de données de base qui peut stocker une collection de taille fixe d'éléments du même type.

int[] array = new int[5];

• Caractéristiques :Taille fixe, stocke des éléments du même type.
• Avantages :Accès aléatoire efficace aux éléments.
• Inconvénients :Taille fixe, l'insertion et la suppression d'éléments sont relativement lentes.

Listes

Java fournit plusieurs implémentations de listes, telles que ArrayList et LinkedList.

List<String> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

ArrayList :

• Caractéristiques :Tableau dynamique, taille variable.
• Avantages :Accès aléatoire efficace et insertion rapide en fin.
• Inconvénients :L'insertion et la suppression au milieu sont relativement lentes.

LinkedList :

• Caractéristiques :Liste doublement chaînée, les éléments sont reliés par des pointeurs.
• Avantages :Insertion et suppression efficaces d'éléments, bonnes performances d'itération.
• Inconvénients :L'accès aléatoire est relativement lent.

Ensembles

Les ensembles sont utilisés pour stocker des éléments non dupliqués, et les implémentations courantes incluent HashSet et TreeSet.

Set<String> hashSet = new HashSet<>();
Set<Integer> treeSet = new TreeSet<>();

HashSet :

• Caractéristiques :Collection non ordonnée, implémentée à partir de HashMap.
• Avantages :Opérations de recherche et d'insertion efficaces.
• Inconvénients :Ne garantit pas l'ordre.

TreeSet :

• Caractéristiques :TreeSet est une collection ordonnée, implémentée sur la base d'un arbre rouge-noir au niveau inférieur, et n'autorise pas les éléments en double.
• Avantages :Fournit une fonctionnalité de tri automatique, adaptée aux scénarios dans lesquels les éléments doivent être stockés dans l'ordre.
• Inconvénients :Les performances sont relativement faibles, et les éléments null ne peuvent pas être insérés.

Plans

Les maps sont utilisées pour stocker des paires clé-valeur, et les implémentations courantes incluent HashMap et TreeMap.

Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();

HashMap :

• Caractéristiques :Une structure de stockage de paires clé-valeur implémentée à partir d'une table de hachage.
• Avantages :Opérations de recherche, d'insertion et de suppression efficaces.
• Inconvénients :Non ordonné, ne garantit pas l'ordre.

TreeMap :

• Caractéristiques :Une structure de stockage de paires clé-valeur ordonnée implémentée à partir d'un arbre rouge-noir.
• Avantages :Ordonné, prend en charge le parcours dans l'ordre des clés.
• Inconvénients :L'insertion et la suppression sont relativement lentes.

Pile

Une pile est une structure de données linéaire qui gère les éléments selon le principe Dernier entré, premier sorti (LIFO). Dans une pile, les nouveaux éléments sont ajoutés au sommet de la pile, et les éléments ne peuvent être retirés que du sommet de la pile. Cela signifie que le dernier élément ajouté est le premier à être retiré.

Stack<Integer> stack = new Stack<>();

Classe Stack :

• Caractéristiques :Représente une pile, fonctionnant généralement sur les éléments dans un ordre dernier entré, premier sorti (LIFO).

File

Les files d'attente suivent le principe premier entré, premier sorti (FIFO), et les implémentations courantes incluent LinkedList et PriorityQueue.

Queue<String> queue = new LinkedList<>();

Interface Queue :

• Caractéristiques :Représente une file d'attente, fonctionnant généralement sur les éléments dans un ordre premier entré, premier sorti (FIFO).
• Classes d'implémentation : LinkedList, PriorityQueue, ArrayDeque.

Tas

Un tas est la base d'une file de priorité et peut implémenter un tas-max et un tas-min.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Arbres

Java fournit le type TreeNode, qui peut être utilisé pour construire des structures de données telles que des arbres binaires.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Graphes

La représentation des graphes nécessite généralement des structures de données personnalisées ou l'utilisation de bibliothèques de graphes ; Java n'a pas de classe de graphe intégrée.

Ce qui précède ne représente que quelques structures de données courantes en Java. En fait, il existe de nombreuses autres structures de données et algorithmes qui peuvent être sélectionnés et utilisés en fonction de problèmes spécifiques.

---

Autres notes

Les classes suivantes sont traditionnellement des classes historiques. Dans Java 2, un nouveau framework, le Collection Framework, a été introduit, que nous aborderons plus tard.

Enumeration

L'interface Enumeration, bien qu'elle ne soit pas elle-même une structure de données, est largement utilisée dans le cadre d'autres structures de données. L'interface Enumeration définit une manière de récupérer des éléments consécutifs à partir d'une structure de données.

Par exemple, Enumeration définit une méthode appelée nextElement, qui est utilisée pour obtenir l'élément suivant d'une structure de données contenant plusieurs éléments.

Pour plus d'informations sur l'interface Enumeration,veuillez consulter Enumeration。

BitSet

La classe BitSet implémente un groupe de bits ou d'indicateurs qui peuvent être définis et effacés individuellement.

Cette classe est très utile lorsqu'on traite un groupe de valeurs de type boolean. Vous devez seulement assigner un "bit" à chaque valeur, puis définir ou effacer les bits de manière appropriée pour opérer sur les valeurs de type boolean.

Pour plus d'informations sur cette classe,veuillez consulter BitSet。

Vecteur

La classe Vector est très similaire à un tableau traditionnel, mais la taille de Vector peut changer dynamiquement selon les besoins.

Comme les tableaux, les éléments des objets Vector peuvent également être consultés par index.

Le principal avantage d'utiliser la classe Vector est que vous n'avez pas besoin de spécifier une taille pour l'objet lors de sa création ; sa taille change dynamiquement selon les besoins.

Pour plus d'informations sur cette classe,veuillez consulter Vector

Pile

La classe Stack implémente une structure de données dernier entré, premier sorti (LIFO).

Vous pouvez comprendre une pile comme une pile d'objets répartis verticalement. Lorsque vous ajoutez un nouvel élément, vous le placez au-dessus des autres éléments.

Lorsque vous retirez un élément de la pile, vous le prenez au sommet de la pile. En d'autres termes, l'élément qui est entré en dernier dans la pile est retiré en premier.

Pour plus d'informations sur cette classe,veuillez consulter Stack。

Dictionnaire

La classe Dictionary est une classe abstraite qui définit une structure de données qui associe des clés à des valeurs.

Lorsque vous souhaitez accéder aux données via une clé spécifique plutôt qu'un index entier, vous devez utiliser Dictionary.

Comme la classe Dictionary est une classe abstraite, elle fournit uniquement une structure de données pour associer des clés à des valeurs, mais ne fournit pas d'implémentation spécifique.

Pour plus d'informations sur cette classe,veuillez consulter Dictionary。

La classe Dictionary a été dépréciée dans les versions plus récentes de Java. Il est recommandé d'utiliser l'interface Map et ses classes d'implémentation, telles que HashMap, TreeMap, etc., pour remplacer Dictionary.

Pour l'interface Map et ses classes d'implémentation, veuillez vous référer à :Java Collections Framework。

Hashtable

La classe Hashtable fournit un moyen d'organiser les données en fonction d'une structure de clé définie par l'utilisateur.

Par exemple, dans une table de hachage d'une liste d'adresses, vous pouvez stocker et trier les données en fonction du code postal comme clé, plutôt que par le nom de la personne.

La signification spécifique d'une clé de table de hachage dépend entièrement du scénario d'utilisation de la table de hachage et des données qu'elle contient.

Pour plus d'informations sur cette classe,veuillez consulter Hashtable。

Propriétés

Properties hérite de Hashtable. La classe Properties représente un ensemble persistant de propriétés. Chaque clé et sa valeur correspondante dans la liste de propriétés sont des chaînes.

La classe Properties est utilisée par de nombreuses classes Java. Par exemple, elle sert de valeur de retour de la méthode System.getProperties() lors de l'obtention des variables d'environnement.

Pour plus d'informations sur cette classe,voir Properties。

Autres extensions