# --- Tableau dynamique (comme list en Python) : accès O(1), insertion en fin amortie O(1) ---
tableau = [1, 2, 3]
tableau.append(4)          # O(1) amorti (réallocation occasionnelle en O(n))
tableau.insert(0, 0)       # O(n) : décale tous les éléments suivants
valeur = tableau[2]        # O(1) : accès direct par index (calcul d'adresse mémoire)
tableau.pop()               # O(1) : retire le dernier élément
tableau.pop(0)               # O(n) : retire le premier, décale tout le reste

# --- Liste chaînée simple : implémentation complète ---
class Noeud:
    __slots__ = ("valeur", "suivant")
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant: "Noeud | None" = None

class ListeChainee:
    def __init__(self):
        self.tete: Noeud | None = None
        self.taille = 0

    def ajouter_en_tete(self, valeur) -> None:
        # O(1) : pas besoin de parcourir la liste
        nouveau = Noeud(valeur)
        nouveau.suivant = self.tete
        self.tete = nouveau
        self.taille += 1

    def ajouter_en_queue(self, valeur) -> None:
        # O(n) sans pointeur de queue : il faut parcourir toute la liste
        nouveau = Noeud(valeur)
        if self.tete is None:
            self.tete = nouveau
        else:
            courant = self.tete
            while courant.suivant is not None:
                courant = courant.suivant
            courant.suivant = nouveau
        self.taille += 1

    def supprimer(self, valeur) -> bool:
        # O(n) : recherche puis suppression par re-chaînage
        if self.tete is None:
            return False
        if self.tete.valeur == valeur:
            self.tete = self.tete.suivant
            self.taille -= 1
            return True
        courant = self.tete
        while courant.suivant is not None:
            if courant.suivant.valeur == valeur:
                courant.suivant = courant.suivant.suivant  # saute le noeud à supprimer
                self.taille -= 1
                return True
            courant = courant.suivant
        return False

    def contient(self, valeur) -> bool:
        courant = self.tete
        while courant is not None:
            if courant.valeur == valeur:
                return True
            courant = courant.suivant
        return False

    def inverser(self) -> None:
        # O(n) en temps, O(1) en espace : ré-chaîne chaque noeud dans l'autre sens
        precedent = None
        courant = self.tete
        while courant is not None:
            suivant = courant.suivant
            courant.suivant = precedent
            precedent = courant
            courant = suivant
        self.tete = precedent

    def vers_liste_python(self) -> list:
        resultat = []
        courant = self.tete
        while courant is not None:
            resultat.append(courant.valeur)
            courant = courant.suivant
        return resultat

    def __len__(self) -> int:
        return self.taille

# --- Détection de cycle : algorithme de Floyd (tortue et lièvre) ---
def contient_cycle(tete: Noeud | None) -> bool:
    # O(n) en temps, O(1) en espace -- classique d'entretien technique
    lent = rapide = tete
    while rapide is not None and rapide.suivant is not None:
        lent = lent.suivant
        rapide = rapide.suivant.suivant
        if lent is rapide:   # les deux pointeurs se rencontrent -> il y a un cycle
            return True
    return False

# --- Liste doublement chaînée : navigation dans les deux sens ---
class NoeudDouble:
    __slots__ = ("valeur", "precedent", "suivant")
    def __init__(self, valeur):
        self.valeur = valeur
        self.precedent: "NoeudDouble | None" = None
        self.suivant: "NoeudDouble | None" = None

class ListeDoublementChainee:
    def __init__(self):
        self.tete: NoeudDouble | None = None
        self.queue: NoeudDouble | None = None

    def ajouter_en_queue(self, valeur) -> None:
        # O(1) grâce au pointeur de queue maintenu à jour
        nouveau = NoeudDouble(valeur)
        if self.queue is None:
            self.tete = self.queue = nouveau
        else:
            nouveau.precedent = self.queue
            self.queue.suivant = nouveau
            self.queue = nouveau