Développer des opérations sur les listes chaînées

Question

Implémentez une classe Cellule qui possède deux arguments : valeur et suivante.

Lors de l'initialisation, valeur est obligatoire mais suivante est facultatif et vaut None si aucune valeur est donnée (voir indice pour savoir comment faire).

Vous rajouterez des getters et setters.

Indice

Pour avoir une fonction (ou une méthode) avec des paramètres facultatifs, utilisez la syntaxe suivante :

1
def maFonction(param1, param2, param3=None):
2
    ...

Ainsi, lors de l'appel de maFonction() :

  • si 2 arguments sont donnés, param3 vaudra None ;

  • si 3 arguments sont donnés, param3 vaudra la valeur du 3ème argument.

Question

Implémentez une classe Liste correspondant à l'implémentation d'une liste doublement chaînée.

Vous devez rédiger l'initialisation de la liste, correspondant à la primitive creerListeVide().

Indice

Voir le cours, tout y est expliqué

Question

Écrire une méthode estVide pour vérifier si une liste vide.

Question

Écrire une méthode ajouterQueue pour la classe Liste qui prend en paramètre une valeur elt et ajoute cet élément en queue de liste.

De même pour la méthode ajouterTete pour la classe Liste qui prend en paramètre une valeur elt et ajoute cet élément en tête de liste.

Indice

Il faut faire une disjonction de cas en fonction de si la liste est vide ou non.

Question

Écrire une méthode retirerQueue pour la classe Liste qui supprime et renvoie l'élément en queue de liste.

De même pour la méthode retirerTete pour la classe Liste qui supprime et renvoie l'élément en tête de liste.

Indice

Attention à vérifier que la liste est non vide et à gérer le cas où la liste devient vide.

Question

Écrire une méthode __len__ qui renvoie la longueur d'une liste.

Proposez une piste d'amélioration pour que ce calcul se fasse en temps constant (c'est-à-dire qu'il n'y ait pas besoin de parcourir tous les éléments de la liste à chaque calcul).

Question

Écrire une méthode __getitem__ qui prend en paramètre un indice i (int) et renvoie la valeur de l'élément à position i.

Que pouvez-vous dire sur la complexité de cette méthode ? Comment l'améliorer sans changer d'implémentation ?

Indice

Le premier élément est à la position 0.

Question

Écrire une méthode inserer qui prend en paramètre un indice i (int) et un élément e et ajoute l'élément dans la liste à l'indice donné.

Question

Écrire une méthode supprimer qui prend en paramètre un indice i (int) et supprime l'élément dans la liste à l'indice donné.

Question

Écrire une méthode contient qui prend en paramètre un élément e et renvoie True si l'élément est dans la liste, False sinon.

Inspirez vous de la liste des méthodes des List Python pour ajouter de nouvelles méthodes.