14 - Implémenter une Liste 3/3

⏪

⏬

⏩

1 - Base

2 - Insertion

3 - Suppression

4 - Classe Cellule

5 - Classe Liste chaînée

6 - Effet de bord

7 - FAQ

Aujourd'hui, on va partir de l'idée abstraite d'une Liste Récursive
implémentée sous forme d'une Liste Chaînée Muable
utilisant en interne un modèle objet.

Peut-on alors avoir les performances suivantes des deux côtés ?

accéder, insérer, supprimer en TETE à coût CONSTANT.
accéder, insérer, supprimer en FIN à coût CONSTANT.

Agir de manière efficace en TETE ET FIN serait un gros avantage.

Image tirée du film Alice de Tim Burton

Prérequis : programmation objet et notion de liste abstraite.

Documents de cours : open document ou pdf

Exercices supplémentaires 🏠 : Exercices

MODE COURS (cacher les questions)

1 - Liste chaînée sous forme d'objets : la base

⇩ ⇧ ⤊

(RAPPEL) Implémentation avec un modèle tuple

Voir ?

Principe

L'idée abstraite d'une Liste Récursive peut être
implémentée sous forme d'une Liste Chaînée Immuable
utilisant en interne un modèle tuple (valeur de tête, successeur).

Coûts :

accéder, insérer et supprimer en TETE de liste à coût CONSTANT.
accéder, insérer et supprimer en position i à coût LINEAIRE : 𝞗(i) et 𝓞(n).
accéder, insérer et supprimer en FIN i à coût LINEAIRE : 𝞗(n).
concatener à coût LINEAIRE en 𝞗(n_g) (seul le nombre d'éléments dans la liste de gauche a une influence).

Exemple

ca = (5, ())
cb = (15, cc)
cc = (25, cb)
lst = cc

Liste et Cellule

Avec cette implémentation, on peut ne donner à l'utilisateur que de quoi gérer les Listes et les Eléments, sans qu'il manipule les Cellules directement : la Liste n'est qu'un alias vers la Cellule de tête. On se passe des primitives liées aux Cellules en les remplaçant par la primitive premier().

Les primitives qu'on sélectionne classiquement pour manipuler une telle Liste chaînée :

nouvelle_liste_vide() → Liste VIDE

est_liste_vide(lst:Liste) → bool

inserer_tete(lst:Liste, elt:Element) → Liste NON VIDE

supprimer_tete(lst:Liste NON VIDE) → Liste

premier(lst:Liste NON VIDE) → Elément

(RAPPEL) Implémentation avec un modèle list-Python

Voir ?

L'idée abstraite d'une Liste Itérative peut être
implémentée sous forme d'un tableau
utilisant en interne un modèle type list de Python.

Coûts :

accéder à toutes les cases à coût CONSTANT.
insérer et supprimer en TETE i à coût LINEAIRE : 𝞗(n).
insérer et supprimer en position i à coût LINEAIRE : 𝞗(n-i) et 𝓞(n).
accéder, insérer et supprimer en FIN à coût CONSTANT.
concatener à coût LINEAIRE en 𝞗(n_g+n_d) (tous les éléments interviennent puisqu'on doit les déplacer dans la copie).

Liste et Case

Avec cette implémentation, on peut ne donner à l'utilisateur que de quoi gérer les Listes et les Eléments, sans qu'il manipule les Cases.

Voici les primitives qu'on sélectionne classiquement pour manipuler un tableau (ou Liste contiguë) :

nouvelle_liste_vide() → Liste VIDE
est_liste_vide(lst:Liste) → bool
longueur(lst:Liste) → int
inserer(lst:Liste, elt:Elément, i:int VALIDE) → Liste NON VIDE
supprimer(lst:Liste NON VIDE, i:int VALIDE) → Liste
ieme(lst:Liste NON VIDE, i:int VALIDE) → Element

1.1 - Implémentation des Cellules avec un modèle objet

Voir ?

Principe

Les Cellules sont des instances d'une classe Cellule possédant deux attributs :

class Cellule:
    def __init__(self, valeur:'Element', successeur:'None|Cellule'):
        self.v = valeur
        self.s = successeur

v pour la valeur, et
s pour le successeur qui est une référence menant

soit à None s'il s'agit de la Cellule de FIN.
soit à une instance de Cellule pour toutes les autres cellules

Exemples d'instanciation

1
2

ca = Cellule(5, None)  # Cellule finale ca contenant 5
cb = Cellule(15, ca)   # Cellule cb contenant 15 menant à la cellule ca

Voici deux représentations mentales qu'on peut se faire des deux cellules :

Création des primitives liées aux Cellules

Sur cette implémentation, on distingue réellement Cellule et Liste. Nous allons devoir les primitives propres aux cellules. Deux possibilités :

soit ne pas respecter l'encapsulation et utiliser une manipulation directe des attributs Cellule :

c.v pour émuler contenu()
c.s pour émuler successeur()

soit respecter l'encapsulation et créer des méthodes contenu() et successeur().

class Cellule:
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def contenu(self:'Cellule') -> 'Element':
        """Renvoie le contenu de la Cellule"""
        return self.v
     
    def successeur(self:'Cellule') -> 'Cellule|None':
        """Renvoie le successeur de la cellule cible"""
        return self.s
     
    def est_fin(self:'Cellule') -> bool:
        """Prédicat qui renvoie True si la Cellule n'a pas de successeur"""
        return self.s == None   # ou même return not self.a_successeur()
     
    def a_successeur(self:'Cellule') -> bool:
        """Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule"""
        return not self.s == None    # ou return self.s is not None

En NSI, nous utiliserons plutôt la méthode directe pour obtenir moins de lignes de code. Pour un prototype ou le BAC, c'est ok.

Pour une production réelle, ce serait plutôt une mauvaise pratique car on demande à l'utilisateur de manipuler directement notre modèle.

Priorité des opérateurs (PACBo)

Voir ?

Parenthèses (la plus haute priorité)

Opérateurs Arithmétiques

Exposant, puissance
Multiplication, division
Addition, soustraction

Opérateurs de Comparaison

Opérateur in
Opérateurs is et is not
Opérateurs d'ordre > <...
Opérateur égalité et différence == !=

Opérateurs Boolléens

Opérateur not
Opérateur and
Opérateur or

Conséquence avec == (égalité de contenu) :

not self.s == None équivalent à
not (self.s == None)
puisqu'on commence par l'opérateur d'égalité == plutôt que par l'opérateur booléen not.

Conséquence avec is (égalité d'adresses) :

not self.s is None équivalent à
not (self.s is None)
puisqu'on commence par l'opérateur de comparaison is plutôt que par l'opérateur booléen not.

Remarque : is not

self.s is not None équivalent à
self.s is not None
puisque l'opérateur is not est un opérateur de comparaison unique en réalité. Ce n'est pas is puis not mais bien "is not".

1.2 - Implémentation de la Liste avec un modèle objet également

Voir ?

Principe

class Liste:
    def __init__(self):
        self.tete = None
     
    def est_liste_vide(self:'Liste') -> bool:
        return self.tete == None

Une instante de Liste possède un attribut tete qui fait référence :

soit à None s'il s'agit d'une Liste VIDE.
soit à la Cellule en tête s'il s'agit d'une Liste NON VIDE.

C'est cette différence qui permet à la méthode est_liste_vide() de savoir si un objet correspond à une Liste VIDE ou une Liste NON VIDE.

Exemples d'instanciation

lst1 = Liste()  # Liste vide
ca = Cellule(5, None)
cb = Cellule(15, ca)
cc = Cellule(25, cb)  
lst1.tete = cc  # lst est la liste 25 puis 15 puis 5
lst2 = Liste()  # Liste vide

Différences avec le modèle tuple

La liste est encore une référence vers la Cellule de Tête, mais ce n'est pas un simple alias : la référence est stockée dans l'objet lst1 de classe Liste, différente de l'objet cc de classe Cellule.

1.3 - Exemple d'utilisation

Voir ?

class Cellule:
    def __init__(self, valeur:'Element', successeur:'None|Cellule'):
        self.v = valeur
        self.s = successeur
 
class Liste:
    def __init__(self):
        self.tete = None
     
    def est_liste_vide(self:'Liste') -> bool:
        return self.tete == None
 
ca = Cellule(5, None)
cb = Cellule(15, ca)
cc = Cellule(25, cb)
lst1 = Liste()
lst1.tete = cc

On peut alors facilement accéder aux éléments stockés :


>>> lst1.tete.v
25
 
>>> lst1.tete.s.v
15
 
>>> lst1.tete.s.s.v
5

1.4 - Méthodes acces_tete() et acces()

Voir ?

A - Intérêt ?

Avant de pouvoir agir sur une Cellule en position i, il faut d'abord pouvoir la localiser !

B - Les deux méthodes (version itérative)

class Liste:
     
    # ...
     
    def acces_tete(self:'Liste NON VIDE') -> Cellule:
        """Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""
        return self.tete
     
    def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule:
        """Renvoie l'adresse de la cellule i dans la liste NON VIDE"""
        c = self.acces_tete()  # récupère la cellule de tête
        for _ in range(i):     # Faire i fois
            c = c.s            # passe au successeur
        return c

Puisqu'il faut renvoyer une instance de Cellule, il est nécessaire de pouvoir trouver une Cellule. Il y a donc deux PRECONDITIONS :

La liste doit être NON VIDE de façon à avoir des Cellules internes;
L'indice i fourni doit correspondre à un indice possible dans cette liste.

C - Coûts

Le coût de la méthode acces_tete() est constant puisqu'on n'y fait que des lectures d'adresses et d'attributs.

cst

def acces_tete(self:'Liste NON VIDE') -> Cellule:
    """Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""
    return self.tete

Le coût de la méthode acces() est évidemment linéaire puisqu'on boucle i fois sur une action à coût constant. On a donc 𝞗(i) ou encore 𝓞(n).



cst
i fois
-- cst
cst

def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule:
    """Renvoie l'adresse de la cellule i dans la liste NON VIDE"""
    c = self.acces_tete()  # récupère la cellule de tête
    for _ in range(i):     # Faire i fois
        c = c.s            # passe au successeur
    return c

On en déduit que le coût est en 1 + i*1 + 1 = 𝞗(i) = 𝓞(n)

1.5- Méthode longueur()

Voir ?

A - Intérêt ?

Connaître les indices valides.

B - Coût et principe

On peut le décrire soit en récursif, soit en itératif.

SI la liste est vide, on renvoie 0.

SINON, on localise la tête et on compte.

Dans les deux cas, il faudra parcourir la liste chaînée Cellule par Cellule en partant de la tête. Le coût est donc linéaire (en 𝞗(n)).

C - Version itérative

On crée un compteur qui vaut 0.
Si la liste n'est pas vide :
Tant qu'un successeur existe, on augmente le compteur et on passe au successeur.
On renvoie le compteur.

class Liste:
     
    # ...
     
    def longueur(self:'Liste') -> int:
        """Renvoie la longueur de la liste"""
        nb = 0        
        if not self.est_liste_vide():
            c = self.tete
            nb = 1
            while c.s is != None:
                nb = nb + 1
                c = c.s
        return nb

Remarque : en ligne 4, vous pourriez noter if self.est_liste_vide() == False: mais on préfère utiliser not.

D - Version récursive

Il va falloir commencer par enrichir notre classe Cellule d'une méthode RECURSIVE nb_cellules() pouvant renvoyer le nombre de cellules qui composent la chaîne à partir de cette cellule.

Cas de base : la cellule active est la FIN (son successeur contient None). Elle répond 1 pour indiquer qu'elle sait qu'elle existe et qu'il n'y a personne derrière elle.
Cas récursif : une cellule va répondre 1 + la réponse de son successeur.

class Cellule:
     
    # ...
     
     def nb_cellules(self:'Cellule') -> int:
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if self.s == None:                # si il n'y a pas de successeur
            return 1                      # il y a au moins la Cellule actuelle
        else:
            return 1 + self.s.nb_cellules()  # on demande au successeur...

Notez bien que nb_cellules() étant une méthode de la classe Cellule, et qu'on doit donc utiliser la notation pointée pour en faire l'appel depuis un objet, comme en ligne 6 :

return 1 + self.s.nb_cellules()

On a testé que la cellule avait un vrai successeur, donc self.s est bien une instance de Cellule, et pas None qui aurait déclenché une erreur : None.s n'existe pas.

Pour l'intégrer dans la Liste, on peut donc écrire ceci :

class Liste:
     
    # ...
     
    def longueur(self:'Liste') -> int:
        """Renvoie la longueur de la liste"""
        if self.est_liste_vide():
            return 0
        else:
            return self.tete.nb_cellules()

nb_cellules() étant une méthode de la classe Cellule, il faut que devant le point on trouve une instance de cette classe. D'où le test de la ligne 9 permettant de gérer à part le cas de la liste VIDE.

2 - Liste chaînée sous forme d'objets : l'insertion

⇩ ⇧ ⤊

Pour insérer en position i, il faut connaître :

le prédécesseur (en position i-1) éventuel;
le successeur (en position i) éventuel qui deviendra la cellule en position i+1.

Dans une liste chaînée, on peut obtenir facilement le successeur si on connait le prédécesseur.

CONCLUSION : il suffit de localiser la Cellule en position (i-1) lorsqu'on veut insérer une nouvelle cellule en position i.

2.1 - Insérer une cellule en position de TETE dans notre liste chaînée

Voir ?

A - Principe et coût de cette insertion

Pour insérer en tête, on a besoin de la tête actuelle.

Etape 1 : on crée la nouvelle Cellule cd (coût constant)

Etape 2 : on localise la tête actuelle et on en fait le successeur de la Cellule cd. Le successeur de cd est donc soit une vraie cellule, soit None si la liste était vide (coût constant : on lit ou modifie des attributs)

Etape 3 : on modifie l'attribut tete de la liste pour qu'elle pointe la nouvelle cellule (coût constant)

Voici les instructions correspondantes :

(cst) Etape 1
(cst) Etape 2
(cst) Etape 3

nouvelle = Cellule(valeur_voulue, None)
nouvelle.s = lst.tete
lst.tete = nouvelle

Coût : cette insertion est donc à coût constant.

B - Implémentation dans une méthode

class Liste:
     
    # ...
     
    def inserer_tete(self:'Liste', elt:'Element') -> None:
        """Rajoute une nouvelle cellule contenant elt en tête de liste"""
        nouvelle = Cellule(elt, None)  # Etape 1 : création de la cellule
        nouvelle.s = self.tete         # Etape 2 : on relie la nouvelle cellule à l'"ancienne" tête
        self.tete = nouvelle           # Etape 3 : modification de la liste

2.2 - Insérer une cellule en position i dans notre liste chaînée

Voir ?

A - Principe de l'insertion en position i

Pour insérer une cellule en position i, il faut localiser la cellule i-1.

Par exemple, pour insérer en position 2, il suffit de localiser la cellule cb en position 1 :

SI on reçoit un indice i de 0, on lance simplement un appel à inserer_tete().

SINON, il suffit de quatre opérations :

Etape 1 : Localiser le prédécesseur, la Cellule i-1. On utilisera éventuellement acces() si elle existe.

Exemple avec 50 qu'on insère en position 2 : on devra localiser la cellule d'indice 1.

Etape 2 : Créer la nouvelle Cellule.

Etape 3 : Faire pointer la nouvelle Cellule vers le successeur actuel du prédécesseur. Si on arrête là, cc a deux prédécesseurs.

Etape 4 : Faire pointer le prédécesseur vers la nouvelle Cellule.

Les instructions correspondantes :

Etape 1
Etape 2
Etape 3
Etape 4

pred = acces(lst, i-1)
nouvelle = Cellule(valeur_voulue, None)
nouvelle.s = pred.s
pred.s = nouvelle

Cette opération va donc hériter de la PRECONDITION de acces() (puisqu'elle l'utilise) : l'indice i doit être un indice VALIDE.

B - Coût de l'opération

(lin) Etape 1
(cst) Etape 2
(cst) Etape 3
(cst) Etape 4

pred = acces(lst, i-1)
nouvelle = Cellule(valeur_voulue, None)
nouvelle.s = pred.s
pred.s = nouvelle

Les étapes 2-3-4 sont à coût constant. Par contre, acces() est à coût linéaire, en 𝓞(n) ou 𝞗(i).

Coût : l'insertion en position i est donc à coût linéaire, en 𝓞(n) ou en 𝞗(i).

Un autre exemple avec une liste 25-12-20-10-18-5 plus grande où on veut insérer une cellule contenant 20 en position 5 :

La localisation (à partir de la tête) du 18 en position 4 est une opération linéaire.

Notez que si on connaissait déjà l'adresse de ce prédécesseur, il n'y aurait que des étapes à coût constant.

C - Implémentation dans une méthode

class Liste:
     
    # ...
     
    def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None:
        """Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste"""
        if i == 0:
            self.inserer_tete(elt)
        else:
            pred = self.acces(i-1)         # Etape 1 : recherche de la cellule i-1
            nouvelle = Cellule(elt, None)  # Etape 2 : création de la cellule
            nouvelle.s = pred.s            # Etape 3 : liaison nouvelle i vers ancienne i
            pred.s = nouvelle              # Etape 4 : liaison i-1 vers nouvelle i

D - Insérer une cellule derrière la Fin pour en faire la nouvelle Fin ?

Si on a une liste de n éléments, la Tête est la cellule 0 et la Fin est la cellule n-1.

Insérer une cellule en tant que nouvelle Fin actuelle revient donc à localiser la cellule n-1 (qui est la Fin actuelle) et faire de la nouvelle cellule son successeur.

2.3 - Insérer une cellule en FIN de liste

Voir ?

On veut faire l'équivalent de append() : insérer une nouvelle cellule en fin de liste sans fournir le numéro d'indice nous même.

A - Principe

Il suffit de localiser la cellule de Fin actuelle (c'et à dire la seule Cellule qui n'a pas de successeur).

SI la liste est vide, on lance simplement un appel à inserer_tete(), puisque la cellule qu'on veut placer en fin de liste fera aussi office de tête.

SINON, il suffit de trois opérations :

Etape 1 : localiser la Fin actuelle

On part de la Tête.
On avance TANT QUE la cellule actuelle a bien un successeur.

Etape 2 : on crée la nouvelle Cellule
~~Etape 3 : gestion du successeur.~~ Inutile puisqu'on sait que le successeur est None.
Etape 3 : on relie l'ancienne Fin à la nouvelle

B - Coût

C'est le coût de l'étape 1 qui pose problème : linéaire (en 𝞗(n)) puisqu'on va devoir parcourir toutes les cellules de la Tête jusqu'à la Fin.

C - Implémentation dans une méthode

class Liste:
     
    # ...
     
     def inserer_fin(self:'Liste', elt:'Element') -> None:
        """Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""
        if self.est_liste_vide():
            self.inserer_tete(elt)
        else:
            pred = self.tete               # Etape 1 : recherche de la cellule de Fin
            while pred.s != None:      #   TANT QUE pred n'est pas la fin actuelle
                pred = pred.s              #     on passe à la cellule suivante
            nouvelle = Cellule(elt, None)  # Etape 2 : création de la cellule
            pred.s = nouvelle              # Etape 3 : on relie l'ancienne Fin à la nouvelle

D - Peut-on faire mieux ?

Oui, il faudrait stocker la référence de la Fin dans la Liste. Comme cela, localiser la Fin pourra se faire à coût constant.

Par contre, cela va complexifier les mises à jour.

C'est ce que nous allons faire pendant le TP.

3 - Liste chaînée sous forme d'objets : la suppression

⇩ ⇧ ⤊

Pour supprimer la cellule numéro i, il faut connaître :

le prédécesseur, de numéro i-1, éventuel;
le successeur, de numéro i+1, éventuel qui deviendra la cellule en position i.

On peut dire que le prédécesseur mène alors au successeur de son ancien successeur.

CONCLUSION : il suffit de localiser la cellule en position i-1.

3.1 - Supprimer la cellule en position de TETE dans notre liste chaînée

Voir ?

A - Principe et coût de cette suppression

Il suffit de localiser la cellule de Tête actuelle.

Puisque la méthode n'aura rien à renvoyer, nous allons pouvoir en profiter pour lui faire renvoyer la valeur de la tête qu'elle vient de supprimer.

Etape 1 : on mémorise la valeur actuellement en tête de liste (coût constant). Elle vaut 20 sur l'exemple.

Etape 2 : on modifie l'attribut tete de la liste pour qu'il pointe vers le successeur de la tête actuelle (coût constant)

Etape 3 : on renvoie la valeur mémorisée (coût constant)

(coût constant) Etape 1
(coût constant) Etape 2
(coût constant) Etape 3

ancienne_valeur = lst.tete.v
lst.tete = lst.tete.s
return ancienne_valeur

Coût : cette suppression est donc à coût constant.

PRECONDITION : la liste doit être NON VIDE puisqu'on lit sa valeur et son successeur. Si lst.tete pointait sur None, None.s déclencherait une erreur.

B - Implémentation dans une méthode

class Liste:
     
    def __init__(self):
        self.tete = None
     
# ....
     
    def supprimer_tete(self:'Liste NON VIDE') -> 'Elt':
        """Supprime la cellule de tête et renvoie l'élément qui y était stocké"""
        ancienne_valeur = self.tete.v  # Etape 1 : on mémorise la valeur en tête
        self.tete = self.tete.s        # Etape 2 : la tête devient le successeur de la tête
        return ancienne_valeur         # Etape 3 : on renvoie la valeur stockée

3.2 - Supprimer la cellule en position i dans notre liste chaînée

Voir ?

A - Principe et coût de cette suppression

Pour supprimer la cellule i, il suffit de localiser la Cellule pred en position i-1 et de chercher le successeur du successeur de pred.

SI on reçoit un indice i de 0, on lance simplement un appel à supprimer_tete().

SINON, il suffit de quatre opérations :

Etape 1 : Trouver la Cellule en position i-1, le prédécesseur (coût linéaire)

Exemple avec la cellule en position 2 qu'on voudrait supprimer, il faut trouver la cellule 1.

Etape 2 : on mémorise la valeur actuellement en position i (15 sur l'exemple), en partant de son prédécesseur connu (coût constant)
Etape 3 : on fait pointer le prédécesseur vers le successeur de son successeur. La cellule cc a maintenant deux prédécesseurs mais la cellule cb n'est plus référencée dans la liste : en partant de la tête, on a 20-25-5. C'est donc fini.

Etape 4 : on renvoie la valeur mémorisée (coût constant)

Les instructions correspondantes :

(coût linéaire) Etape 1
(coût constant) Etape 2
(coût constant) Etape 3
(coût constant) Etape 4

pred = lst.acces(i-1)
ancienne_valeur = pred.s.v
pred.s = pred.s.s
return ancienne_valeur

Coût : la suppression en position i est donc à coût linéaire, en 𝓞(n) ou en 𝞗(i).

Cette fonction hérite de la PRECONDITION de acces() puisqu'elle l'utilise : l'indice i doit être un indice VALIDE.

PRECONDITION liée à la première : la liste ne doit pas être vide pour qu'un indice valide existe.

B - Implémentation dans une méthode

class Liste:
     
    # ...
     
    def supprimer(self:'Liste NON VIDE', i:'int VALIDE') -> 'Element':
        """Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké"""
        if i == 0:                  # En réalité, on veut supprimer la Tête
            return self.supprimer_tete()
        else:
            pred = self.acces(i-1)      # Etape 1 : recherche de la cellule i-1
            ancienne_valeur = pred.s.v  # Etape 2 : on mémorise la valeur en position i actuellement
            pred.s = pred.s.s           # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur
            return ancienne_valeur      # Etape 4 : on renvoie la valeur mémorisée

3.3 - Supprimer la cellule en fin de liste chaînée

Voir ?

A - Principe et coût

Il suffit de localiser le prédécesseur de la Fin.

Les étapes :

Etape 1 : Il faut trouver le prédécesseur de la Fin : une Cellule dont le successeur du successeur est None. On part de la tête, le coût sera linéaire.
Etape 2 : On mémorise la valeur de Fin (coût constant)
Etape 3 : On impose que le successeur du prédécesseur soit maintenant None (coût constant).
Etape 4 : On renvoie l'ancienne valeur de la Fin (coût constant).

Le coût de cette opération de suppression est linéaire à cause de l'étape 1.

Ci-dessous, un exemple qui montre que supprimer en fin revient à la même chose que supprimer une Cellule interne. La seule différence vient du fait que le successeur de la Fin est None.

Au final, on obtient donc ceci :

B - Implémentation dans une méthode

class Liste:
     
    # ...
     
    def supprimer_fin(self:'Liste NON VIDE') -> 'Element':
        """Supprime la cellule de Fin d'une liste NON VIDE et renvoie l'élément qui y était stocké"""
         
        if self.tete.s is None:
            return self.supprimer_tete()
        else:
            # Etape 1 : on cherche le prédécesseur de la Fin
            pred = lst.tete    # on part de la tête
            while pred.s.s != None:   # tant que c n'est pas le prédécesseur de la Fin
                pred = pred.s                # on passe à la cellule suivante
             
            ancienne_valeur = pred.s.v  # Etape 2 : on mémorise la valeur en position i actuellement
            pred.s = None               # Etape 3 : on fait pointer le prédécesseur sur None
            return ancienne_valeur      # Etape 4 : on renvoie la valeur mémorisée

D - On peut faire mieux si on connaît la Fin ?

Non, nous avons besoin de trouver le prédécesseur de la Fin. Et connaître la fin ne nous aide en rien à le trouver. Nous allons donc devoir partir de la Tête et remonter une à une les cellules.

E - On ne peut vraiment pas mieux ?

Si, mais cela va rendre le code plus complexe.

Nous parlerons de deux solutions possibles en fin de TP pour voir comment parvenir à gérer à coût constant le suppression en fin de liste chaînée.

4 - TP : Cellule en tant que Classe

⇩ ⇧ ⤊

Voyons comment réaliser ce type de structure de données. Vous allez partir d'une implémentation de liste ne référençant que la Tête et allez devoir réaliser l'implémentation intégrant la référence de la Fin également.

Avant d'implémenter la Liste dans une Classe, il faut commencer par implémenter... la Cellule.

01° Placer en mémoire la classe Cellule qui peut recevoir deux paramètres lors de l'appel du constructeur : un paramètre valeur et un paramètre successeur.

class Cellule:
    """Cellule (valeur, successeur)"""
     
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def contenu(self:'Cellule') -> 'Element':
        """Renvoie le contenu de la Cellule"""
        return ...
     
    def successeur(self:'Cellule') -> 'Cellule|None':
        """Renvoie le successeur de la cellule cible"""
        return ...
     
    def est_fin(self:'Cellule') -> bool:
        """Prédicat qui renvoie True si la Cellule n'a pas de successeur"""
        return ...
     
    def nb_cellules(self:'Cellule') -> int:
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if ... :                # si il n'y a pas de successeur
            return ...          # il y a au moins la fin
        else:
            return 1 + ...      # on demande au successeur

Questions

L'attribut v peut-il référencer None dans cette implémentation si la liste est homogène ?
Que veut dire 'Cellule|None' pour le successeur ?
Que contient l'attribut s d'une cellule de fin dans cette implémentation ?

Rajouter de quoi tester la classe dans le programme principal (en utilisant bien entendu if __name__ == "__main__":) :

Créer une cellule cve contenant "Vendredi" qui n'a pas de successeur.
Créer une cellule cje contenant "Jeudi" qui mène à cve.
Créer une cellule cma contenant "Mardi" qui mène à cje.

Comme vous pouvez le voir, il manque des jours.

Correction ?

...CORRECTION...

Question 1

L'attribut v est initialisé avec le paramètre valeur. En regardant la documentation, on voit que cette valeur doit être du type Element. A moins de vouloir stocker uniquement des valeurs None, ce n'est donc pas possible.

Le commentaire sur la ligne L5 est explicite également sur la question.

Question 2

'Cellule|None' veut dire que le paramètre successeur peut être soit une instance de Cellule, soit la valeur None.

Question 3

Une Cellule de Fin possède un attribut s à None.

Question 4+

1
2
3

cve = Cellule("Vendredi", None)
cje = Cellule("Jeudi", cve)
cma = Cellule("Mardi", cje)

02° Représenter sur feuille la structure linéaire créée par les instructions suivantes

>>> c1 = Cellule(5, None)
>>> c2 = Cellule(15, c1)
>>> c3 = Cellule(25, c2)
>>> c4 = Cellule(35, c3)

Correction ?

...CORRECTION...

03° Mettre les 4 cellules en mémoire et vérifier les contenus en partant de la Cellule de tête qui est donc c4.

Nous allons à chaque fois utiliser l'attribut s qui contient ... l'adresse de la cellule suivante. On peut donc y trouver des attributs s et v également !


>>> c4.v
35
 
>>> c4.s.v
25
 
>>> c4.s.s.v
15
 
>>> c4.s.s.s.v
5

04° Compléter maintenant les méthodes contenu(), successeur() et est_fin().

Correction ?

...CORRECTION...

class Cellule:
    """Cellule (valeur, successeur)"""
     
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def contenu(self:'Cellule') -> 'Element':
        """Renvoie le contenu de la Cellule"""
        return self.v
     
    def successeur(self:'Cellule') -> 'Cellule|None':
        """Renvoie le successeur de la cellule cible"""
        return self.s
     
    def est_fin(self:'Cellule') -> bool:
        """Prédicat qui renvoie True si la Cellule n'a pas de successeur"""
        return self.s is None
     
    def nb_cellules(self:'Cellule') -> int:
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if ... :                # si il n'y a pas de successeur
            return ...          # il y a au moins la fin
        else:
            return 1 + ...      # on demande au successeur

Bien. Nous sommes capables de créer des Cellules et les lier entre elles. Regardons maintenant comment les compter.

Pour faire cela, nous allons créer une fonction récursive nommée nb_cellules() qui aura la charge de donner le nombre de cellules en partant de la cellule fournie.

05° Partir de la tête indiquée sur le schéma et suivre la liste pour être certain de comprendre comment cela se lit.

Principe de la lecture de la liste chaînée

La tête désigne ici la cellule clu qui contient le string "Lundi" et qui mène à la cellule cma,...

Comme vous le voyez, les cellules n'ont pas à être situées dans des zones mémoires contiguës.

06° Travaillons maintenant sur la méthode nb_cellules() qu'on notera d'abord juste nbC().

Voici le prototype :

`1`	`def nbC(self:'Cellule') -> int:`

C'est une méthode récursive. Le principe est le suivant :

Cas de base : la cellule n'a pas de successeur. Elle peut répondre 1 pour signaler qu'elle existe.
Cas récursif : elle répondra 1 + la réponse de l'appel qu'elle formule à son successeur.

Questions théoriques (la fonction n'est pas fournie pour l'instant)

Réaliser l'empilement des fonctions lorsqu'on lance l'appel cve.nbC().

cve.nbC() va renvoyer 1 + csa.nbC()

...

Réaliser le dépilement pour obtenir la réponse finale théorique.

Correction ?

...CORRECTION...

Empilement

cve.nbC() va renvoyer 1 + csa.nbC()

....csa.nbC() va renvoyer 1 + cdi.nbC()

........cdi.nbC() RENVOIE 1

Dépilement

Ici, c'est simple, la réponse du cas de base va juste remonter jusqu'à l'appel initial.

cdi.nbC() RENVOIE 1 à csa.nbC()

csa.nbC() RENVOIE 1+1 donc 2 à ... cve.nbC()

cve.nbC() RENVOIE 1+2 donc 3 à ... l'entité informatique qui a fait appel à elle.

07° Compléter maintenant la méthode nb_cellules() dans le programme.

class Cellule:
    """Cellule (valeur, successeur)"""
     
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def contenu(self:'Cellule') -> 'Element':
        """Renvoie le contenu de la Cellule"""
        return self.v
     
    def successeur(self:'Cellule') -> 'Cellule|None':
        """Renvoie le successeur de la cellule cible"""
        return self.s
     
    def est_fin(self:'Cellule') -> bool:
        """Prédicat qui renvoie True si la Cellule n'a pas de successeur"""
        return self.s is None
     
    def nb_cellules(self:'Cellule') -> int:
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if ... :                # si il n'y a pas de successeur
            return ...          # il y a au moins la fin
        else:
            return 1 + ...      # on demande au successeur
 
 
# Instructions du programme principal
 
if __name__ == '__main__':
 
    cdi = Cellule("Dimanche", None)
    csa = Cellule("Samedi", cdi)
    cve = Cellule("Vendredi", csa)
    cje = Cellule("Jeudi", cve)
    cme = Cellule("Mercredi", cje)
    cma = Cellule("Mardi", cme)
    clu = Cellule("Lundi", cma)
     
    assert clu.nb_cellules() == 7

Correction ?

...CORRECTION...

def nb_cellules(self:'Cellule') -> int:
    """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
    if self.s == None :                 # si il n'y a pas de successeur
        return 1                        # il y a au moins la fin
    else:
        return 1 + self.s.nb_cellules()  # on demande au successeur

08° Donner le coût (et la complexité) de la méthode nb_cellules() en considérant une séquence de n cellules dont on connait la tête. Justifier votre réponse.

Le coût est constant et la complexité en 𝞞(1)
Le coût est constant et la complexité en 𝞗(1)
Le coût est logarithmique et la complexité en 𝞞(lg n)
Le coût est logarithmique et la complexité en 𝞗(lg n)
Le coût est linéaire et la complexité en 𝞞(n)
Le coût est linéaire et la complexité en 𝞗(n)
Le coût est quadratique et la complexité en 𝞞(n²)
Le coût est quadratique et la complexité en 𝞗(n²)
Le coût est exponentielle et la complexité en 𝞞(eⁿ)
Le coût est exponentielle et la complexité en 𝞗(eⁿ)

Correction ?

...CORRECTION...

Le coût est linéaire puisqu'on doit partir de la tête et parcourir les cellules une à une.

On peut écrire 𝞗(n) puisque la complexité est réellement linéaire dans tous les cas. Quelque soit le contenu de la liste, il n'y a pas de cas où on pourrait s'arrêter avant d'avoir atteint la Fin. Seule la taille n de la liste importe.

5 - TP : Liste chaînée en tant que Classe

⇩ ⇧ ⤊

09° Placer le programme en mémoire puis répondre aux questions sur la classe Liste.

Questions

Que contient l'attribut tete de la liste lst après exécution de la ligne 57 ?
Que contient l'attribut tete de la liste lst après exécution de la ligne 58 ?
Expliquer la ligne 59 en mode pas à pas

class Cellule:
    """Cellule (valeur, successeur)"""
     
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def nb_cellules(self:'Cellule') -> int:
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if self.s == None :                 # si il n'y a pas de successeur
            return 1                        # il y a au moins la fin
        else:
            return 1 + self.s.nb_cellules()  # on demande au successeur
 
class Liste:
    """Liste chaînée muable"""
     
    def __init__(self):
        self.tete = None
     
    def est_liste_vide(self:'Liste') -> bool:
        return self.tete == None
     
    def acces_tete(self:'Liste NON VIDE') -> Cellule:
        """Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""
        return self.tete
     
    def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule:
        """Renvoie l'adresse de la cellule i dans la liste NON VIDE"""
        c = self.acces_tete()  # récupère la cellule de tête
        for _ in range(i):    # Faire i fois
            c = c.s           # passe au successeur
        return c
     
    def longueur(self:'Liste') -> int:
        """Renvoie la longueur de la liste"""
        if self.est_liste_vide():
            return 0
        else:
            return self.tete.nb_cellules()
 
 
# Instructions du programme principal
 
if __name__ == '__main__':
 
    cdi = Cellule("Dimanche", None)
    csa = Cellule("Samedi", cdi)
    cve = Cellule("Vendredi", csa)
    cje = Cellule("Jeudi", cve)
    cme = Cellule("Mercredi", cje)
    cma = Cellule("Mardi", cme)
    clu = Cellule("Lundi", cma)
    assert clu.nb_cellules() == 7
     
    lst = Liste()
    lst.tete = clu
    assert lst.acces(2).v == "Mercredi"

Correction ?

...CORRECTION...

10° Remplacer uniquement le programme principal pour celui-ci.

if __name__ == '__main__':
 
    a = Cellule('Marie-Antoinette', None)
    b = Cellule('Louis XVI', a)
    c = Cellule('Louis XV', b)
    ls_1 = Liste()
    ls_1.tete = c

Une fois, la liste du programme en mémoire,

Comment obtenir la tête en utilisant l'objet ls_1 ?
Comment obtenir le contenu de la tête en utilisant l'objet ls_1 ?
Comment obtenir la valeur du successeur de la tête en utilisant l'objet ls_1 ?
Comment obtenir le contenu du successeur du successeur de la tête en utilisant l'objet ls_1 ?

Correction ?

...CORRECTION...

Pour obtenir la tête de la liste (l'indice 0), puis son contenu :

>>> ls_1.tete
<__main__.Cellule object at 0x7f03e9774a20>

>>> ls_1.tete.v
'Louis XV'

Pour obtenir le contenu du successeur de la tête (l'indice 1 en gros)

>>> ls_1.tete.s.v
'Louis XVI'

Pour obtenir le contenu du successeur du successeur de la tête (l'indice 2 en gros)

>>> ls_1.tete.s.s.v
'Marie-Antoinette'

Nous allons maintenant enrichir les fonctions disponibles pour commencer à retrouver nos fonctions d'interface.

Nous allons commencer par fournir au moins l'interface ci-dessous, pour justifier que nous avons bien une Liste.

11° Observer la liste des quelques primitives qu'on donne ci-dessous et expliquer pourquoi nous avons bien une liste muable (on dit aussi mutable).

nouvelle_liste_vide() → Liste VIDE
est_liste_vide(lst:Liste) → bool
longueur(lst:Liste) → int
inserer_tete(lst:Liste, elt:"Element") → None
supprimer_tete(lst:Liste NON VIDE) → "Element"
acces_tete(lst:Liste NON VIDE) → Cellule
contenu(c:Cellule) → "Element"
successeur(c:Cellule) → "Cellule|None"

Correction ?

...CORRECTION...

inserer_tete(lst:Liste, elt:"Element") → None
supprimer_tete(lst:Liste NON VIDE) → "Element"

On voit qu'inserer_tete() ne renvoie rien.

On voit que supprimer_tete() renvoie l'élément supprimé.

Cela indique clairement que les listes sont modifiées en place.

Vous allez trouver ci-dessous une implémentation utilisant un modèle à deux classes Liste et Cellule intégrant déjà quelques méthodes correspondant à ce qu'on désire. Il faudra compléter les autres.

Attention, cette implémentation comporte deux attributs pour la liste : un attribut tete et un attribut fin.

12° Mettre en mémoire le programme suivant qui intègre notre module de liste chaînée muable Tete-Fin.

Compléter ensuite la méthode inserer_tete() SANS GERER l'attribut fin pour le moment. Faire comme si cet attribut n'était pas là.

Puisque votre première réponse n'intégre pas la gestion de la fin, vous allez nécessairement déclencher les assertions. C'est normal.

VOIR LE MODULE ?

"""Module du TP implémentant une liste chaînée TETE-FIN MUABLE sous forme d'un objet composé :
+ d'un objet Liste référençant la Tête et la Fin
+ d'instances de classe Cellules (valeur, successeur)
 
"""
 
class Cellule:
    """Cellule (valeur, successeur)
 
    Les Cellules disposent de deux attributs :
    + un attribut v    : la valeur contenue dans cette cellule
    + un attribut s    : le successeur de la cellule, None ou Cellule
 
    Méthodes
    --------
       contenu(self:'Cellule') -> 'Element'               # coût constant
       successeur(self:'Cellule') -> 'Cellule|None'       # coût constant
       a_successeur(self:'Cellule') -> bool               # coût constant
       est_fin(self:'Cellule') -> bool                    # coût constant
       nb_cellules(self:'Cellule') -> int                 # Coût linéaire 𝞗(n)
 
   """
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
 
    # Méthodes ayant un lien avec une primitive de liste chaînée
 
    def contenu(self:'Cellule') -> 'Element':
        """Renvoie le contenu de la Cellule"""
        return self.v
 
    def successeur(self:'Cellule') -> 'Cellule|None':  # coût constant
        """Renvoie le successeur de la cellule cible"""
        return self.s
 
    # Autres méthodes
 
    def a_successeur(self:'Cellule') -> bool:  # coût constant
        """Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule"""
        return self.s != None  # ou return self.s is not None
 
    def est_fin(self:'Cellule') -> bool:  # coût constant
        """Prédicat qui renvoie True si la Cellule n'a pas de successeur"""
        return self.s == None   # ou même return not self.a_successeur()
 
    def nb_cellules(self:'Cellule') -> int:  # Coût linéaire 𝞗(n)
        """Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""
        if self.s == None:                # si il n'y a pas de successeur
            return 1                      # il y a au moins la fin
        else:
            return 1 + self.s.nb_cellules()  # on demande au successeur...
 
 
class Liste:
    """Liste chaînée muable
 
    Les objets disposent de deux attributs :
    + un attribut tete : None si liste vide ou la référence de la Cellule de Tête
    + un attribut fin  : None si liste vide ou la référence de la Cellule de Fin
 
    Méthodes primitives
    -------------------
    est_liste_vide(self:'Liste') -> bool                           # coût constant
    inserer_tete(self:'Liste', elt:'Element') -> None              # coût constant
    supprimer_tete(self:'Liste NON VIDE') -> 'Elt'                 # coût constant
    acces_tete(self:'Liste NON VIDE') -> Cellule                   # coût constant
    premier(self:'Liste NON VIDE') -> Element                      # coût constant
 
    Méthodes primitives (extension)
    -------------------------------
    acces_fin(self:'Liste NON VIDE') -> Cellule                    # coût constant
    inserer_fin(self:'Liste', elt:'Element') -> None               # Coût ???
    supprimer_fin(self:'Liste NON VIDE') -> 'Element'              # Coût ???
 
    Autres méthodes (on peut les construire avec les primitives)
    ---------------
    acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule       # Coût linéaire 𝞗(i) O(n)
    inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None  # Coût linéaire 𝞗(i) O(n)
    supprimer(self:'Liste', i:'int VALIDE') -> 'Element'          # Coût linéaire 𝞗(i) O(n)
    longueur(self:'Liste') -> int                                 # Coût linéaire 𝞗(n)
    afficher(self:'Liste') -> None
    """
 
    def __init__(self):
        self.tete = None  # Seule une liste vide peut avoir cette valeur d'attribut
        self.fin = None   # Seule une liste vide peut avoir cettte valeur d'attribut
 
    # Méthodes-primitives de liste chaînée basique
 
    def est_liste_vide(self:'Liste') -> bool:  # coût constant
        return self.tete == None
 
    def inserer_tete(self:'Liste', elt:'Element') -> None:  # coût constant
        """Rajoute une nouvelle cellule contenant elt en tête de liste"""
        ...  # Etape 1 : création de la cellule
        ...  # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête
        ...  # Etape 3 : modification de la liste
 
    def supprimer_tete(self:'Liste NON VIDE') -> 'Elt':  # coût constant
        """Supprime la cellule de tête et renvoie l'élément qui y était stocké"""
        ...  # Etape 1 : on mémorise la valeur en tête
        ...  # Etape 2 : la tête devient le successeur de la tête
        ...  # Etape 3 : on renvoie la valeur stockée
 
    def acces_tete(self:'Liste NON VIDE') -> Cellule:  # coût constant
        """Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""
        return self.tete
 
    def premier(self:'Liste NON VIDE') -> 'Element':  # coût constant
        """Renvoie la valeur de la cellule de Tête dans la liste NON VIDE"""
        return self.tete.v
 
    # Méthodes-primitives de l'extentsion liste chaînée Tête et Fin
 
    def acces_fin(self:'Liste NON VIDE') -> Cellule:  # coût constant
        """Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE"""
        pass
 
    def inserer_fin(self:'Liste', elt:'Element') -> None:  # Coût ???
        """Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""
        pass
 
    def supprimer_fin(self:'Liste NON VIDE') -> 'Element':  # Coût ???
        """Supprime la cellule de fin d'une liste NON VIDE et renvoie l'élément qui y était stocké"""
        pass
 
    # Autres méthodes
 
    def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule:  # Coût linéaire 𝞗(i) O(n)
        """Renvoie l'adresse de la cellule i dans la liste NON VIDE"""
        c = self.acces_tete()  # récupère la cellule de tête
        for _ in range(i):    # Faire i fois
            c = c.s           # passe au successeur
        return c
 
    def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None:  # Coût linéaire 𝞗(i) O(n)
        """Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste"""
        if i == 0:
            self.inserer_tete(elt)
        else:
            pred = self.acces(i-1)         # Etape 1 : recherche de la cellule i-1
            nouvelle = Cellule(elt, None)  # Etape 2 : création de la cellule
            nouvelle.s = pred.s            # Etape 3 : le successeur de la nouvelle est le successeur du prédécesseur
            pred.s = nouvelle              # Etape 4 : le successeur du prédécesseur est la nouvelle cellule
 
    def supprimer(self:'Liste NON VIDE', i:'int VALIDE') -> 'Element':  # Coût linéaire 𝞗(i) O(n)
        """Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké"""
        if i == 0:                  # En réalité, on veut supprimer la Tête
            return self.supprimer_tete()
        else:
            pred = self.acces(i-1)      # Etape 1 : recherche de la cellule i-1
            ancienne_valeur = pred.s.v  # Etape 2 : on mémorise la valeur en position i actuellement
            pred.s = pred.s.s           # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur
            return ancienne_valeur      # Etape 4 : on renvoie la valeur mémorisée
 
    def longueur(self:'Liste') -> int:  # Coût linéaire 𝞗(n) 
        """Renvoie la longueur de la liste"""
        if self.est_liste_vide():
            return 0
        else:
            return self.tete.nb_cellules()
 
    def afficher(self:'Liste') -> None:  # Coût linéaire
        actuellement = self.acces_tete()
        while actuellement != None:
            print(f"{actuellement.v} -> ", end='')
            actuellement = actuellement.s
        print('x')
 
# Programme
 
if __name__ == '__main__':
 
    def tester_inserer_tete():
        print("Tests de inserer_tete())...", end="")
        lst = Liste()
        lst.inserer_tete(5)
        assert lst.tete == lst.fin
        lst.inserer_tete(10)
        assert lst.tete != lst.fin
        assert lst.tete.v == 10
        assert lst.fin.v == 5
        lst.inserer_tete(20)
        assert lst.tete != lst.fin
        assert lst.tete.v == 20
        assert lst.fin.v == 5
        print("ok")
 
    def tester_supprimer_tete():
        print("Tests de supprimer_tete())...", end="")
        lst = Liste()
        lst.inserer_tete(5)
        lst.inserer_tete(10)
        lst.inserer_tete(20)
        lst.supprimer_tete()
        assert lst.tete != lst.fin
        assert lst.tete.v == 10
        assert lst.fin.v == 5
        lst.supprimer_tete()
        assert lst.tete == lst.fin
        assert lst.fin.v == 5
        lst.supprimer_tete()
        assert lst.tete == lst.fin
        assert lst.fin == None
        print("ok")
 
    def tester_inserer_fin():
        print("Tests de inserer_fin())...", end="")
        lst = Liste()
        lst.inserer_fin(5)
        assert lst.tete == lst.fin
        lst.inserer_fin(10)
        assert lst.tete != lst.fin
        assert lst.tete.v == 5
        assert lst.fin.v == 10
        lst.inserer_fin(20)
        assert lst.tete != lst.fin
        assert lst.tete.v == 5
        assert lst.fin.v == 20
        lst.inserer_tete(200)
        assert lst.tete != lst.fin
        assert lst.tete.v == 200
        assert lst.fin.v == 20
        print("ok")
 
    def tester_supprimer_fin():
        print("Tests de supprimer_fin())...", end="")
        lst = Liste()
        lst.inserer_tete(5)
        lst.inserer_tete(10)
        lst.inserer_tete(20)
        lst.inserer_tete(200)
        lst.supprimer_fin()
        assert lst.tete != lst.fin
        assert lst.tete.v == 200
        assert lst.fin.v == 10
        lst.supprimer_tete()
        assert lst.tete != lst.fin
        assert lst.tete.v == 20
        assert lst.fin.v == 10
        lst.supprimer_fin()
        assert lst.tete == lst.fin
        assert lst.fin.v == 20
        lst.supprimer_fin()
        assert lst.tete == lst.fin
        assert lst.fin == None
        print("ok")
 
    #tester_inserer_tete()
    #tester_supprimer_tete()
    #tester_inserer_fin()
    #tester_supprimer_fin()

Correction ?

...CORRECTION...

    def inserer_tete(self:'Liste', elt:'Element') -> None:  # coût constant
        """Rajoute une nouvelle cellule contenant elt en tête de liste"""
        nouvelle = Cellule(elt, None)  # Etape 1 : création de la cellule
        nouvelle.s = self.tete         # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête
        self.tete = nouvelle           # Etape 3 : modification de la liste

13° Répondre aux questions suivantes :

Une liste VIDE pointe-t-elle au même endroit sa Tête et sa Fin ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste vide.
Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de un élément.
Une liste de deux éléments pointe-t-elle au même endroit sa Tête et sa Fin ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de deux éléments ou plus.

Correction ?

...CORRECTION...

Une liste vide pointe-t-elle au même endroit sa Tête et sa Fin ?

Oui, les deux attributs pointent vers None.

En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste vide.

Oui, fin devra pointer vers la nouvelle cellule.

Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?

Oui, les deux attributs pointent vers la seule cellule présente.

En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de un élément.

Non, fin devra toujours pointer vers l'ancienne cellule qui jouait le rôle de Tête avant. Inutile de la mettre à jour, elle a été poussée de sa place de Tête mais joue toujours le rôle de Fin. C'est la Tête qui devra être modifiée.

Une liste de deux éléments pointe-t-elle au même endroit sa Tête et sa Fin ?

Non, chaque attribut pointe vers une cellule différente.

En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de deux éléments ou plus.

Non plus, la fin reste la fin.

14° Compléter alors maintenant la méthode inserer_tete() pour qu'elle gère correctement la mise à jour de l'attribut fin lorsqu'il le faut.

Attention : on veut une fonction à coût constant.

Vous avez des fonctions de test à décommenter pour tester votre réalisation. Si vous ne voyez pas où est votre erreur, vous pouvez modifier les fonctions de tests en rajoutant lst.afficher() avant et après avoir modifié la liste en lui rajoutant une tête. Vous pourrez un peu mieux voir ce qui se passe.

Correction ?

...CORRECTION...

Aucune boucle et que des opérations à coût constant. La méthode est donc à coût constant.

Sans attribut Fin :

    def inserer_tete(self:'Liste', elt:'Element') -> None:  # coût constant
        """Rajoute une nouvelle cellule contenant elt en tête de liste"""
        c = Cellule(elt, None)  # Etape 1 : création de la cellule
        c.s = self.tete         # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête
        self.tete = c           # Etape 3 : modification de la liste

Avec l'attribut Fin :

    def inserer_tete(self:'Liste', elt:'Element') -> None:  # coût constant
        """Rajoute une nouvelle cellule contenant elt en tête de liste"""
        c = Cellule(elt, None)    # Etape 1 : création de la cellule
        if self.est_liste_vide(): # Etape supplémentaire si la liste est vide initialement
            self.fin = c
        c.s = self.tete           # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête
        self.tete = c             # Etape 3 : modification de la liste

15° Compléter la méthode supprimer_tete().

Commencer par gérer uniquement l'attribut tete et la modification de la liste. C'est clairement au programme.

Ensuite, il faudra vous demander dans quel(s) cas la mise à jour de fin va être nécessaire :

lors du passage de 3 cellules à 2 cellules ?
lors du assage de 2 cellules à 1 cellule ?
lors du passage de 1 cellule à une liste vide ?

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

Attention : on veut une fonction à coût constant.

Voir quand mettre à jour ?

...CORRECTION...

Nous aurons besoin de mettre à jour l'attribut fin lorsque la liste possédait UN UNIQUE élément et qu'on vient de le supprimer : supprimer la tête revient à supprimer la fin. L'attribut fin doit alors pointer vers None.

voir la méthode ?

...CORRECTION...

    def supprimer_tete(self:'Liste NON VIDE') -> 'Elt':  # coût constant
        """Supprime la tête et renvoie son contenu"""
        memoire = self.tete.v      # Etape 1 : on mémorise l'ancienne valeur
        self.tete = self.tete.s    # Etape 2 : la tête devient le successeur de l'ancienne tête
        if self.est_liste_vide():  # si la liste est maintenant VIDE
            self.fin = None
        return memoire

16° Compléter la méthode acces_fin() pour la forme (facile) puis la méthode inserer_fin() (moyen). Donner également les coûts de ces méthodes.

Quelques conseils et indications

Si la liste est vide, on peut faire appel à inserer_tete() puisqu'insérer une fin dans une liste vide revient à insérer une tête.

Si la liste n'est pas vide, c'est à vous d'agir : il faudra que la nouvelle cellule soit le successeur de la fin précédente. Il faut donc mettre la main sur la fin précédente pour lui dire qu'elle a un successeur maintenant.

Attention, on veut une fonction à coût constant cette fois. Il faudra donc trouver la fin avec un coût constant... Comment faire ?

Une fois la gestion de la fin bien réaliser, il faudra vous demander dans quel(s) cas la mise à jour de tete va être nécessaire :

Passage de liste vide à une liste de 1 cellule ?
Passage de 1 cellule à 2 cellules ?
passage de 2 cellules à 3 cellules ?

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

Voir quand mettre à jour ?

...CORRECTION...

Puisqu'on rajoute une fin, l'attribut fin devra toujours être modifié.

Si la liste est vide, on fait appel à inserer_tete(), et c'est elle qui va mettre les attributs.

Si la liste est contient déjà une Cellule, inutile de modifier l'attribut tete de la Liste, il pointe au bon endroit. Par contre, la cellule de tête doit être modifiée pour indiquer qu'elle a un successeur maintenant.

Si la liste possède déjà 2 cellules ou plus, inutile de se demander s'il faut modifier la Tête, les deux attributs pointaient déjà vers deux cellules différentes.

En conclusion, nous n'aurons jamais à modifier la tête : dans le seul cas où il aurait fallu le faire, on active directement une autre méthode.

voir la méthode ?

...CORRECTION...

Aucune boucle et que des opérations à coût constant. La méthode est donc à coût constant.

    def acces_fin(self:'Liste NON VIDE') -> Cellule:  # coût constant
        """Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE"""
        return self.fin
 
    def inserer_fin(self:'Liste', elt:'Element') -> None:  # Coût ???
        """Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""
        if self.est_liste_vide():   # Si la liste est vide, on fait appel
            self.inserer_tete(elt)
        else:
            nouvelle = Cellule(elt, None)  # Etape 1 : on crée la nouvelle Cellule
            self.fin.s = nouvelle          # Etape 2 : on relie l'ancienne Fin à la nouvelle
            self.fin = nouvelle            # Etape 3 : mise à jour de la liste

17° Passons à la suppression de la fin.

Quelle cellule faut-il localiser pour supprimer la Fin ?
En déduire le coût de cette opération de suppression dans cette implémentation.
Dans quel cas va-t-on juste faire appel à supprimer_tete() en interne ?
Compléter la méthode supprimer_fin() (difficle).
Donner également le coût de la méthode en le justifiant à l'aide du code.

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

Qui localiser ?

...CORRECTION...

Il faut localiser le prédécesseur de la Fin.

Or, on ne l'a pas en mémoire : il va falloir chercher. On peut en déduire immédiatement que le coût de l'opération va être linéaire.

Si la liste ne contient qu'une seule cellule, on pourra faire appel à supprimer_tete() puisque Tête et Fin pointe vers la même cellule.

voir la méthode ?

...CORRECTION...

    def supprimer_fin(self:'Liste NON VIDE') -> 'Element':  # Coût Linéaire 𝞗(n)
        """Supprime la cellule de fin d'une liste NON VIDE et renvoie l'élément qui y était stocké"""
         
        if self.tete == self.fin:       # si la liste ne possède qu'une seule cellule
            return self.supprimer_tete() # on demande à l'autre fonction de faire le travail
        else :
            # Etape 1 : on cherche le prédécesseur de la Fin
            c = self.tete             # on part de la tête
            while c.s.s != None:  # tant que c n'est pas le prédécesseur de la Fin
                c = c.s               # on passe à la cellule suivante
             
            ancienne_valeur = c.s.v   # Etape 2 : on mémorise la valeur de Fin actuelle
            c.s = None                # Etape 3 : on fait pointer le prédécesseur sur None
            self.fin = c              # Etape 4 : on met la liste à jour
            return ancienne_valeur       # Etape 5 : on renvoie la valeur mémorisée

Si on veut plus d'efficacité, il faut donc encore complexifier la liste.

Nous avons une liste dite simplement chaînée (une liste où on peut trouver le successeur de chaque cellule) en stockant simplement l'adresse de la tête.

flowchart LR subgraph Liste A(tete) end subgraph Cellules B(1) --> C(5) --> D(7) --> F(10) end A -..-> B

L'insertion et suppression en fin était linéaire...

Nous avons alors conçu une liste simplement chaînée stockant l'adresse de la tête ET l'adresse de la fin.

flowchart LR subgraph Liste direction RL A(tete) Z(fin) end subgraph Cellules direction RL B(1) --> C(5) --> D(7) --> F(10) end A -...-> B Z -...-> F

L'insertion en fin est alors constant mais la suppression de la fin est toujours linéaire car il faut connaître le prédécesseur de la fin...

Nous pourrions alors créer une liste simplement chaînée en stockant l'adresse de la tête, de la fin ET du prédécesseur de la Fin.

flowchart LR subgraph Liste A(tete) Y(predecesseur fin) Z(fin) end subgraph Cellules B(1) --> C(5) --> D(7) --> F(10) end A -..-> B Y -..-> D Z -..-> F

L'insertion en fin est alors également à coût constant une seule fois... Pourquoi ? Car il faut alors remplir l'attribut pred avec le prédécesseur de la nouvelle fin, et on ne le connaît pas... Bref, vous pouvez voir que ce n'est pas si simple que cela...

Pour contrer cela, on peut créer une liste doublement chaînée : chaque Cellule permet de localiser son successeur et son prédécesseur.

flowchart LR subgraph Liste direction RL A(tete) Z(fin) end subgraph Cellules direction LR B(1) --> C(5) --> D(7) --> F(10) F --> D D --> C C --> B end A -..-> B Z -..-> F

Il existe même des listes chaînes cycliques.

flowchart LR subgraph Cellules direction LR B(1) --> C(5) --> D(7) --> F(10) --> B end

Bien entendu, tout ceci ne peut pas rentrer dans une séance de 2-3h. Vous n'avez donc fait que les deux premières implémentations. Les deux autres ne sont pas réellement compliquées, il faut juste penser à gérer tous les cas particuliers lors des mises à jour.

Petit bilan des différentes listes vues jusqu'à présent.

	Chaînée Tuple (Immuable)	Tableau dynamique (muable)	Chaînée Objet:Tête (muable)	Chaînée Objet:Tête+Fin (muable)	Doub.Chaînée Objet:Tête+Fin (muable)
Accès TETE	CST	CST	CST	CST	CST
... insérer en TETE	CST	LINEAIRE 𝞗(n)	CST	CST	CST
... supprimer la TETE	CST	LINEAIRE 𝞗(n)	CST	CST	CST
	Chaînée Tuple (Immuable)	Tableau dynamique (muable)	Chaînée Objet:Tête (muable)	Chaînée Objet:Tête+Fin (muable)	Doub.Chaînée Objet:Tête+Fin (muable)
Accès à la position i	LINEAIRE 𝞗(i) 𝞞(n)	CST	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(min(i, n-i)) 𝞞(n)
... insérer en position i	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(n-i) 𝞞(n)	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(min(i, n-i)) 𝞞(n)
... supprimer la position i	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(n-i) 𝞞(n)	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(i) 𝞞(n)	LINEAIRE 𝞗(min(i, n-i)) 𝞞(n)
	Chaînée Tuple (Immuable)	Tableau dynamique (muable)	Chaînée Objet:Tête (muable)	Chaînée Objet:Tête+Fin (muable)	Doub.Chaînée Objet:Tête+Fin (muable)
Accès FIN	LINEAIRE 𝞗(n)	CST	LINEAIRE 𝞗(n)	CST	CST
... insérer en FIN	LINEAIRE 𝞗(n)	CST amorti	LINEAIRE 𝞗(n)	CST	CST
... supprimer la FIN	LINEAIRE 𝞗(n)	CST	LINEAIRE 𝞗(n)	LINEAIRE 𝞗(n)	CST

Voici les deux modules totalement corrigés :

6 - Effet de bord : concaténation et sécurité

⇩ ⇧ ⤊

En réalité, la plus grande force des listes chaînées ne vient pas juste de l'insertion d'une donnée individuelle mais de l'insertion d'une liste à la suite d'une autre liste. On parlera de concaténation de listes, comme avec les strings.

Lorsqu'on parle de concaténation, la plupart des langages offrent surtout une concaténation par création d'une nouvelle liste, pas de la modification d'une liste déjà existante :

concatener(Liste, Liste) -> Liste

Liste + Liste -> Liste

RAPPEL : concaténation de tableaux statiques

Imaginons qu'on dispose des deux listes. L'une de 20 000 éléments et l'autre de 20 000 éléments également. Si on désire concaténer les deux listes, c'est long avec des tableaux :

Etape 1 : création d'un nouveau tableau

D'abord, il faut réserver une nouvelle place mémoire de 40 000 places :

Etape 2 : recopie des éléments de gauche

Il faut déplacer un par un les 20 000 éléments du premier tableau.

Etape 3 : recopie des éléments de droite

Puis on déplace les 20 000 éléments du deuxième tableau.

Concaténation de listes chaînées

Sur le papier, la concaténation de listes chaînées dont on connait les références de la cellule de Tête et de la cellule de Fin a l'air bien bien simple à mettre en oeuvre :

18° Mettre cette méthode concatener_problematique() en mémoire. Voici son prototype :

concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste'

Questions

Expliquer ce qu'elle réalise ligne par ligne.
Quel est le coût de cette opération ?
A-t-on vraiment réalisé une copie indépendante ? Voyez-vous d'où vient le problème de cette façon d'agir ?

    def concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste':
        """Renvoie une liste qui est la concaténation des listes self et liste_droite"""
         
        nouvelle = Liste()                                         # ?
        if not self.est_liste_vide() and not droite.est_liste_vide():  # ?
            nouvelle.tete = self.tete                              # ?
            self.fin.s = droite.tete                               # ?
            nouvelle.fin = droite.fin                              # ?
        elif self.est_liste_vide() and not droite.est_liste_vide():    # ?
            nouvelle.tete = droite.tete                            # ?
            nouvelle.fin = droite.fin                              # ?
        elif droite.est_liste_vide() and not self.est_liste_vide():    # ?
            nouvelle.tete = self.tete                            # ?
            nouvelle.fin = self.fin                              # ?
        return nouvelle                                            # ?

Correction ?

...CORRECTION...

    def concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste':
        """Renvoie une liste qui est la concaténation des listes self et liste_droite"""
         
        nouvelle = Liste()                                         # on crée une instance de Liste
        if not self.est_liste_vide() and not droite.est_liste_vide():  # si aucune des deux listes n'est vide 
            nouvelle.tete = self.tete                              # nouvelle a la même Tête que gauche
            self.fin.s = droite.tete                               # on fait pointer la fin de gauche sur la tête de droite
            nouvelle.fin = droite.fin                              # nouvelle a la même Fin que droite
        elif self.est_liste_vide() and not droite.est_liste_vide():    # si seule la liste de gauche est vide
            nouvelle.tete = droite.tete                            # nouvelle a la même Tête que droite
            nouvelle.fin = droite.fin                              # nouvelle a la même Fin que droite
        elif droite.est_liste_vide() and not self.est_liste_vide():    # si seule la liste de droite est vide
            nouvelle.tete = droite.tete                            # nouvelle a la même Tête que gauche
            nouvelle.fin = droite.fin                              # nouvelle a la même Tête que gauche
        return nouvelle                                            # on renvoie la référence de notre nouvelle liste

Toutes les opérations internes sont à coût constant. La fonction parvient donc à agir à coût CONSTANT.

Le problème vient de la nature muable des cellules : nous n'avons pas copié le contenu, nous déclarons juste où se trouve le début (et la fin). Si gauche n'est pas vide, nous avons en réalité modifiée la cellule de fin de gauche qui pointe maintenant sur la tête de droite : nous avons donc en réalité également modifié gauche !

19° Rajouter ces instructions dans le programme principal.

Exécuter mentalement ce qui s'y passe et représenter l'état des listes au fur et à mesure.

Lancer ensuite le programme pour vérifier votre résultat...

gauche = Liste()
gauche.inserer_fin(5)
gauche.inserer_fin(15)
gauche.inserer_fin(25)
droite = Liste()
droite.inserer_fin(40)
droite.inserer_fin(50)
droite.inserer_fin(60)
 
print("\nAvant concaténation :")
print("---------------------")
print("Gauche  : ", end='')
gauche.afficher()
print("Droite  : ", end='')
droite.afficher()
 
t = gauche.concatener_problematique(droite)
 
print("\nAprès concaténation :")
print("---------------------")
print("Gauche  : ", end='')
gauche.afficher()
print("Droite  : ", end='')
droite.afficher()
print("t = g+d : ", end='')
t.afficher()
 
droite.supprimer_fin()
droite.inserer_fin(1000)
 
print("\nAprès modification de droite :")
print("------------------------------")
print("Gauche  : ", end='')
gauche.afficher()
print("Droite  : ", end='')
droite.afficher()
print("t = g+d : ", end='')
t.afficher()

20° Comment se nomme ce type de modification, où un contenu muable associé à une variable est modifié à cause d'une action sur une autre variable ?

Attention aux concaténations muables de Listes

La muabilité fait gagner de la place mémoire puisqu'on ne stocke pas de multiples versions de presque les mêmes données.

Mais on perd en sécurité car on peut modifier des choses sans s'en rendre compte, par effet de bord.

Premier problème :

Voici ce qui se passe si on concatène de cette manière très muable une liste lst1 contenant 1->-5->7 à la liste lst2 contenant 10->-20->30.

flowchart LR A[lst1] --> B(1) --> C(5) --> D(7) E[lst2] --> F(10) --> G(20) --> H(30) D --> F Z[lst3=lst1+lst2] --> B

Nous avons obtenu ce que nous voulions avec notre concaténation muable. lst3 référence maintenant 1->-5->7->10->20->30.

Le problème, c'est que c'est aussi le cas de lst1...

Deuxième problème :

Imaginons qu'on veuille alors concaténer lst2 à la liste lst3 contenant 100->-400->800

flowchart LR A[lst1] --> B(1) --> C(5) --> D(7) E[lst2] --> F(10) --> G(20) --> H(30) I[lst3] --> J[100] --> K[400] --> M[800] D --> F H --> J Z[lst3] --> B Y[lst4=lst2+lst3] --> F

Moralité : on a modifié lst1 en agissant sur autre chose de cette liste... lst1 référence maintenant 1->-5->7->10->20->30->100->400->800.

Troisème problème :

Que se passerait-il si on voulait supprimer la tête de la liste 2 ?

En supprimant la tête contenant 10, on supprime également la liaison avec la cellule contenant 7.

flowchart LR A[lst1] --> B(1) --> C(5) --> D(7) E[lst2] --> G(20) --> H(30) I[lst3] --> J[100] --> K[400] --> M[800] H --> J Z[lst3] --> B Y[lst4] --> F(10)

Moralité : on a modifié lst1 en agissant sur autre chose de cette liste... lst1 référence maintenant 1->-5->7. Idem pour lst4...

Comme vous le voyez, il faut être très prudent avec ces listes hautement muables.

CONCLUSION : manipuler directement les cellules et les liaisons est posible et permet de réaliser des choses très rapidement mais cela demande de vraiment réflechir à ce qui est fait.

Complément Hors programme

En Python, on peut comparer les données ou les adresses des données.

Les opérateurs == et != permettent de comparer les contenus.
Les opérateurs is et is not permettent de comparer les adresses et donc de savoir s'il s'agit d'alias ou pas.

a is b revient donc à noter id(a) == id(b)

Exemple :


>>> t = [5,10,20]
>>> t2 = [5,10,20]
>>> t == t2
True
 
>>> t is t2
False
 
>>> id(t)
132360037485312
 
>>> id(t2)
132360039002240

Dans les sujets de BAC, vous ne devriez donc voir apparaître que == et !=.

Complément Hors programme, le retour

Le problème avec les objets est qu'on peut le configurer comme on veut. Notamment, on peut définir une méthode spéciale comme __eq__(self, other) qui permet de savoir quoi répondre lorsqu'on demande d'évaluer objet1 == objet2 pour des instances de cette classe.

Lorsqu'on veut tester si quelque chose est None, on devrait donc systématiquement tester si l'adresse de notre variable mène bien à None et pas tester avec == qui peut être customiser...

Il faudrait donc remplacer tous les tests de cette forme :

self.s == None

par

self.s is None

De la même façon :

self.s != None

par

self.s is not None

7 - FAQ

⇩ ⇧ ⤊

On peut avoir les modules ?

On m'a dit de faire attention aux copies de listes. C'est vrai ?

Activité publiée le 14 10 2020
Dernière modification : 30 10 2022
Auteur : ows. h.

⏪

⏫

⏩