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

Apprenez à connaître les structures de données que vous utilisez chaque jour.

👋 Bienvenue! Commençons par un contexte vital. Permettez-moi de vous poser cette question:

✅ É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 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 découvrirez les avantages et les inconvénients des tableaux, leur structure, leurs opérations et leurs cas d'utilisation.

Commençons! 👍

🔎 Plongez-vous dans la structure de base des tableaux

Pour comprendre leur fonctionnement, il est très utile de visualiser la mémoire de votre ordinateur sous forme de grille, tout 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 associées dans des emplacements mémoire adjacents afin de garantir une efficacité extrême pour trouver ces valeurs. 🔳🔳🔳🔳

Vous pouvez penser à des tableaux comme celui-ci:

Leurs éléments sont côte à côte dans la 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.

Génial, non? Apprenons comment cela fonctionne dans les coulisses! 😃

📚 Classification

Les tableaux sont classés comme des structures de données homogènes carstocker des éléments du même type .

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

👀 Lire les valeurs - La magie commence!

La puissance incroyable des tableaux vient de leur efficacité à accéder aux valeurs . Ceci est réalisé grâce à sa structure en forme de grille. Jetons un coup d'œil à cela plus en détail.

Lorsque vous créez un tableau, vous:

- Affectez-le à une variable. 👈

- Définissez le type d'éléments qu'il stockera. 🎈

- Définissez sa taille (le nombre maximum d'éléments). 📚

💡 Remarque: 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 modifier le tableau.

Mais comment pouvez-vous dire à l'ordinateur à quelle valeur particulière vous souhaitez accéder? C'est là que les indices jouent un rôle essentiel!

1️⃣ Indices

Vous utilisez ce qu'on appelle un «index» («indices» au pluriel) pour accéder à une valeur dans un tableau. Il s'agit d'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 désigné à l'aide de l'index 0. Au fur et à mesure que vous vous déplacez vers la droite, l'index augmente de un pour chaque espace en mémoire.

💡 Remarque: je sais qu'il semble étrange au début de commencer à compter à partir de 0 au lieu de 1, mais cela s'appelle la numérotation à base zéro. C'est très courant en informatique.

La syntaxe générale pour accéder à un élément est:[]

Par exemple:

Si votre tableau est stocké dans la variable myArrayet que vous souhaitez accéder au premier élément (à l'index 0), vous utiliseriezmyArray[0]

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 valeurs futures que vous voudrez peut-être insérer.

💡 Remarque: si vous ne remplissez pas le tableau avec des valeurs, cet espace restera réservé et vide jusqu'à ce que vous le fassiez.

Par exemple:

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

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. De cette façon, l'ordinateur sait exactement où chercher pour trouver les informations que vous avez demandées.

Mais… il y a un inconvénient 😞 parce que ce n'est pas efficace en mémoire . Vous réservez de la mémoire pour des opérations futures qui risquent de 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 reste un espace vide. Nous voulons insérer un élément «e» au début du tableau (index 0), mais cette place est déjà occupée par l'élément «a». Que devrions nous faire?

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

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

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

⚠️ Attendez une minute! Que se passe-t-il si la baie est pleine?

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 avec des millions d'éléments! Cela pourrait prendre beaucoup de temps. ⏳

💡 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'index situé à droite du dernier élément) et qu'il reste de l'espace disponible. Cela se fait en temps constant O (1).

2️⃣ Suppression - Bye, Bye!

Disons maintenant que vous souhaitez supprimer un élément du tableau.

Pour maintenir l'efficacité de l'accès aléatoire (pouvoir accéder au tableau via un index extrêmement rapide) les éléments doivent être stockés dans des espaces contigus de 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 souhaitez supprimer d'un index vers la gauche.

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

💡 Remarque: la suppression est très efficace lorsque vous supprimez le dernier élément. Puisque vous devez créer une variable pour garder une trace du dernier index contenant des éléments (dans le diagramme ci-dessus, index 3), vous pouvez directement supprimer cet élément à l'aide de l'index.

3️⃣ Trouver un élément

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

  • Si vous savez où il se trouve , utilisez l'index.
  • Si vous ne savez pas où elles se trouvent 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 rechercher 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 d'éléments et la taille du tableau sont fixes et définis lors de sa création.
  • La mémoire est allouée immédiatement après la création du tableau et elle est vide jusqu'à ce que vous affectiez les valeurs.
  • Leurs éléments sont situés dans des emplacements contigus en mémoire , de sorte qu'ils peuvent être accédés très efficacement (accès aléatoire, O (1) = temps constant) à l'aide d' indices .
  • Les indices commencent à 0 , pas à 1 comme nous en avons l'habitude.
  • L'insertion d'é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éer 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).
  • Supprimer des éléments du début ou du 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 l'ensemble du 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 aujourd'hui, espérer pour demain. L'important est de ne pas arrêter de remettre en question. »

- Albert Einstein

👋 Merci!

J'espère vraiment que vous avez aimé mon article. ❤️

Suivez-moi sur Twitter pour trouver plus d'articles comme celui-ci. 😃