Fiche de révision : Structures de données linéaires

📋 Plan du Cours

1. Types abstraits et opérations CRUD
2. Listes et opérations indexées
3. Implémentations des listes
4. Piles et files
5. Dictionnaires et accès par clé

📖 1. Types abstraits et opérations CRUD

🔑 Notions clés & Définitions

• Type abstrait de données : Un type abstrait de données décrit des données indépendamment de leur implémentation, avec une notation, des opérations et les propriétés de ces opérations.
• Interface : Ensemble des routines qui permettent d’ajouter, d’effacer et d’accéder aux données.

★ À maîtriser

• Les quatre opérations CRUD sont :
  • Create pour ajouter une donnée
  • Read pour lire une donnée
  • Update pour modifier une donnée
  • Delete pour supprimer une donnée

Compléments

• La recherche d’une donnée est nécessaire aux opérations de lecture, de modification et de suppression.

📖 2. Listes et opérations indexées

🔑 Notions clés & Définitions

• Liste : Structure de données qui regroupe des éléments ordonnés, repérés par un indice, auxquels l’accès est séquentiel.
• Liste récursive : Soit vide, soit composée d’un premier élément appelé tête et du reste, qui est lui-même une liste appelée queue.

★ À maîtriser

• Le type abstrait liste décrit une structure de données, tandis que les listes Python sont des tableaux dynamiques.

• Pour lire, modifier ou supprimer une liste à l’indice i, l’opération est définie si et seulement si $0 \leq i < \operatorname{longueur}(liste)$.

• Pour insérer un élément dans une liste à l’indice i, l’opération est définie si et seulement si $0 \leq i \leq \operatorname{longueur}(liste)$.

Compléments

• Une liste est évolutive : il est possible d’ajouter ou de supprimer n’importe quel élément.

• Les opérations élémentaires d’une liste sont :

  • créer une liste vide
  • tester si elle est vide
  • obtenir sa longueur
  • insérer un élément
  • modifier un élément
  • supprimer un élément
  • lire un élément
  • rechercher un élément

📖 3. Implémentations des listes

🔑 Notions clés & Définitions

• Liste chaînée : Ensemble d’éléments rangés linéairement, pas nécessairement contigus en mémoire, où chaque cellule contient des informations et un ou plusieurs liens vers d’autres éléments.
• Tableau : Suite de variables de même type situées dans un espace contigu en mémoire.

★ À maîtriser

• Avec une implémentation par tableau, l’accès à une valeur se fait en temps constant, tandis que les insertions et suppressions prennent un temps linéaire.

• Dans une liste chaînée, l’accès à une valeur prend un temps linéaire, tandis que l’insertion et la suppression prennent un temps constant.

Compléments

• Dans une liste chaînée, un lien qui ne désigne aucun autre élément porte la valeur spéciale None.

• Une liste chaînée peut être :

  • simplement chaînée
  • doublement chaînée
  • circulaire

💡 Astuce mémo

Tableau contigu pour lire vite, chaînage pour insérer vite.

📖 4. Piles et files

🔑 Notions clés & Définitions

• Pile : Structure de données qui donne accès en priorité aux dernières données ajoutées, selon le principe LIFO, « Last In, First Out ».
• File : Structure de données qui donne accès en priorité aux premières données ajoutées, selon le principe FIFO, « First In, First Out ».

★ À maîtriser

📌 Empiler ajoute un élément au sommet si la pile n’est pas pleine, et dépiler retire et retourne l’élément du sommet si la pile n’est pas vide.

📌 Enfiler ajoute un élément en queue si la file n’est pas pleine, et défiler retire et retourne l’élément en tête si la file n’est pas vide.

Compléments

• Dans une pile, seul l’objet situé au sommet est accessible.

• Une pile peut être dotée d’une taille maximale et les opérations pile_vide et pile_pleine permettent de tester respectivement si elle est vide ou pleine.

• Dans une file, seul l’objet situé au début de la file est accessible.

• Les files d’impression utilisent une structure de données de type file.

💡 Astuce mémo

Pile LIFO : le dernier entre sort d’abord ; file FIFO : le premier entre sort d’abord.

📖 5. Dictionnaires et accès par clé

🔑 Notions clés & Définitions

• Dictionnaire : Structure de données contenant des entrées sous forme de couples clé-valeur, où chaque valeur est accessible par sa clé.

★ À maîtriser

📌 Contrairement aux listes, les dictionnaires ne comportent pas d’ordre et l’accès à une valeur se fait uniquement par sa clé.

• Les tables de hachage et les fonctions de hachage permettent un accès aux valeurs d’un dictionnaire en temps constant.

📌 Dans un dictionnaire, lire une valeur ou supprimer une entrée de clé cle est défini si et seulement si rechercher(dico, cle) renvoie vrai.

Compléments

• Python possède une implémentation native des dictionnaires, ce qui n’est pas le cas de tous les langages de programmation.

• Les opérations élémentaires d’un dictionnaire sont :

  • créer un dictionnaire vide
  • insérer un couple clé-valeur
  • supprimer une entrée par sa clé
  • lire une valeur par sa clé
  • rechercher si une clé existe

📊 Tableaux de synthèse

Performances des implémentations de listes