fonctionnement liste chainée mutable

[stefouil25]

Bonjour

Tout d'abord mon niveau dans ce domaine est plutôt débutant (voire carrément)

Pour implémenter ne liste chainée j'ai crée la classe Cellule

class Cellule:
    """ définit la classe Cellule"""
    def __init__(self,v,s):
        self.valeur = v
        self.suivante = s

Sur le livre où je m'inspire (trrès fortement) pour comprendre ces notions voici comment s'implémente une file avec quelques méthodes :

class File:

    def __init__(self):

        self.tete = None
        self.queue = None


    def enfiler(self,x):

        c = Cellule(x,None)

        if self.tete is None:
            self.tete = c

        else:
            self.queue.suivante = c

        self.queue = c


    def __str__(self):

        if self.tete is None:
            res = ''
        else :
            res = ''
            l = self.tete
            while not l is None:
                res = res + str(l.valeur) + ' '
                l = l.suivante
            l1 = self.queue
            res= res+'|'
            while not l1 is None:
                res = res + str(l1.valeur)+' '
                l1 = l1.suivante
          
        return res

J'aimerais vos lumières car je ne comprends pas pourquoi la méthode "enfiler" dans ce cas fonctionne,
il serait question de liste "mutable" mais je ne vois pas pourquoi l'attribut tete qui dans le programme ne s'initialise qu'au début avec la première cellule finit par récupérer tout de même les autres éléments au fur et à mesure que j'"enfile" des valeurs.

j'aimerais comprendre ce qui se passe ...
Merci 100000000 fois pour votre aide
-----

[umfred]

Dans __str__, l est de type Cellule et correspond à la Cellule de tête au moment où l'on fait l =self.tete.
Quand dans la boucle, on fait l=l.suivante, on utilise la propriété suivante de Celulle qui "pointe" vers la Celulle suivante (que l'on récupère); etc
ça fonctionne grâce à enfiler() :
Quand on instancie une File (f=File()), on a f.tete=f.queue=None
Quand on rajoute un élément à la file (f.enfiler("truc")), on a self.tete qui est égale à Cellule("truc",None) et self.queue également.
Quand on ajoute un 2nd élément à la file (f.enfiler("2nd truc")), self.queue vaut Cellule("truc",Cellule("2nd truc",None)) (ce qui modifie aussi self.tete puisque c'est le même objet à ce moment là; ensuite self.queue est l'objet Cellule("2nd truc",None)
etc
donc si l'on veut la valeur du second objet de la file, on peut faire f.tete.suivante.valeur et pour la dernière valeur, f.queue.valeur

Je ne sais si c'est très clair, mais c'est le principe (si besoin d'éclaircir encore un peu, demande)

[stefouil25]

...
Quand on ajoute un 2nd élément à la file (f.enfiler("2nd truc")), self.queue vaut Cellule("truc",Cellule("2nd truc",None)) (ce qui modifie aussi self.tete puisque c'est le même objet à ce moment là; ...

Bonjour Umfred, tout d'abord Merci énormément pour avoir pris le temps de me répondre si rapidement.
J'ai gardé la partie de ton commentaire qui me pose question et qui effectivement est au coeur de mon questionnement : Pourquoi self.tete et self.queue pointent vers les mêmes éléments ?
Au début lorsque la File est vide c'est bien ce qui se passe, mais en Second, dans le script seul self.queue est modifié ce qui donne effectivement le résultat que vous avez écrit, mais je en comprends pas pourquoi self.tete alors lui aussi pointe sur cette même cellule...
Une zone d'ombre plane sur ma réflexion...
Vous avez pointé le doigt sur mon souci, si je peux encore abuser de votre patience... merci encore pour votre prochaine réponse !

[pm42]

J'ai gardé la partie de ton commentaire qui me pose question et qui effectivement est au coeur de mon questionnement : Pourquoi self.tete et self.queue pointent vers les mêmes éléments ?

Ils ne pointent pas vers les mêmes éléments. self. tete pointe toujours vers le 1er élément de la liste et self.queue vers le dernier. Qui sont différents sauf quand la liste ne contient qu'un seul élément.
self.tete ne va jamais changer dès qu'on aura mis un 1er élément dans la liste.

L'élément pointé par self.tete a le chainage vers le 2nd élément qui a le chainage vers le 3ème élément.
A la limite, on pourrait se passer de self.queue pour ajouter : on parcourerait toute la liste pour trouver le dernier élément, celui qui n'a de successeur et on le modifierait.
Mais ce serait lent : donc on garde self.queue pour accéder rapidement à ce dernier élément.
Et quand on ajoute, on fait le chainage du dernier qui devient l'avant-dernier et on ajoute. C'est le self.queue.suivante = c.
Et bien sur, maintenant que le dernier élément a change, on met à jour self.queue.

[A voir en vidéo sur Futura]

[umfred]

Bonjour Umfred, tout d'abord Merci énormément pour avoir pris le temps de me répondre si rapidement.
J'ai gardé la partie de ton commentaire qui me pose question et qui effectivement est au coeur de mon questionnement : Pourquoi self.tete et self.queue pointent vers les mêmes éléments ?
Au début lorsque la File est vide c'est bien ce qui se passe, mais en Second, dans le script seul self.queue est modifié ce qui donne effectivement le résultat que vous avez écrit, mais je en comprends pas pourquoi self.tete alors lui aussi pointe sur cette même cellule...
Une zone d'ombre plane sur ma réflexion...
Vous avez pointé le doigt sur mon souci, si je peux encore abuser de votre patience... merci encore pour votre prochaine réponse !

Pour l'expliquer différemment de pm42, en réutilisant (précisant) mon exemple:
Au second ajout, au début d'enfiler(), self.queue et self.tete correspondent tous deux au 1er élément, qui est modifier via self.queue.suivant et ensuite self.queue correspond au 2nd élément (le dernier entré dans la file) et self.tete correspond toujours au 1er élément.
Au troisième tour (j'aurai peut-être dû continuer en fait) (toujours au début), self.queue correspond au dernier élément entrée (soit le 2nd) dont on va modifier l'attribut suivante avant de correspondre à ce dernier élément. et ainsi de suite

[pm42]

Pour l'expliquer différemment de pm42,

Ce qui est toujours une bonne idée et en te lisant, cela m'a fait penser qu'une bonne technique pour comprendre ce qui se passe est d'écrire un programme qui part d'une liste vide, ajoute 3 éléments et de regarder ce qui se passe au debugger en voyant les valeurs que prennent les variables.

[umfred]

je dois avouer que c'est un peu ce que j'ai fait

f=File()
f.enfiler(1)
f.enfiler(2)
f.enfiler("titi")
f.enfiler(3)
print(f)

plus quelques essais dans l'interpréteur python (commentés)

1 2 titi 3 |3 #résultat du code ci-dessus
>>> f
<__main__.File object at 0x02F80328> # on voit que f est un objet de File
>>> f.tete
<__main__.Cellule object at 0x0318AF58> #on voit que f.tete est un objet de type Cellule à une certaine adresse
>>> f.queue
<__main__.Cellule object at 0x03952070> #on voit que f.queue est un autre objet Cellule (à une autre adresse)
>>> f.tete.suivante
<__main__.Cellule object at 0x0318AF10> #on voit ici que f.tete.suivante est un objet Cellule autre que f.tete (car adresse différente)
>>> f.queue.valeur
3 # accès à la valeur de la dernière entrée
>>> f.tete.valeur
1 # accès à la valeur de la 1ère entrée (la "tête")
>>> f.tete.suivante.valeur
2 #accès à la valeur de la 2nde entrée "tête+1" si j'ose dire

[pm42]

plus quelques essais dans l'interpréteur python (commentés)

Bonne idée en effet : pour un petit programme, on peut déjà voir pas mal de choses rien qu'avec l'interpréteur. C'est d'ailleurs ce que je fait au quotidien.

[stefouil25]

Merci beaucoup pm42 et umfred votre aide m'a été précieuse !!
Je vous remercie également pour votre incroyable rapidité !

A bientôt !