Listes chaînées en POO

Une liste chaînée est une structure de données classique en informatique. Elle permet de stocker un nombre quelconque de valeurs tout en maintenant un ordre en elles (la première valeur précède la deuxième qui précède elle-même la troisième etc).

On se propose dans cet exercice de mettre en œuvre les listes chaînée à l'aide de la programmation orientée objet. Pour ce faire on va utiliser deux classes :

  • la classe Maillon qui représentera les différents éléments de la liste chaînée ;
  • la classe ListeChainee qui représentera la liste chaînée à proprement parler.
Classe Maillon

Une liste chaînée est une succession de Maillon. Chacun d'entre eux est caractérisé par deux attributs :

  • sa valeur qui peut être quelconque et qui est obligatoirement fournie lors de l'instanciation de l'objet ;
  • son successeur qui est soit vide (None en Python) soit un autre Maillon.

Cette structure de données permet donc de stocker, dans chaque Maillon, une unique valeur tout en pointant vers le prochain Maillon qui contient la valeur suivante etc.

Maillons

Un Maillon dont l'attribut successeur est None est le dernier de la chaîne.

On a chargé dans l'éditeur ci-dessous une classe Maillon dont le code est fourni ci-dessous 1. Vous pouvez l'utiliser sans l'importer.

Code de la classe Maillon 
class Maillon:
    """
    Classe représentant un maillon d'une liste chaînée

    Attributs :
    * valeur : une valeur de type quelconque
    * successeur : le successeur de ce Maillon. 
                Cet attribut vaut None si ce Maillon n'a pas de successeur
                Dans le cas contraire, le successeur est lui même un Maillon

    Exemples :
    >>> troisieme = Maillon("Loulou")
    >>> deuxieme = Maillon("Fifi")
    >>> deuxieme.successeur = troisieme
    >>> premier = Maillon("Riri", deuxieme)
    """

    def __init__(self, valeur, successeur=None):
        self.valeur = valeur
        self.successeur = successeur

    def __str__(self):
        if self.successeur is None:
            prochain = "∅"
        else:
            prochain = f"{self.successeur}"
        return f"{self.valeur} -> {prochain}"

Compléter l'éditeur afin de répondre aux questions.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013pbvM(40i2edm3s7= 1o5lSnatf)9h6qcrg.yPFu8/050l0k0z0y0i0v0o0r0G0v0y0o0o0q010z0i0b010406050o0N0m0m0y0H0K040w0t0v0N0*0t0x050P0;0?0^0`0/0b04131a051d0P1d1f1a0/0l0i0d0Y0!0$0(0D0i0I0D0v1t0D0z0-050T0c0v0k1o0#0%011s1u1w1u0z1C1E1A0z0c0t0l0`1B0H1b0z0D0Y0}0o0b0y0x0(0j011G1q010A0V0k0x0y0m0k1A1(1*1/1I1=1E1^1`0-0a0r0L0H0t0b0t0o0i100x0r0R1$0H0H0k0G2f131}0x1b0P1!2s0z1Y1X1Z0l1 0(1w0x1@2c1A1l1n0Z1H2C0i2E0x1U1m1A0b2l1b2q2s2W0:1)2g2K1:2P0H0@0v0-0r0s2p2!0.2Z1~2$1I2(2*2,0j2/1*2;2q2B012_0y2+040r0n2}2r0/302@0(33350r0g392 2!313f2,0u3j3b3l3d320t2)342,0E3q2=2#1p2^3v2`360p3A3c3D3e3F3x360O3J3s3L3u3w3g0C3R2?3T3n040s0h3j1c2U132I2v0l2z310G1U1{1b3-1e3+2Y142:053=0R2V3S2L010G0s0-030r0y0r0k0o0z0r0N2g0e0U0v0v111$0x0z1@1*4f0!0r0d340k0N0H2-3Y3C440x0-0y3j0r3B310t0-0q4I4K3t4F044j0V4m123}2~4Q3T0,040f3)3K440m0i0-2.4Y2r4!444$0B4C3;4704490c4c4e4g4i4k4W4o4q1^4p0r4u4w1E4z0r2|4:3k3Z4E0-0c4P4*1:4M044O5g4J5n2^0-4U4l114)431:4$4(5g4=1:4,0-5f2Y5u0(4@4_3t46480Y4 4f4h0r5x543=4p4r585a4x5d385g3r5i2%0-0G5m5B1I5p5r2W5t5?3e5w535z5F5M015D5A5.1I5I045+5L5|630-4^5,5G1I5R4|0r0M0U2l4c2g0o3v4q0r0F0N1F4~6r2e591F0;0G0G4d0o4y4A2i4H6g624S6L6b660(5p0J654D5/046D6F0$6I5=6R015^6%6W5v045l6M6c6j496m0i6o1@0r6r0H6t6v1F0G6{0t6A1E6{0N6E6G6I2h6x5P3!5k6V4L0-6U616c4S6Z794z6+7h5q7q4R5:3A0P400k2s2T7z3,1m3.2v2x2t1T1V2v0y1D7C0P3-0/7P0S4k0o04.
Classe ListeChainee

