Please enable JavaScript.

Coggle requires JavaScript to display documents.

Structures de données (TDA (Spécifications (commentaires Doxygène) pour…

- - - - Séquence ordonnée d’éléments d’un certain type (chaque élément possède une position dans la liste + concept de position courante -> i.e endroit ou on peut insérer et supprimer)
    - - Suppression d'un élément à la position courante
      - Insertion d'un élément avant la position courante
      - Accès à l'élément suivant (opérateur ++)
      - Accès à l'élément précédant (si liste doublement chaînée)
    - - :timer_clock: Les 4 opérations se font en temps O(1)
    - - Insertions et suppressions à la position courante sont très rapides
      - Surtout utilisée pour construire d'autres structures comme les files, piles , etc ...
    - - Liste simplement chaînée
        
        Chaque noeud possède un seul pointeur sur le noeud suivant
        
        On peut parcourir la liste seulement dans une direction
      - Liste circulaire
        
        Liste simplement chaînée où le pointeur next du dernier noeud
        pointe sur le premier noeud
        
        La liste n’a ni début ni fin: prendre garde aux boucles infinies!
        
        :warning: Faire les mises à jour du pointeur dernier lors de la suppression du dernier noeud où l’ajout d’un noeud à cette position
      - Liste doublement chaînée
    - - Parties contenues dans un noeud
        
        Pointeur pointant au noeud précédent (prev)
        
        Pointeur pointant au noeud suivant (next)
        
        Élément stocké
      - Classe interne et privée de la classe List -> seul les méthodes de List peuvent manipuler les objets Node
      - Sentinelles
        
        Noeuds de tête et de fin (sentinelle) ne contiennent pas de données de l'utilisateur. Si la liste est vide, les pointeurs prev et next pointent à 0.
        
        Pas besoin de mettre à jour les pointeurs head et tail
        de List pour ces opérations car il suffit de mettre à jour les pointeurs next et prev des noeud pertinents peu importe où se fait l’opération
  - - - Séquence ordonnée d'éléments d'un certain type (chaque élément possède une position dans le vecteur)
    - - Insertion d'un élément avant celui situé à la position k
      - Suppression du k-ième élément
      - Accès au k-ième élément
    - - :timer_clock: Accès se fait en temps O(1)
      - :timer_clock: Insertion et suppression se fait en temps O(n), n est le nombre d'éléments stockés dans le vecteur
    - - Accès très rapide et constant (peut importe la position de l'élément)
  - - - Définition
        
        Sert à permettre la mise en attente d'informations dans le but de les récupérer plus tard
        
        LIFO (last in, first out)
        
        Empiler et dépiler par le même point d’accès
      - Opérations devant être supportées
        
        Ajouter un nouvel élément dans la Pile (empiler, push)
        
        Enlever l'élément se trouvant au sommet de la Pile (dépiler, pop)
      - Spécifications souhaitées
        
        :timer_clock: Les 2 opérations se font en temps O(1)
    - - Opérations devant être supportées
        
        Ajouter un nouvel élément dans la file (enfiler, push)
        
        Enlever l'élément le plus ancien de la file (défiler, pop)
      - Spécifications souhaitées
        
        :timer_clock: Les 2 opérations se font en temps O(1)
      - Définition
        
        FIFO (first in, first out)
        
        Sert à permettre la mise en attente d'informations dans le but de les récupérer plus tard
        
        Enfiler et défiler par des points d'accès opposés
- - - - <list> pour les listes doublement chaînées
      - <forward_list> pour les listes simplement chaînées
    - - <queue> pour les files (FIFO)
      - <deque> pour les files extensibles dans les deux directions
    - - <stack> pour les piles (LIFO)
    - - <vector>