What is a data structure?

Reading time5 min

En bref

Résumé de l’article

Une structure de données est une manière d’organiser les données afin qu’elles puissent être traitées plus facilement. Elle fournit une implémentation concrète d’un type de données abstrait, qui n’est pas un type de données intégré.

Un type de données abstrait est associé à un ensemble d’opérations qui peuvent être effectuées dessus. On l’appelle type de données abstrait car il ne spécifie pas comment les données sont représentées ni comment les opérations sont implémentées.

Points clés

  • Les types de données abstraits sont des structures de données qui ne sont pas des types de données intégrés.

  • Lors de l’utilisation de types de données abstraits, les opérations sur les données sont définies indépendamment de leur implémentation (l’implémentation est abstraite).

  • De nombreux types de types de données abstraits existent, par exemple, liste chaînée, pile, file, arbre, graphe.

Contenu de l’article

1 — Qu’est-ce qu’une structure de données ?

Les structures de données permettent de stocker et récupérer des données, d’effectuer des opérations sur les données, et de résoudre des problèmes spécifiques. En comprenant les structures de données, vous pouvez :

  • Décider quelle structure de données est la meilleure pour une situation donnée.
  • Écrire des programmes qui s’exécutent plus rapidement ou utilisent moins de mémoire.
  • Comprendre comment aborder et résoudre des problèmes complexes de manière systématique.

Les types de données tels que int, float, etc. sont des types de données intégrés, sur lesquels nous pouvons effectuer des opérations de base telles que addition, soustraction, division, multiplication, etc. Cependant, il peut y avoir des situations où nous devons définir des opérations pour nos types de données définis par l’utilisateur. Ces opérations ne peuvent être définies que lorsque nous en avons besoin. Ainsi, pour simplifier le processus de résolution de problèmes, nous pouvons créer des structures de données avec leurs opérations, et ces structures de données qui ne sont pas intégrées sont appelées “types de données abstraits” (TDA).

2 — Quelques TDA couramment rencontrés

Les types de données abstraits courants incluent :

  • Linked list – Une structure de données dans laquelle les éléments ne sont pas stockés à des emplacements mémoire contigus. Les éléments dans une liste chaînée sont liés à l’aide de “pointeurs”, c’est-à-dire un lien vers l’élément suivant. Ils existent sous différentes formes, par exemple, liste simplement chaînée, liste doublement chaînée, liste circulaire, liste doublement circulaire. Les opérations effectuées sur une liste chaînée incluent : initialisation, insertion d’éléments, suppression d’éléments, recherche d’éléments, mise à jour d’éléments, parcours des éléments et inversion d’une liste chaînée.

  • Stack – Une structure de données qui suit un ordre particulier dans lequel les opérations sont effectuées. L’ordre est Last In First Out (LIFO), c’est-à-dire que l’élément de données stocké en dernier sera accédé en premier. L’entrée et la récupération des données sont possibles uniquement par une extrémité. L’entrée et la récupération des données sont également appelées opérations push et pop dans une pile.

  • Queue – Une structure de données qui suit un ordre particulier dans lequel les opérations sont effectuées. L’ordre est First In First Out (FIFO), c’est-à-dire que l’élément de données stocké en premier sera accédé en premier. Quelques opérations de base effectuées sur une file sont push (également appelée enqueue), pop (également appelée dequeue).

  • Tree – Une structure de données, également connue sous le nom de structure de données non linéaire et hiérarchique, où les éléments sont organisés en une structure arborescente. Dans un arbre, le nœud le plus haut est appelé “nœud racine”. Chaque nœud contient des données, et les données peuvent être de n’importe quel type. Il se compose d’un nœud central, de nœuds structurels et de sous-nœuds qui sont connectés par des arêtes. Différentes structures d’arbres permettent un accès plus rapide et plus facile aux données car c’est une structure de données non linéaire. Les arbres introduisent de nombreux concepts tels que nœud, racine, branche, hauteur d’un arbre, degré d’un arbre, etc. Il existe différents types d’arbres : arbre binaire, arbre binaire de recherche, arbre AVL, arbre B, etc. Certaines opérations courantes incluent : insérer un élément, rechercher un élément, parcourir (parcours en profondeur - Depth-First-Search, parcours en largeur - Breadth-First-Search) ou équilibrer.

  • Graph – Une structure de données (non linéaire) qui consiste en des sommets (ou nœuds) et des arêtes. Elle consiste en un ensemble fini de sommets et un ensemble d’arêtes qui connectent une paire de nœuds. Le graphe est utilisé pour résoudre des problèmes de programmation plus difficiles et complexes. Les graphes introduisent de nombreux concepts tels que chemin, degré, sommets adjacents, composantes connexes, etc. Certaines opérations courantes effectuées sur les graphes incluent : ajouter/supprimer un sommet, ajouter/supprimer une arête, parcourir, détection de cycle, etc.

Dans le reste du cours, nous nous concentrerons sur certaines structures de données courantes, qui sont des types de données intégrés (listes, ensembles, tuples et dictionnaires) et certains types de données abstraits (liste chaînée, pile et file).

Pour aller plus loin

On dirait que cette section est vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà