Structures de données 101 : Les tableaux – Une introduction visuelle pour les débutants

Apprenez à connaître les structures de données que vous utilisez tous les jours.

👋 Bienvenue ! Commençons par un contexte vital. Laissez-moi vous demander ceci :
✅ Écoutez-vous de la musique sur votre smartphone ?
✅ Conservez-vous une liste de contacts sur votre téléphone ?
✅ Avez-vous déjà vu un tableau de classement lors d’une compétition ?

Si votre réponse est « oui » à l’une de ces questions, alors il est presque certain que vous avez utilisé des tableaux et que vous ne le saviez même pas ! 😃 Les tableaux sont des structures de données très puissantes qui stockent des listes d’éléments. Ils ont des applications infinies. Ils sont très importants dans le monde de l’informatique.

Dans cet article, vous apprendrez les avantages et les inconvénients des tableaux, leur structure, leurs opérations et leurs cas d’utilisation.

Commençons ! 👍

🔎 Plongée profonde dans la structure de base des tableaux

Pour comprendre leur fonctionnement, il est très utile de visualiser la mémoire de votre ordinateur comme une grille, comme celle ci-dessous. Chaque information est stockée dans l’un de ces petits éléments (carrés) qui composent la grille.

Les tableaux tirent parti de cette structure en « grille » pour stocker des listes d’informations connexes dans des emplacements mémoire adjacents afin de garantir une efficacité extrême pour trouver ces valeurs. 🔳🔳🔳🔳 🔳

Vous pouvez penser aux tableaux comme ceci :

Leurs éléments sont les uns à côté des autres en mémoire. Si vous avez besoin d’accéder à plusieurs d’entre eux, le processus est extrêmement optimisé car votre ordinateur sait déjà où se trouve la valeur.

Awesome, non ? Apprenons comment cela fonctionne dans les coulisses ! 😃

📚 Classification

Les tableaux sont classés comme des structures de données homogènes parce qu’ils stockent des éléments du même type.

Ils peuvent stocker des nombres, des chaînes de caractères, des valeurs booléennes (vrai et faux), des caractères, des objets, et ainsi de suite. Mais une fois que vous avez défini le type de valeurs que votre tableau va stocker, tous ses éléments doivent être de ce même type. Vous ne pouvez pas « mélanger » différents types de données.

👀 Lecture des valeurs – La magie commence!

L’étonnant pouvoir des tableaux provient de leur efficacité à accéder aux valeurs. Ceci est réalisé grâce à sa structure en forme de grille. Voyons cela plus en détail.🔍

Lorsque vous créez un tableau, vous :
– L’assignez à une variable. 👈
– Définissez le type d’éléments qu’il va stocker. 🎈
– Définir sa taille (le nombre maximum d’éléments). 📚

💡 Note : Le nom que vous attribuez à cette variable est très important car vous l’utiliserez plus tard dans votre code pour accéder aux valeurs et pour modifier le tableau.

Mais comment indiquer à l’ordinateur à quelle valeur particulière vous souhaitez accéder ? C’est là que les indices prennent un rôle vital!

1️⃣ Indices

Vous utilisez ce qu’on appelle un « indice » (« indices » au pluriel) pour accéder à une valeur dans un tableau. C’est un nombre qui fait référence à l’emplacement où la valeur est stockée.

Comme vous pouvez le voir dans le diagramme ci-dessous, le premier élément du tableau est référencé en utilisant l’indice 0. Au fur et à mesure que vous vous déplacez vers la droite, l’indice augmente d’une unité pour chaque espace de la mémoire.

💡 Note : Je sais que cela semble étrange au début de commencer à compter à partir de 0 au lieu de 1, mais cela s’appelle la numérotation basée sur le zéro. C’est très courant en informatique.

La syntaxe générale pour accéder à un élément est : <ArrayVariable>

Par exemple:
Si votre tableau est stocké dans la variable myArray et que vous voulez accéder au premier élément (à l’indice 0), vous utiliserez myArray

2️⃣ Mémoire

Maintenant que vous savez comment accéder aux valeurs, voyons comment les tableaux sont stockés dans la mémoire de votre ordinateur. Lorsque vous définissez la taille du tableau, tout cet espace en mémoire est « réservé » à partir de ce moment pour les futures valeurs que vous pourriez vouloir insérer.

💡 Note : Si vous ne remplissez pas le tableau avec des valeurs, cet espace sera gardé réservé et vide jusqu’à ce que vous le fassiez.

Par exemple :
Disons que vous définissez un tableau de taille 5 mais que vous n’insérez qu’une seule valeur. Tout cet espace restant sera vide et « réservé » en mémoire, en attendant de futures affectations.

Ceci est essentiel car les tableaux sont extrêmement efficaces pour accéder aux valeurs car tous les éléments sont stockés dans des espaces contigus en mémoire. Ainsi, l’ordinateur sait exactement où regarder pour trouver l’information que vous avez demandée.

Mais… il y a un inconvénient 😞 car ce n’est pas efficace en termes de mémoire. Vous réservez de la mémoire pour des opérations futures qui pourraient ne pas se produire. C’est pourquoi les tableaux sont recommandés dans les situations où vous savez à l’avance combien d’éléments vous allez stocker.

