7 structures de données que tout développeur doit connaitre
Les structures de données sont l'un des piliers de l'informatique. Elles sont l'un des ingrédients essentiel pour tout bon programme, car choisir la mauvaise structure de données pour résoudre un problème aura un effet négatif sur le performance de votre solution.
Qu'est ce qu'une structure de données?
Une structure de données est une méthode d'organisation et de stockage de données dans les ordinateurs. Elles représentent un ensemble de valeurs, des relations entre ces valeurs et des opérations ou fonctions qu'elles peuvent fournir.
Pourquoi les structures de données sont importantes?
Les structures de données sont un élément important de l'informatique car elles aident les professionnels à stocker et à gérer de grands ensembles de données. L’utilisation d’un système efficace peut vous aider à récupérer et manipuler facilement les informations.
Les 7 structures de données
1. Le tableau
Un tableau (Array) est une collection d'éléments à taille fixe qui est stockée à des emplacements mémoire contigus.
Les tableaux sont largement utilisés dans le traitement d'images. En effet, toute image de dimension MxN pixels peux être modélisé comment un tableau de MxN dont chaque élément du tableau représente la couleur de chaque pixel.
2. La liste
Une liste (List) est une collection ordonnée d'éléments à taille variable. Contrairement aux tableaux, les éléments de la liste sont stockées en mémoire de façon éparse, chaque élément ayant la référence de l'élément suivant.
La liste permet d'ajouter ou retirer des éléments.
Les listes sont largement utilisées dans les réseaux sociaux tel que Twitter, où le fil de tweets est une liste des tweets des utilisateurs que vous suivez, en ordre chronologique.
3. La pile
Une pile (Stack) est une collection d'éléments qui sont empilés les uns sur les autres. C'est une structure de type LIFO (Last In, First Out), qui indique que l'on retire toujours d'une pile le dernier élément rajouté.
Les navigateurs web utilisent les piles pour gérer l'historique de navigation. Chaque fois qu'on navigue vers un site, l'adresse du site est empilée dans l'historique de navigation. Lorsqu'on clique sur le bouton Back, le navigateur dépile la dernière adresse de l'historique et vous redirige à l'adresse au dessus de l'historique.
5. La file
Une file (Queue) est une collection d'éléments de type FIFO (First In, First Out), qui indique que l'on retire toujours de la file le 1er élément rajouté.
Les files sont utilisées dans les applications de messageries, pour stocker les messages reçus afin de s'assurer qu'il sont affichés dans le bon ordre.
5. L'arbre
Les arbres (Tree) sont utilisés pour organiser les données de façon hiérarchique. Il existe plusieurs types d'arbres, en fonction de leurs propriétés: N-ary Tree,Balanced Tree, AVL Tree, etc.
Les navigateurs utilisent les arbres pour charger les pages HTML en mémoire.
6. Le graphe
Les graphes (Graph) sont utilisés pour gérer les relations entre les données et trouver les chemins entre elles.
Cette structure est largement utilisée dans les réseaux sociaux pour représenter les connections entre les usagers et leur intérêts.
A partir du graphe ci dessus, qui est une représentation simplifiée des connections d'un réseau social ou Roger est ami aver Thomas et Antoine:
- On peut suggérer à Roger de suivre Emmanuel. On assume que les amis communs à Thomas et Antoine sont aussi les amis de Roger.
- On peux suggérer sur le fil de Roger les publications A, B et C car elles sont aimées par ses amis. On assume que Roger a les mêmes intérêts que ses amis Thomas et Antoine.
- On peux déduire que la publication C est la plus tendance, car c'est la publication la plus aimée.
7. Table de Hachage
Une table de hachage est une structure de données qui permet des accès, insertions et suppression rapides.
Elles utilisent une fonction de hachage pour transformer une clé à la position de l'élément en mémoire; ce qui permet d'offrir un temps constant d'accès aux éléments.
Les tables de hachage sont largement utilisées dans les caches pour d'accéder rapidement aux données fréquemment recherchées. Ceci permet améliorer la performance générale du système car le temps d'accès à la cache est constant, contrairement aux bases de données dont la performance dépend beaucoup de la quantité de données stockée.
Conclusion
Toutes les structures de données ont une variété d’applications et d’objectifs. Avoir une compréhension rudimentaire des structures de données est une première étape cruciale pour devenir un programmeur qualifié.
Si vous avez aimé cet article, abonnez vous à mon blog pour recevoir un article tous les 2 mercredi.
