Dans cet article, vous apprenez ce qu'est une structure de données, les types de structure de données en Java, les opérations sur les structures de données et la complexité des algorithmes. La structure de données est utilisée pour organiser, gérer et stocker efficacement les données en mémoire afin de faciliter l'accès et la modification des données. L'étude de la structure de données comprend les points suivants :
La structure de données en Java est largement classée dans les deux catégories suivantes :
- Structure de données primitives
- Structure de données non primitive
Structure de données primitive en Java
Les structures de données primitives en Java sont des structures de données fondamentales.
Elles peuvent être directement exploitées par des instructions machine.
Elles sont disponibles dans la plupart des langages de programmation en tant que types intégrés.
La taille d'une structure de données primitive dépend du type de structure de données.
Les structures de données primitives contiennent une seule valeur à un emplacement particulier, contrairement aux structures de données non primitives.
int, float, boolean, char sont quelques exemples de structures de données primitives en Java.
Structures de données non primitives en Java
Les structures de données non primitives en Java sont dérivées des structures de données primitives.
Elles sont plus compliquées que les structures de données primitives en Java.
Elles sont largement classées dans les 2 catégories suivantes :
Structure de données linéaire
Structure de données non-linéaires.
Structure de données linéaire en Java
Une structure de données linéaire en Java est une structure dans laquelle les données sont stockées dans un ordre linéaire ou séquentiel.
Les structures de données linéaires peuvent être représentées de deux manières différentes en mémoire. Dans la première façon, les éléments sont stockés séquentiellement en mémoire. Par exemple, un tableau occupe la mémoire dans un ordre séquentiel. Dans la deuxième façon, les éléments ont une relation linéaire à l'aide d'un lien. Par exemple, les nœuds de la liste liée sont liés entre eux car leurs nœuds sont disposés en mémoire dans un ordre non séquentiel. Les opérations effectuées à l'aide d'une structure de données linéaire sont la traversée, l'insertion, la suppression, la recherche, le tri et la fusion. Les structures de données linéaires ne font pas toujours le meilleur usage de la mémoire et peuvent entraîner un gaspillage de celle-ci. Voici quelques exemples de structures de données linéaires :
- Tableau
- Liste liée
- Pile
- File d'attente.
Tableau
Un tableau est une collection de taille fixe d'éléments de même type de données. Un tableau est la structure de données la plus couramment utilisée dans de nombreux algorithmes. Les éléments d'un tableau sont stockés dans des emplacements mémoire contigus et sont accessibles à l'aide d'un index. Les opérations de base qui peuvent être effectuées sur un tableau sont l'insertion, la suppression, la recherche, la mise à jour et le parcours d'un tableau. Les tableaux peuvent être de type - tableau à une dimension, tableaux multidimensionnels et tableaux dynamiques.
Liste liée
Une liste liée est une structure de données qui contient un ensemble de nœuds. Chaque nœud stocke des données et l'adresse du nœud suivant. Les nœuds se connectent ensemble pour former une structure similaire à une chaîne. La liste liée peut être de type - Liste liée simple, liste liée double et liste liée circulaire.
Pile
Une pile est une structure de données en Java dans laquelle les éléments sont insérés et supprimés à partir d'une seule extrémité.
La pile est également connue sous le nom de structure de données last in first out (LIFO).
Un tableau ou une liste chaînée peuvent être utilisés pour mettre en œuvre une pile.
Les opérations de base qu'une pile peut effectuer sont les suivantes :
- Push - pour insérer des données dans une pile et les placer au sommet.
- Pop - pour supprimer les données du haut de la pile.
- Peek - pour regarder les données au sommet sans les supprimer.
File d'attente
La file d'attente est une structure de données qui permet l'insertion à une extrémité et la suppression à l'autre extrémité.
L'extrémité à laquelle la suppression se produit est appelée extrémité FRONT.
L'extrémité où se produit l'insertion est appelée extrémité REAR.
La file d'attente est également connue sous le nom de structure de données First in First out (FIFO).
La structure de données de la file d'attente est implémentée à l'aide d'un tableau.
Les opérations qui peuvent être effectuées sur la file d'attente sont les suivantes :
- pour insérer des données dans une file d'attente et les placer à l'arrière.
- pour retirer les données à l'avant.
- pour retourner les données à l'avant sans les retirer.
Structures de données hiérarchiques ou non linéaires en Java
Les structures de données non linéaires stockent les données dans un ordre non séquentiel formant une relation hiérarchique entre les éléments parents et enfants.
Elles sont réparties à l'intérieur de la mémoire à différents endroits et ne peuvent être retracées que par l'adresse.
Les structures de données non linéaires en Java sont efficaces en termes de mémoire.
Les types de structures de données non linéaires en Java sont les suivants :
- Arbre
- Graph
Arbre
Un arbre est défini comme un ensemble de nœuds de données dans lequel les données sont organisées en branches et sous-branches.
Les arbres représentent des relations hiérarchiques entre différents éléments. L'arbre est constitué de nœuds qui sont reliés par des liens. Un nœud est représenté par un cercle et des liens sont utilisés pour connecter les nœuds. Contrairement à la liste liée où un nœud ne peut être connecté qu'à un seul nœud, un arbre peut avoir un nœud connecté à deux nœuds ou plus. Les arbres peuvent être de type : arbre général, arbre binaire, arbre de recherche binaire, etc.
Graphe:
Un graphe est une collection de nœuds et de relations logiques entre les nœuds. Les graphes peuvent être de type : graphe dirigé, graphe non dirigé, graphe mixte, graphe simple etc.
Opérations sur les structures de données:
Les opérations les plus courantes effectuées sur une structure de données sont les suivantes :
- Sélectionner : Select fait référence à l'accès à une donnée particulière dans une structure de données.
- Mettre à jour : Il s'agit de mettre à jour ou de modifier des données dans une structure de données.
- Rechercher : Elle permet de trouver la présence d'une donnée dans une structure de données.
- Trier : Le tri est un processus qui consiste à classer tous les éléments de la structure de données dans un ordre particulier, soit ascendant, soit descendant.
- Fusionner : La fusion combine les données de deux structures de données du même type en une seule structure.
- Traverse : traverse chaque nœud dans un ordre systématique.
Complexité temporelle et spatiale des algorithmes:
Les algorithmes sont des programmes à l'aide desquels les structures de données sont mises en œuvre.
Il existe deux mesures principales de l'efficacité d'un algorithme
- La complexité temporelle : C'est une fonction qui détermine le temps que prend l'algorithme
- La complexité spatiale : c'est une fonction qui détermine la quantité d'espace mémoire que prend l'algorithme.
La complexité est classée en trois grandes catégories : analyse du pire cas, analyse du cas moyen et analyse du meilleur cas.