🔧 Opérations – Dans les coulisses !

Maintenant que vous savez ce que sont les tableaux lorsqu’ils sont utilisés, et comment ils stockent les éléments, nous allons plonger dans leurs opérations comme l’insertion et la suppression.

1️⃣ Insertion – Bienvenue!

Disons que nous avons un tableau de taille 6 et qu’il y a encore un espace vide. Nous voulons insérer un élément « e » au début du tableau (indice 0), mais cette place est déjà prise par l’élément « a ». Que devons-nous faire ?

Pour insérer dans des tableaux, nous déplaçons tous les éléments situés à droite du site d’insertion, d’un indice vers la droite. L’élément « a » sera maintenant à l’indice 1, l’élément « b » sera à l’indice 2 et ainsi de suite…

💡 Note : Vous devrez créer une variable pour garder la trace du dernier indice qui contient des éléments. Dans le schéma ci-dessus, le tableau est rempli jusqu’à l’indice 4 avant l’insertion. De cette façon, vous pouvez déterminer si le tableau est plein et quel indice vous devez utiliser pour insérer un élément à la fin.

Après avoir fait cela, notre élément est inséré avec succès. 👏

⚠️ Attendez une minute ! Que se passe-t-il si le tableau est plein ?

Que pensez-vous qu’il se passera si le tableau est plein et que vous essayez d’insérer un élément ? 😱

Dans ce cas, vous devez créer un nouveau tableau, plus grand, et copier manuellement tous les éléments dans ce nouveau tableau. Cette opération est très coûteuse, en termes de temps. Imaginez ce qui se passerait si vous aviez un tableau contenant des millions d’éléments ! Cela pourrait prendre un temps très long à réaliser. ⏳

💡 Remarque : La seule exception à cette règle, lorsque l’insertion est très rapide, est lorsque vous insérez un élément à la fin du tableau (à l’indice situé à droite du dernier élément) et qu’il reste de la place disponible. Cela se fait en temps constant O(1).

2️⃣ Suppression- Bye, Bye!

Maintenant disons que vous voulez supprimer un élément du tableau.

Pour maintenir l’efficacité de l’accès aléatoire (être capable d’accéder au tableau par un index extrêmement rapide) les éléments doivent être stockés dans des espaces contigus de la mémoire. Vous ne pouvez pas simplement supprimer l’élément et laisser cet espace vide.

Vous devez déplacer les éléments qui viennent après l’élément que vous voulez supprimer d’un indice vers la gauche.

Et finalement, vous avez ce tableau résultant 👇. Comme vous pouvez le voir, « b » a été supprimé avec succès.

💡 Note : La suppression est très efficace lorsque vous supprimez le dernier élément. Puisque vous devez créer une variable pour garder la trace du dernier indice qui contient des éléments (dans le schéma ci-dessus, l’indice 3), vous pouvez directement supprimer cet élément en utilisant l’indice.

3️⃣ Trouver un élément

Vous avez trois options pour trouver un élément dans un tableau :

• Si vous savez où il se trouve, utilisez l’index.
• Si vous ne savez pas où il se trouve et que vos données sont triées, vous pouvez utiliser des algorithmes pour optimiser votre recherche, comme la recherche binaire.
• Si vous ne savez pas où il se trouve et que vos données ne sont pas triées, vous devrez chercher dans chaque élément du tableau et vérifier si l’élément actuel est l’élément que vous recherchez (veuillez voir la séquence de diagrammes ci-dessous).

👋 En résumé…

• Les tableaux sont des structures de données extrêmement puissantes qui stockent des éléments du même type. Le type des éléments et la taille du tableau sont fixes et définis lorsque vous le créez.
• La mémoire est allouée immédiatement après la création du tableau et il est vide jusqu’à ce que vous assigniez les valeurs.
• Leurs éléments sont situés dans des emplacements contigus en mémoire, on peut donc y accéder très efficacement (accès aléatoire, O(1) = temps constant) en utilisant les indices.
• Les indices commencent à 0, et non à 1 comme nous en avons l’habitude.
• Insérer des éléments au début ou au milieu du tableau implique de déplacer les éléments vers la droite. Si le tableau est plein, création d’un nouveau tableau plus grand (ce qui n’est pas très efficace). L’insertion à la fin du tableau est très efficace, temps constant O(1).
• Enlever des éléments au début ou au milieu du tableau implique de déplacer tous les éléments vers la gauche pour éviter de laisser un espace vide en mémoire. Cela garantit que les éléments sont stockés dans des espaces contigus en mémoire. La suppression à la fin du tableau est très efficace car vous ne supprimez que le dernier élément.
• Pour trouver un élément, vous devez vérifier tout le tableau jusqu’à ce que vous le trouviez. Si les données sont triées, vous pouvez utiliser des algorithmes tels que la recherche binaire pour optimiser le processus.

« Apprendre d’hier, vivre pour aujourd’hui, espérer pour demain. L’important est de ne pas cesser de s’interroger. »
– Albert Einstein

👋 Merci!

J’espère vraiment que mon article vous a plu. ❤️
Suivez-moi sur Twitter pour trouver d’autres articles comme celui-ci. 😃