Principales structures de données et algorithmes Java que vous devez connaître

Si je devais choisir le sujet le plus important du développement logiciel, ce serait les structures de données et les algorithmes. Vous pouvez le considérer comme l'outil fondamental à la disposition de tout programmeur informatique. Lors de la programmation, nous utilisons structures de données pour stocker et organiser les données, et algorithmes pour manipuler les données dans ces structures. Cet article contient une revue détaillée de toutes les structures de données et algorithmes courants dans pour permettre aux lecteurs de devenir bien équipés.

Vous trouverez ci-dessous les sujets abordés dans cet article:

java convertir de double en int

• Structures de données en Java
  • Structures de données linéaires
  • Structures de données hiérarchiques
• Algorithmes en Java
  • Algorithmes de tri
  • Recherche d'algorithmes

Structures de données en Java

Une structure de données est un moyen de stocker et d'organiser des données dans un ordinateur afin qu'elles puissent être utilisées efficacement. Il fournit un moyen de gérer efficacement de grandes quantités de données. Et des structures de données efficaces sont essentielles pour concevoir des algorithmes efficaces.

Danscet article «Structures de données et algorithmes en Java», nous allons couvrir les structures de données de base telles que:

• Structures de données linéaires
  • Liste liée
  • Piles
  • Files d'attente

• Structures de données hiérarchiques
  • Arbres binaires
  • Tas
  • Tables de hachage

Voyons chacun d’entre eux.

Structures de données linéaires en Java

Structures de données linéaires dans sont ceux dont les éléments sont séquentiels et ordonnés de telle sorte que: il n'y en a qu'un premier élément et n'en a qu'un élément suivant , il n'y a qu'un seul dernier élément et n'en a qu'un élément précédent , tandis que tous les autres éléments ont un Suivant et un précédent élément.

Tableaux

Une tableau est une structure de données linéairereprésentant un groupe d'éléments similaires, accessibles par index. La taille d'un tableau doit être fournie avant de stocker les données. Vous trouverez ci-dessous les propriétés d'un tableau:

• Chaque élément d'un tableau est du même type de données et a la même taille
• Les éléments du tableau sont stockés dans des emplacements de mémoire contigus, le premier élément commençant au plus petit emplacement de mémoire
• Les éléments du tableau sont accessibles de manière aléatoire
• La structure des données du tableau n'est pas complètement dynamique

Par exemple , nous souhaitons peut-être qu'un jeu vidéo garde une trace des dix meilleurs scores de ce jeu. Plutôt que d'en utiliser dix variables pour cette tâche, nous pourrions utiliser un seul nom pour l'ensemble du groupe et utiliser des numéros d'index pour désigner les scores élevés de ce groupe.

Liste liée

À est une structure de données linéaire avec la collection de plusieurs nœuds, où eChaque élément stocke ses propres données et un pointeur vers l'emplacement de l'élément suivant. Le dernier lien d'une liste liée pointe vers null, indiquant la fin de la chaîne. Un élément d'une liste liée est appelé un nœud . Le premier nœud s'appelle le tête .Le dernier nœud est appeléla queue .

Types de liste liée

Liste à liaison unique (unidirectionnelle)

Liste doublement liée (bidirectionnelle)

Liste liée circulaire

Voici un exemple simple: Imaginez une liste chaînée comme une chaîne de trombones reliés entre eux. Vous pouvez facilement ajouter un autre trombone en haut ou en bas. Il est même rapide d’en insérer un au milieu. Tout ce que vous avez à faire est de simplement déconnecter la chaîne au milieu, ajouter le nouveau trombone, puis reconnecter l'autre moitié. Une liste chaînée est similaire.

Piles

