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 autorisées
3. Implémentations des listes
4. Piles et comportement LIFO
5. Files et comportement FIFO
6. Dictionnaires et accès par clé

📖 1. Types abstraits et opérations CRUD

🔑 Notions clés & Définitions

• Type abstrait de données : Description 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 permettant d’ajouter, d’effacer et d’accéder aux données.

★ À maîtriser

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

Compléments

• La recherche d’une donnée est une routine importante derrière les opérations de lecture, de modification et de suppression.

💡 Astuce mémo

CRUD : Create, Read, Update, Delete

📖 2. Listes et opérations autorisées

🔑 Notions clés & Définitions

• Liste : Suite finie d’éléments ordonnés, repérés par leur indice, dont l’accès est séquentiel et à laquelle on peut ajouter ou supprimer des éléments.
• Définition récursive d’une liste : Liste soit vide, soit constituée d’un premier élément appelé tête et du reste, appelé queue, qui est lui-même une liste.

★ À maîtriser

• Les opérations élémentaires d’une liste sont :
  • créer une liste vide
  • tester si elle est vide
  • connaître sa longueur
  • insérer un élément
  • modifier un élément
  • supprimer un élément
  • lire un élément
  • rechercher un élément

📌 Dans une liste de longueur n, lire, modifier et supprimer à l’indice i sont définies si et seulement si $0 \leq i < n$.

📌 Dans une liste de longueur n, insérer à l’indice i est défini si et seulement si $0 \leq i \leq n$.

Compléments

📌 Les listes Python sont des tableaux dynamiques et ne doivent pas être confondues avec le type abstrait liste.

📖 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, dont 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 l’insertion et la suppression se font en temps linéaire.

• Avec une liste chaînée, l’accès à une valeur se fait en temps linéaire, tandis que l’insertion et la suppression se font en temps constant.

Compléments

• Dans une liste chaînée, les liens ne désignant aucun autre élément sont représentés par la valeur None.

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

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

💡 Astuce mémo

Tableau contigu pour l’accès rapide ; cellules chaînées pour les insertions rapides

📖 4. Piles et comportement LIFO

🔑 Notions clés & Définitions

• Pile : Structure de données où la dernière donnée ajoutée est la première à sortir, et seul l’objet situé au sommet est accessible.

★ À maîtriser

• Le comportement d’une pile est appelé LIFO, pour « Last In, First Out ».

• Les opérations essentielles d’une pile sont empiler un élément au sommet si la pile n’est pas pleine, puis dépiler et retourner la dernière donnée si la pile n’est pas vide.

📌 Empiler est défini si et seulement si la pile n’est pas pleine, et dépiler est défini si et seulement si la pile n’est pas vide.

Compléments

• Une pile peut être limitée par une taille maximale.

💡 Astuce mémo

Une pile d’assiettes : on retire d’abord celle du dessus

📖 5. Files et comportement FIFO

🔑 Notions clés & Définitions

• File : Structure de données où les premières données ajoutées sortent en premier, et seul l’objet situé au début de la file est accessible.

★ À maîtriser

• Le comportement d’une file est appelé FIFO, pour « First In, First Out ».

• Les opérations essentielles d’une file sont enfiler un élément en queue si la file n’est pas pleine, puis défiler et retourner la donnée en tête si la file n’est pas vide.

📌 Enfiler est défini si et seulement si la file n’est pas pleine, et défiler est défini si et seulement si la file n’est pas vide.

Compléments

• Les files d’impression utilisent une structure de file.

💡 Astuce mémo

Une file d’attente à la caisse : le premier arrivé passe en premier

📖 6. Dictionnaires et accès par clé

🔑 Notions clés & Définitions

• Dictionnaire : Structure de données contenant des couples clé-valeur, appelés entrées, où chaque valeur est accessible par sa clé et où les entrées ne sont pas ordonnées.

★ À maîtriser

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

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

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

📌 Lire ou supprimer une entrée d’un dictionnaire est défini si et seulement si la clé existe dans le dictionnaire.

Compléments

• Python possède une implémentation native des dictionnaires, contrairement à de nombreux autres langages de programmation.

💡 Astuce mémo

La liste repère par indice et ordonne ; le dictionnaire repère par clé et n’ordonne pas

📊 Tableaux de synthèse

Performances des implémentations de listes