Fiches de révision

Points clés

• •Chaque élément (maillon) contient une valeur et un pointeur vers le suivant
• •Insertion/suppression en O(1) si on a le pointeur
• •Accès par indice en O(n)
• •Pas besoin de redimensionner comme les tableaux

Code / Exemple

class Maillon:
    def __init__(self, val, suiv=None):
        self.valeur = val
        self.suivant = suiv

Points clés

• •Last In First Out : le dernier entré sort en premier
• •Opérations : empiler (push), dépiler (pop), sommet (top)
• •Toutes les opérations en O(1)
• •Utilisé pour : récursivité, parsing, undo/redo

Code / Exemple

pile = []
pile.append(x)  # empiler
x = pile.pop()  # dépiler
top = pile[-1]  # sommet

Points clés

• •First In First Out : le premier entré sort en premier
• •Opérations : enfiler, défiler, tête
• •Utiliser collections.deque pour O(1)
• •Utilisé pour : BFS, files d'attente, buffer

Code / Exemple

from collections import deque
file = deque()
file.append(x)     # enfiler
x = file.popleft() # défiler

Points clés

• •Chaque nœud a au plus 2 enfants (gauche, droite)
• •Hauteur h, nombre de nœuds max : 2^(h+1) - 1
• •ABR : gauche < racine < droite
• •Parcours : préfixe (RGD), infixe (GRD), suffixe (GDR)

Code / Exemple

class Noeud:
    def __init__(self, val, g=None, d=None):
        self.valeur = val
        self.gauche = g
        self.droite = d

Points clés

• •G = (S, A) : sommets et arêtes
• •Orienté vs non orienté, pondéré vs non pondéré
• •Représentation : matrice d'adjacence ou liste d'adjacence
• •Parcours : BFS (largeur), DFS (profondeur)

Code / Exemple

# Liste d'adjacence
graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}