Empiler, une structure de données abstraite, est une collection de objets insérés et retirés selon le dernier entré, premier sorti (LIFO) principe. Les objets peuvent être insérés dans une pile à tout moment, mais seul le dernier objet inséré (c'est-à-dire le «dernier») peut être supprimé à tout moment.Vous trouverez ci-dessous les propriétés d'une pile:

• C'est une liste ordonnée dans laquellel'insertion et la suppression ne peuvent être effectuées qu'à une seule extrémité appelée Haut
• Structure de données récursive avec un pointeur vers son élément supérieur
• Suit le dernier entré, premier sorti (LIFO) principe
• Prend en charge les deux méthodes les plus fondamentales
  • push (e): insérer l'élément e, en haut de la pile
  • pop (): Retirez et retournez l'élément supérieur de la pile

Des exemples pratiques de la pile incluent lors de l'inversion d'un mot,pour vérifier l'exactitude de parenthèsesséquence,implémenter la fonctionnalité de retour dans les navigateurs et bien d'autres.

Files d'attente

sont également un autre type de structure de données abstraite. Contrairement à une pile, la file d'attente est une collection d'objets qui sont insérés et supprimés selon le premier entré, premier sorti (FIFO) principe. Autrement dit, les éléments peuvent être insérés à tout moment, mais seul l'élément qui a été dans la file d'attente le plus longtemps peut être supprimé à tout moment.Vous trouverez ci-dessous les propriétés d'une file d'attente:

• Souvent appelé le premier entré, premier sorti liste
• Prend en charge les deux méthodes les plus fondamentales
  • mettre en file d'attente (e): insérer l'élément e, au arrière de la file d'attente
  • dequeue (): supprime et renvoie l'élément du de face de la file d'attente

Les files d'attente sont utilisées danstransfert asynchrone de données entre deux processus, planification du processeur, planification de disque et autres situations où les ressources sont partagées entre plusieurs utilisateurs et servies sur la base du premier arrivé, premier serveur. Ensuite, dans cet article «Structures de données et algorithmes en Java», nous avons des structures de données hiérarchiques.

Structures de données hiérarchiques en Java

Arbre binaire

L'arbre binaire est unstructures de données arborescentes hiérarchiques dans lesquelles chaque nœud a au plus deux enfants , qui sont appelés enfant gauche et le bon enfant . Chaque arbre binaire a les groupes de nœuds suivants:

• Nœud racine: il s'agit du nœud le plus élevé et souvent appelé nœud principalcar tous les autres nœuds peuvent être atteints à partir de la racine
• Sous-arbre gauche, qui est également un arbre binaire
• Sous-arbre droit, qui est également un arbre binaire

Vous trouverez ci-dessous les propriétés d'un arbre binaire:

• Un arbre binaire peut être parcouru de deux manières:
  • Première traversée en profondeur : Dans l'ordre (gauche-racine-droite), précommande (racine-gauche-droite) et post-ordre (gauche-droite-racine)
  • Largeur première traversée : Traversée de l'ordre des niveaux
• Complexité temporelle de la traversée des arbres: O (n)
• Le nombre maximal de nœuds au niveau «l» = 2^l-1.

Les applications des arbres binaires incluent:

• Utilisé dans de nombreuses applications de recherche où les données entrent / sortent constamment
• En tant que flux de travail pour la composition d'images numériques pour des effets visuels
• Utilisé dans presque tous les routeurs à bande passante élevée pour stocker les tables de routeurs
• Également utilisé dans les réseaux sans fil et l'allocation de mémoire
• Utilisé dans les algorithmes de compression et bien d'autres

Tas binaire

Binary Heap est unarbre binaire, qui répond à la propriété du tas. En termes simples, ilest une variante d'un arbre binaire avec les propriétés suivantes:

• Heap est un arbre binaire complet: Un arbre est dit complet si tous ses niveaux, sauf peut-être le plus profond, sont complets. Tsa propriété de Binary Heap le rend approprié pour être stocké dans un .
• Suit la propriété du tas: Un tas binaire est soit un Min-Heap ou un Max-Heap .
  • Tas binaire min: Fou chaque nœud d'un tas, la valeur du nœud est inférieur ou égal à valeurs des enfants
  • Tas binaire maximum: Fou chaque nœud d'un tas, la valeur du nœud est Plus grand ou égal à valeurs des enfants

Les applications populaires du tas binaire incluentimplémenter des files d'attente de priorité efficaces, trouver efficacement les k plus petits (ou plus grands) éléments d'un tableau et bien d'autres.

Tables de hachage

Imaginez que vous avez un objet et vous souhaitez lui attribuer une clé pour faciliter la recherche. Pour stocker cette paire clé / valeur, vous pouvez utiliser un tableau simple comme une structure de données où les clés (entiers) peuvent être utilisées directement comme index pour stocker les valeurs de données. Cependant, dans les cas où les clés sont trop grandes et ne peuvent pas être utilisées directement comme index, une technique appelée hachage est utilisée.

Dans le hachage, les grandes clés sont converties en petites clés en utilisant fonctions de hachage . Les valeurs sont ensuite stockées dans une structure de données appeléeà table de hachage. Une table de hachage est une structure de données qui implémente un dictionnaire ADT, une structure qui peut mapper des clés uniques à des valeurs.

En général, une table de hachage comporte deux composants principaux:

1. Baie de godets: Un tableau de compartiment pour une table de hachage est un tableau A de taille N, où chaque cellule de A est considérée comme un «compartiment», c'est-à-dire une collection de paires clé-valeur. L'entier N définit la capacité du tableau.
2. Fonction de hachage: C'est n'importe quelle fonction qui mappe chaque clé k de notre carte à un entier dans la plage [0, N & moins 1], où N est la capacité du tableau de compartiment pour cette table.

Lorsque nous mettons des objets dans une table de hachage, il est possible que différents objets aient le même code de hachage. C'est ce qu'on appelle un collision . Pour gérer les collisions, il existe des techniques comme le chaînage et l'adressage ouvert.

Voici donc quelques structures de données de base et les plus fréquemment utilisées en Java. Maintenant que vous connaissez chacun de ces éléments, vous pouvez commencer à les implémenter dans votre . Avec cela, nous avons terminé la première partie de cet article sur «Structures de données et algorithmes en Java». Dans la partie suivante, nous allons en apprendre davantage suralgorithmes de base et comment les utiliser dans des applications pratiques telles que le tri et la recherche, diviser pour conquérir, algorithmes gourmands, programmation dynamique.

Algorithmes en Java

Historiquement utilisés comme outil de résolution de calculs mathématiques complexes, les algorithmes sont profondément liés à l'informatique, et en particulier aux structures de données. Un algorithme est une séquence d'instructions décrivant une manière de résoudre un problème spécifique dans un laps de temps limité. Ils sont représentés de deux manières:

• Organigrammes - C'est unreprésentation visuelle du flux de contrôle d'un algorithme
• Pseudocode - Ilest une représentation textuelle d'un algorithme qui se rapproche du code source final

Remarque: Les performances de l'algorithme sont mesurées en fonction de la complexité temporelle et spatiale. La plupart du temps, la complexité de tout algorithme dépend du problème et de l'algorithme lui-même.

Explorons les deux principales catégories d'algorithmes en Java, à savoir:

• Tri des algorithmes en Java
• Recherche d'algorithmes en Java

Tri des algorithmes en Java

Les algorithmes de tri sont des algorithmes qui placent les éléments d'une liste dans un certain ordre. Les ordres les plus couramment utilisés sont l'ordre numérique et l'ordre lexicographique. Dans cet article «Structures de données et algorithmes», explorons quelques algorithmes de tri.

Tri à bulles en Java

Le tri à bulles, souvent appelé tri par affaissement, est l'algorithme de tri le plus simple. Il parcourt à plusieurs reprises la liste à trier, compare chaque paire d'éléments adjacents et les échange s'ils sont dans le mauvais ordre.Le tri à bulles tire son nom du fait qu'il filtre les éléments en haut du tableau, comme des bulles qui flottent sur l'eau.

Voicipseudocode représentant l'algorithme de tri à bulles (contexte de tri croissant).

a [] est un tableau de taille N begin BubbleSort (a []) déclare l'entier i, j pour i = 0 à N - 1 pour j = 0 à N - i - 1 si a [j]> a [j + 1 ] puis swap a [j], a [j + 1] end if end pour return a end BubbleSort

Ce code classe un tableau unidimensionnel de N éléments de données dans l'ordre croissant. Une boucle externe fait N-1 passages sur le tableau. Chaque passage utilise une boucle interne pour échanger des éléments de données de sorte que le plus petit élément de données suivant «bouillonne» vers le début du tableau. Mais le problème est que l'algorithme a besoin d'une passe entière sans aucun échange pour savoir que la liste est triée.

Complexité temporelle pire et moyenne: O (n * n). Le pire des cas se produit lorsqu'un tableau est trié à l'envers.

Meilleure complexité temporelle: Sur). Le meilleur cas se produit lorsqu'un tableau est déjà trié.

