Nous avons tous entendu parler de l’importance de connaître vos structures de données pour les entretiens avec les développeurs. Si vous êtes relativement nouveau dans le domaine de l’informatique et de la programmation, ce concept peut être écrasant. Chaque structure de données stocke des informations dans une disposition spécifique. Différentes structures sont propices à différentes opérations, donc en fonction de l’objectif final, un programmeur sélectionnera la structure de données la plus adaptée en fonction de son efficacité et de sa facilité.
Vous avez probablement déjà utilisé de nombreuses structures de données en programmation, et de façon plus abstraite au cours de votre vie quotidienne. Pensez à chercher un livre à la bibliothèque par son nombre décimal de Dewey. Vous utilisez une table de hachage. Et si vous listiez les articles d’épicerie que vous devez acheter ? Il existe un tableau. Lorsque vous cliquez sur le bouton « Précédent » de votre navigateur, vous êtes dirigé vers le nœud précédent d’une liste liée. Et la recherche de fichiers sur votre ordinateur ? C’est un arbre.
Dans cet article, je vais décrire quatre structures de données de base – tableau, table de hachage, liste liée et arbre – et montrer des exemples d’algorithmes simples. Cette liste n’est en aucun cas exhaustive et il y a certainement d’autres structures de données à connaître, mais je pense que ces quatre structures sont un excellent point de départ.
Tableau
Le tableau est probablement la première structure de données que vous avez apprise au cours de votre voyage de programmation. Il est facile à visualiser et agréable à utiliser. Le tableau est une liste d’éléments dans un ordre précis. Chaque élément correspond à un index, le premier élément se trouvant à l’index 0. Les éléments suivants ont des index incrémentés de 1.
Ci-dessous, je crée un tableau en déclarant une variable et en la plaçant dans une liste d’éléments entre crochets, et je réunis les éléments du tableau en une chaîne.
Table de hachage (Hash Table)
Une table de hachage est constituée de paires clé/valeur où chaque clé est unique et indique la valeur qui lui est associée. La clé est transformée en un entier par une fonction de hachage et stockée.
La variable Object en JavaScript est un exemple de table de hachage. Comme pour le tableau, je le crée ci-dessous en déclarant une variable et en lui attribuant les paires clé:valeur entourée d’accolades. L’algorithme utilisé consiste à lister les clés dans l’objet.
Liste liée (Linked List)
Une liste liée, comme un tableau, est une série d’éléments. Cependant, au lieu d’être stockés dans un espace mémoire consécutif, les éléments peuvent être stockés n’importe où et chaque élément garde la trace de ses propres données et de l’élément suivant dans la ligne. Les listes liées peuvent être liées individuellement, chaque élément pointant uniquement sur l’élément qui le précède (comme indiqué ci-dessus), ou doublement liées, chaque élément pointant à la fois devant et derrière. Il faut un peu plus de travail pour construire une liste liée, c’est pourquoi je vais d’abord montrer cela.
À noter que Node et LinkedList ne sont pas des mots spéciaux ou réservés, nous pourrions donc tout aussi bien appeler nos classes Blob au lieu de Node et Fiddlesticks au lieu de LinkedList. C’est la structure sous-jacente de la manière dont ces instances de classe sont reliées qui est importante, et non pas le nom que nous leur donnons. Essayez-le dans une réplique pour confirmer.
Vous trouverez ci-dessous la longueur d’une liste de liens.
Arbre
Un arbre est constitué de nœuds reliés par des arêtes. Un nœud aura un parent (sauf le nœud racine) et peut avoir un ou plusieurs enfants. La photo ci-dessus montre un type d’arbre spécifique appelé arbre de recherche binaire. Dans un BTS (Binary Search Tree), chaque nœud a un maximum de deux enfants, et l’enfant de gauche est inférieur à celui de droite. Cela permet une plus grande efficacité dans les algorithmes de recherche. Tout comme pour les listes liées, nous devons travailler un peu pour mettre en place notre arbre.
Rappelez-vous encore une fois que les noms des classes ne sont pas importants ici. Ce qui est important, c’est la façon dont nous relions les données stockées dans les instances de chaque classe. Dans l’algorithme ci-dessous, je trouve l’entier le plus bas de l’arbre.
La liste des structures de données va au-delà de ces quatre, et il vaut la peine de passer du temps avec chacune d’entre elles. Au fur et à mesure que vous vous familiariserez avec d’autres structures de données, vous constaterez les similitudes et les chevauchements entre elles.