Une instance de la classe ListeChainee est caractérisé par un unique attribut : sa tete.

Celle-ci vaut None si la liste est vide.

Dans le cas contraire, la tete est un objet de type Maillon. Ceux-ci pouvant être enchaînés les uns à la suite des autres, la seule connaissance du premier Maillon permet de retrouver tous les éléments de la liste.

Liste chaînée

On souhaite donc écrire une classe ListeChainee répondant au contrat suivant :

  • une liste chaînée possède un unique attribut nommé tete tel que décrit ci-dessus ;

  • lors de sa création, une liste chaînée est initialement vide. Le constructeur ne prend donc pas de paramètre (hormis self) ;

  • la méthode est_vide renvoie le booléen indiquant si la liste est vide ou non ;

  • la méthode cons (pour construit) prend en paramètre une valeur et ajoute celle-ci au début de la liste.

    On précise que, compte-tenu de l'implantation souhaitée, ajouter une valeur au début de la liste chaînée nécessite d'ajouter un nouveau Maillon en tête de liste.

  • la méthode longueur renvoie le nombre d'éléments présents dans la liste.

Compléter l'éditeur ci-dessous en écrivant le code de la classe ListeChainee. Le code de la classe Maillon est déjà chargé, vous pouvez l'utiliser sans l'importer.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.8709.128013:LpM(40îed3;N 1Ej}o5_Aên)h6,qcyCFuvi2+xms7=wlSatf9{Rrg.*TéPkb8/050l0k0X0W0L0U0Q0p0F0U0W0Q0Q0S010X0L0e010406050Q0J0P0P0W0$0G040V0u0U0J140u0z050:1b1d1f1h190e041q1x051A0:1A1C1x190l0L0K0|0~10120B0L0%0B0U1Q0B0X17050@0.0U0k1L0 11011P1R1T1R0X1Z1#1X0X0.0u0l1h1Y0$1y0X0B0|1k0Q0e0W0z120M011%1N010Y0_0k0z0W0P0k1X2224291)2c1#2f2h170b0p0,0$0u0e0u0Q0L1n0z0p0=200$0$0k0F2C1q2k0z1y0:1~2P0X1|1{1}0l2m121T0z2e2z1X1I1K0}1(2Z0L2#0z1^1J1X0e2I1y2N2P2`1a232D2+2a2:0$1e0U170p0q2M2~182}2l301)3234360M39243b2N2Y013g0W35040p0m3k2O193n3e123q3s0p0h3w3m2~3o3C360v3G3y3I3A3p0u333r360C3N3c2 1M3f3S3h3t0R3X3z3!3B3$3U3t0/3*3P3,3R3T3D0Z3=3d3@3K040q0i3|3Z2,3^3%0q381r3a3O3}453 0q3j4a3l4c44313.3s0q3v4i3x3Y3J4n170q3F4r3H4d4m3_4w3M4z4k4u4D403W4G4t3Q4f3)4M3+4e4v403;4R3?4T4J0q3{4X4B3#4J0M424%4l4)3%0M492`4H4O4U0M4h4?4N3~4_4q4|4S4C4:4y514Y533/0M4F564(3-4*4L5c4.5e4:4Q5h4I4:4W5m4^4*4$5q4~4J0m4,5u4Z3%0m4=4b4}5A3/0m4{5E524/5H505K575M3s0m555P5d465H5b5V5i5X5S5g5!5n5H5l5)5r5B5p5-5v5B5t5;5G3s0h5y5^585`5D4j5F5~170h5J615L5j3/0h5O675Q695`5U6d5W3 0h5Z3l1z2^1q2)2S0l2W3o0F1^2i1y6r1B6p2|4z056w0=2_6e010-173e3G621)0T366O683p0F170d0L0Q0X0k0H0B0^2#0k6T6J16040c433o6R3t0p6^6,5W0Q0l17016 6;3Q6|366^0p0H3!1$0l0+0F0$1J240X0p0J2#0p1T6!1$0F6(0j0z0+1$0P6Z1$2e0p0u0k0J0K2I201d1$7i1$1b0F0F0k100L1o2E1$010f0^0U0U1o013N4@3@736@6^0x1/7d0.1m0p6:4-3o7$750p0)0p6#6#7.7k1$7T0_7W2D2F0X0y7{0u0J0p0o1o7I0L7k0W7k6Z7{7M7g0K0L2F0g0F0 0p230$2E0+0Y0W1m0A7Z6P127=750r0O0k0P0e1#0{7/5z2a8D6^020%0X0n8R8T8V0n7k0F0p0S0p6Y7m6%6)0k0k0g8z7:726}7%0p8X8^8S8Y0U0F0(8j0w8l0=8.717#8=7?0*0$0J6+8:95748Q8`8_8T8Z0(6w0z0Q0g0m8/8N1)8P8@9g9v9i8|8~6!908m8-9q5}9s96750I3r0Q9b9r8C9H9f8W9w8{8}810%9a0J0$939c459t604s6U9t6 7Y4G067?8B6K170=0Y6`5#6?0p9_3o0Y0P170w0w2.2Ba29}3Q6.0ga73@0.6.9L0U9^6E6U6.0A8M4b7?9:6Uad17afah2|6U0u170(ab4e177`9M3a9|aw170S3GaG6J0-6W048a2#7ZapaM9?0kau3a9;9{aA310Y178 91aE6naj17aaai6Jar04ata#1)akam6i9`9eaoa^9O6~6 0#2e0K0u0L1$1#0p1@1k7s2D2.1I0E0J7f0p2A8e8g7m0p8j0pa*7y882:0z9,3Nao759;6L042I0X9Y1p4zaL5Wa=a@a:5Wax04azbO5#bx04aDaK9;0u6?6ZbY6UaN17aQa+3x9/bBb(aVaXa,6Ja!bT3Ja%049l0Qb001a9b bM0kagb 6.0Db%6JbV0Oc617al94459{bA9|b_8;b2010x0s877{0~bs3r7A8t0O0p8x8u7,7g2Fct7l6#by4GcjbK5#c3c5cl3@bQbSavcaaC0?b,3tbZaIc96j177 7V1ocd04a/cTc$04cccP45c7c#cMaec4b=2OcZbRb bVbXc=2aakaSb/aU049@b b^c.bUb{9V9X0$c+c-aYaqc`cOdd3oa`cg2acibAb 7$9,b40zb6b87}0p2:0P0.7D0l000+0U0+2h0z0X0{2@0+9LdP0{0l240{cF8h2i70cJcjbC170Lc|cYdmasc{b cRd0a(9Aa*djcfd(cK6_b:bE0?bHc^3o7u175|4jcK9;d10u0@0Ue43QbQaJbJ9;e604e83xea6UbV6w9Y7fegcQc!ekd/a?d;d31)d?eD3BcV6#bzd)e00T1P1#ewaBb|870$evez6Jb!d+b~eWbP6?2:0XeQ2ab)aP8bc+a{epd~d cUbWed3re*eE170Nej2`cLe50L4weKe=eb6MeTeVf0c~e aFf7eSeudPd=ayd@a?0J7K7M9L9Yf5a e0bFe3e#bUaCe_ef9.aT5WbDdaeG01dcdl6J9 a10w6!0$a6fHc1fHcNd-9;dr9#dta~9:fHdx6 0H1o0K0k0$2A7P7xfPcI4?eqd8d,e{12fVfjc fHbVa)9Cd{e:18e=e?fE17fv0$bIfb9*2704010a9-f@eLd8gbgdfe9*0W17fWgf6~dwf3040!c2dngueXfkg0eIcX9;2A170tdwgggk5E0:6G0k2P2@gT6q1J6s2S2U2Q1@1_2S0W1!gW0:6r19g-0?7U0Q04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.8709.128013:LpM(40îed3;N 1Ej}o5_Aên)h6,qcyCFuvi2+xms7=wlSatf9{Rrg.*TéPkb8/050l0k0X0W0L0U0Q0p0F0U0W0Q0Q0S010X0L0e010406050Q0J0P0P0W0$0G040V0u0U0J140u0z050:1b1d1f1h190e041q1x051A0:1A1C1x190l0L0K0|0~10120B0L0%0B0U1Q0B0X17050@0.0U0k1L0 11011P1R1T1R0X1Z1#1X0X0.0u0l1h1Y0$1y0X0B0|1k0Q0e0W0z120M011%1N010Y0_0k0z0W0P0k1X2224291)2c1#2f2h170b0p0,0$0u0e0u0Q0L1n0z0p0=200$0$0k0F2C1q2k0z1y0:1~2P0X1|1{1}0l2m121T0z2e2z1X1I1K0}1(2Z0L2#0z1^1J1X0e2I1y2N2P2`1a232D2+2a2:0$1e0U170p0q2M2~182}2l301)3234360M39243b2N2Y013g0W35040p0m3k2O193n3e123q3s0p0h3w3m2~3o3C360v3G3y3I3A3p0u333r360C3N3c2 1M3f3S3h3t0R3X3z3!3B3$3U3t0/3*3P3,3R3T3D0Z3=3d3@3K040q0i3|3Z2,3^3%0q381r3a3O3}453 0q3j4a3l4c44313.3s0q3v4i3x3Y3J4n170q3F4r3H4d4m3_4w3M4z4k4u4D403W4G4t3Q4f3)4M3+4e4v403;4R3?4T4J0q3{4X4B3#4J0M424%4l4)3%0M492`4H4O4U0M4h4?4N3~4_4q4|4S4C4:4y514Y533/0M4F564(3-4*4L5c4.5e4:4Q5h4I4:4W5m4^4*4$5q4~4J0m4,5u4Z3%0m4=4b4}5A3/0m4{5E524/5H505K575M3s0m555P5d465H5b5V5i5X5S5g5!5n5H5l5)5r5B5p5-5v5B5t5;5G3s0h5y5^585`5D4j5F5~170h5J615L5j3/0h5O675Q695`5U6d5W3 0h5Z3l1z2^1q2)2S0l2W3o0F1^2i1y6r1B6p2|4z056w0=2_6e010-173e3G621)0T366O683p0F170d0L0Q0X0k0H0B0^2#0k6T6J16040c433o6R3t0p6^6,5W0Q0l17016 6;3Q6|366^0p0H3!1$0l0+0F0$1J240X0p0J2#0p1T6!1$0F6(0j0z0+1$0P6Z1$2e0p0u0k0J0K2I201d1$7i1$1b0F0F0k100L1o2E1$010f0^0U0U1o013N4@3@736@6^0x1/7d0.1m0p6:4-3o7$750p0)0p6#6#7.7k1$7T0_7W2D2F0X0y7{0u0J0p0o1o7I0L7k0W7k6Z7{7M7g0K0L2F0g0F0 0p230$2E0+0Y0W1m0A7Z6P127=750r0O0k0P0e1#0{7/5z2a8D6^020%0X0n8R8T8V0n7k0F0p0S0p6Y7m6%6)0k0k0g8z7:726}7%0p8X8^8S8Y0U0F0(8j0w8l0=8.717#8=7?0*0$0J6+8:95748Q8`8_8T8Z0(6w0z0Q0g0m8/8N1)8P8@9g9v9i8|8~6!908m8-9q5}9s96750I3r0Q9b9r8C9H9f8W9w8{8}810%9a0J0$939c459t604s6U9t6 7Y4G067?8B6K170=0Y6`5#6?0p9_3o0Y0P170w0w2.2Ba29}3Q6.0ga73@0.6.9L0U9^6E6U6.0A8M4b7?9:6Uad17afah2|6U0u170(ab4e177`9M3a9|aw170S3GaG6J0-6W048a2#7ZapaM9?0kau3a9;9{aA310Y178 91aE6naj17aaai6Jar04ata#1)akam6i9`9eaoa^9O6~6 0#2e0K0u0L1$1#0p1@1k7s2D2.1I0E0J7f0p2A8e8g7m0p8j0pa*7y882:0z9,3Nao759;6L042I0X9Y1p4zaL5Wa=a@a:5Wax04azbO5#bx04aDaK9;0u6?6ZbY6UaN17aQa+3x9/bBb(aVaXa,6Ja!bT3Ja%049l0Qb001a9b bM0kagb 6.0Db%6JbV0Oc617al94459{bA9|b_8;b2010x0s877{0~bs3r7A8t0O0p8x8u7,7g2Fct7l6#by4GcjbK5#c3c5cl3@bQbSavcaaC0?b,3tbZaIc96j177 7V1ocd04a/cTc$04cccP45c7c#cMaec4b=2OcZbRb bVbXc=2aakaSb/aU049@b b^c.bUb{9V9X0$c+c-aYaqc`cOdd3oa`cg2acibAb 7$9,b40zb6b87}0p2:0P0.7D0l000+0U0+2h0z0X0{2@0+9LdP0{0l240{cF8h2i70cJcjbC170Lc|cYdmasc{b cRd0a(9Aa*djcfd(cK6_b:bE0?bHc^3o7u175|4jcK9;d10u0@0Ue43QbQaJbJ9;e604e83xea6UbV6w9Y7fegcQc!ekd/a?d;d31)d?eD3BcV6#bzd)e00T1P1#ewaBb|870$evez6Jb!d+b~eWbP6?2:0XeQ2ab)aP8bc+a{epd~d cUbWed3re*eE170Nej2`cLe50L4weKe=eb6MeTeVf0c~e aFf7eSeudPd=ayd@a?0J7K7M9L9Yf5a e0bFe3e#bUaCe_ef9.aT5WbDdaeG01dcdl6J9 a10w6!0$a6fHc1fHcNd-9;dr9#dta~9:fHdx6 0H1o0K0k0$2A7P7xfPcI4?eqd8d,e{12fVfjc fHbVa)9Cd{e:18e=e?fE17fv0$bIfb9*2704010a9-f@eLd8gbgdfe9*0W17fWgf6~dwf3040!c2dngueXfkg0eIcX9;2A170tdwgggk5E0:6G0k2P2@gT6q1J6s2S2U2Q1@1_2S0W1!gW0:6r19g-0?7U0Q04.

  1. la méthode __str__ met en forme l'affichage d'un objet. Cette fonction est appelée lors des conversions au format str par exemple lorsque l'on fait print(objet). ↩