Tri par sélection en Java

Le tri par sélection est une combinaison de recherche et de tri. L'algorithme trie un tableau en trouvant à plusieurs reprises l'élément minimum (en tenant compte de l'ordre croissant) de la partie non triée et en le plaçant à une position appropriée dans le tableau.

Voici le pseudocode représentant l'algorithme de tri par sélection (contexte de tri croissant).

a [] est un tableau de taille N begin SelectionSort (a []) for i = 0 to n - 1 / * définir l'élément actuel comme minimum * / min = i / * trouver l'élément minimum * / pour j = i + 1 à n si liste [j]
Comme vous pouvez le comprendre à partir du code, le nombre de fois où le tri traverse le tableau est inférieur de un au nombre d'éléments du tableau. La boucle interne trouve la valeur la plus petite suivante et la boucle externe place cette valeur à son emplacement approprié. Le tri par sélection n'effectue jamais plus de O (n) swaps et peut être utile lorsque l'écriture en mémoire est une opération coûteuse.
 Complexité temporelle: Sur2) car il y a deux boucles imbriquées.
 Espace auxiliaire: Ou (1).
 Tri par insertion en Java 
Le tri par insertion est un algorithme de tri simple qui itère dans la liste en consommant un élément d'entrée à la fois et construit le tableau trié final. C'est très simple et plus efficace sur des ensembles de données plus petits. C'est une technique de tri stable et en place.
Voici le pseudocode représentant l'algorithme de tri par insertion (contexte de tri croissant).
a [] est un tableau de taille N begin InsertionSort (a []) for i = 1 to N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 end while a [j + 1] = key end for end InsertionSort
Comme vous pouvez le comprendre à partir du code, l'algorithme de tri par insertionsupprime un élément des données d'entrée, trouve l'emplacement auquel il appartient dans la liste triée et l'insère à cet endroit. Il se répète jusqu'à ce qu'aucun élément d'entrée ne reste non trié.
 Meilleur cas: Le meilleur cas est lorsque l'entrée est un tableau déjà trié. Dans ce cas, le tri par insertion a un temps d'exécution linéaire (c'est-à-dire & Theta (n)).
 Pire cas:  L'entrée la plus simple du pire des cas est un tableau trié dans l'ordre inverse.
 QuickSort en Java 
L'algorithme de tri rapide est un algorithme de tri rapide, récursif et non stable qui fonctionne selon le principe de division et de conquête. Il sélectionne un élément comme pivot et partitionne le tableau donné autour de ce pivot sélectionné.
 Étapes de mise en œuvre du tri rapide:  
 
Choisissez un «point de pivot» approprié.
Divisez les listes en deux listesbasé sur cet élément pivot. Chaque élément qui est plus petit que l'élément pivot est placé dans la liste de gauche et chaque élément qui est plus grand est placé dans la liste de droite. Si un élément est égal à l'élément pivot, il peut figurer dans n'importe quelle liste. C'est ce qu'on appelle l'opération de partition.
Triez de manière récursive chacune des petites listes. 
Voici le pseudocode représentant l'algorithme de tri rapide.
QuickSort (A as array, low as int, high as int) {if (low
Dans le pseudocode ci-dessus, cloison() la fonction exécute l'opération de partition et Tri rapide() function appelle à plusieurs reprises la fonction de partition pour chaque petite liste générée. La complexité du tri rapide dans le cas moyen est & Theta (n log (n)) et dans le pire des cas est & Theta (n2).
 Fusionner le tri en Java 
Mergesort est un algorithme de tri rapide, récursif et stable qui fonctionne également selon le principe de division et de conquête. Similaire au tri rapide, le tri par fusion divise la liste des éléments en deux listes. Ces listes sont triées indépendamment puis combinées. Lors de la combinaison des listes, les éléments sont insérés (ou fusionnés) au bon endroit dans la liste.
Voici le pseudocode représentant l'algorithme de tri par fusion.
qu'est-ce que le vecteur en java
procedure MergeSort (a as array) if (n == 1) return a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end procedure procedure merge (a as array, b as array) var c as array while (a et b ont des éléments) if ( a [0]> b [0]) ajouter b [0] à la fin de c supprimer b [0] de b sinon ajouter un [0] à la fin de c supprimer a [0] d'une fin si fin pendant que (a has elements) add a [0] to the end of c remove a [0] from a end while while (b has elements) add b [0] to the end of c remove b [0] from b end while return c fin de la procédure
 tri par fusion() La fonction divise la liste en deux, appelle tri par fusion() sur ces listes séparément puis les combine en les envoyant comme paramètres à la fonction merge ().L'algorithme a une complexité de O (n log (n)) et a une large gamme d'applications.
 Tri de tas en Java 
Heapsort est un algorithme de tri basé sur la comparaisonStructure de données du tas binaire. Vous pouvez le considérer comme un tri de sélection amélioré de la version f, oùil divise son entrée en une région triée et une région non triée, et il réduit de manière itérative la région non triée en extrayant l'élément le plus grand et en le déplaçant vers la région triée.
 Étapes à suivre pour mettre en œuvre Quicksort (par ordre croissant): 
Construire un tas max avec le tableau de tri
À ce pointt, le plus gros élément est stocké à la racine du tas. Remplacez-le par le dernier élément du tas et réduisez la taille du tas de 1. Enfin, amassez la racine de l'arbre
Répétez les étapes ci-dessus jusqu'à ce que la taille du tas soit supérieure à 1
Voici le pseudocode représentant l'algorithme de tri de tas.
Heapsort (a as array) for (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) greater = i // Initialise le plus grand en tant que racine int l eft = 2 * i + 1 // left = 2 * i + 1 int droite = 2 * i + 2 // droite = 2 * i + 2 si (gauche a [plus grand]) plus grand = gauche si (droite a [plus grand]) plus grand = droite si (plus grand! = I) swap ( a [i], A [plus grand]) Heapify (a, n, plus grand) end heapify
En dehors de ceux-ci, il existe d'autres algorithmes de tri qui ne sont pas très connus, tels que Introsort, Counting Sort, etc. Passons au prochain ensemble d'algorithmes de cet article sur les «Structures de données et algorithmes», explorons les algorithmes de recherche.
 Recherche d'algorithmes en Java 
La recherche est l'une des actions les plus courantes et les plus fréquemment exécutées dans les applications d'entreprise classiques. Les algorithmes de recherche sont des algorithmes permettant de trouver un élément avec des propriétés spécifiées parmi une collection d'éléments. Explorons deux des algorithmes de recherche les plus couramment utilisés.
 Algorithme de recherche linéaire en Java 
La recherche linéaire ou la recherche séquentielle est l'algorithme de recherche le plus simple. Cela implique une recherche séquentielle d'un élément dans la structure de données donnée jusqu'à ce que l'élément soit trouvé ou que la fin de la structure soit atteinte. Si l'élément est trouvé, l'emplacement de l'élément est renvoyé, sinon l'algorithme renvoie NULL.
Voici le pseudocode représentant la recherche linéaire en Java:
procedure linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search
C'est unalgorithme de force brute.Bien que ce soit certainement le plus simple, ce n’est certainement pas le plus courant, en raison de son inefficacité. La complexité temporelle de la recherche linéaire est SUR) .
 Algorithme de recherche binaire en Java 
La recherche binaire, également appelée recherche logarithmique, est un algorithme de recherche qui trouve la position d'une valeur cible dans un tableau déjà trié. Il divise la collection d'entrée en deux moitiés égales et l'élément est comparé à l'élément du milieu de la liste. Si l'élément est trouvé, la recherche s'arrête là. Sinon, nous continuons à rechercher l'élément en divisant et en sélectionnant la partition appropriée du tableau, en fonction du fait que l'élément cible est plus petit ou plus grand que l'élément du milieu.
Voici le pseudocode représentant la recherche binaire en Java:
Procédure binary_search un tableau trié n taille du tableau x valeur à rechercher lowerBound = 1 upperBound = n tandis que x non trouvé si upperBound
La recherche se termine lorsque le upperBound (notre pointeur) passe au-delà de lowerBound (dernier élément), ce qui implique que nous avons recherché tout le tableau et que l'élément n'est pas présent.Il s'agit des algorithmes de recherche les plus couramment utilisés principalement en raison de son temps de recherche rapide. La complexité temporelle de la recherche binaire est SUR) ce qui est une nette amélioration de la SUR) complexité temporelle de la recherche linéaire.
Ceci nous amène à la fin de cet article «Structures de données et algorithmes en Java». J'ai couvert l'un des sujets les plus fondamentaux et les plus importants de Java.J'espère que vous êtes clair avec tout ce qui a été partagé avec vous dans cet article.
  Assurez-vous de pratiquer autant que possible et inversez votre expérience.   
 Vérifiez    par Edureka, une entreprise d'apprentissage en ligne de confiance avec un réseau de plus de 250 000 apprenants satisfaits répartis dans le monde entier. Nous sommes là pour vous aider à chaque étape de votre voyage, pour devenir une autre question d'entrevue java, nous proposons un programme conçu pour les étudiants et les professionnels qui souhaitent devenir développeur Java. 
 Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de ce 'Structures de données et algorithmes en Java'  article et nous vous répondrons dans les plus brefs délais.