4.2.1   Notions théoriques

Répondez aux questions suivantes:

1. Qu'est-ce qu'une liste chaînée?
2. Qu'est-ce qu'une structure de données? Donnez un exemple.
3. Expliquez la différence entre un noeud (Node) et sa cargaison (cargo).
4. Expliquez la différence entre un noeud (Node) et une liste chainée (LinkedList).
5. Dans le livre et le cours magistral, la notion d'une liste chaînée a d'abord été expliqué sans la classe LinkedList, simplement en chaînant des noeuds l'un à l'autre. Pourquoi avons nous alors besoin d'une classe LinkedList?
6. Expliquez et donnez un exemple du caractère ambiguë d'un noeud.

4.2.2   Utilisation d'une LinkedList

Question 1 : Manipuler une liste vide

Cette question concerne l'utilisation de la classe LinkedList dont le code se trouve dans l'annexe suivante du syllabus : Appendix - Source code of linked lists

Utilisez la classe LinkedList pour créer une liste chaînée vide l.

Donnez une instruction Python pour imprimer le contenu de cette liste l.

Quel résultat sera affiché si on essaie d'imprimer la liste l avec l'instruction print(l)? Expliquez.

Donnez une instruction Python pour imprimer la taille de cette liste l .

Quel résultat sera affiché si on essaie d'imprimer la taille avec l'instruction print(l.__length)? Expliquez.

Question 2 : Remplir la liste

Pour ajouter des éléments à une liste vide, quelqu'un a écrit les instructions suivantes:

l = LinkedList()
l.add(3)
l.add(2)
l.add(1)
l.print()

Mais quelqu'un d'autre à écrit:

l = LinkedList()
l.add(Node(3))
l.add(Node(2))
l.add(Node(1))
l.print()

Dans les deux cas, exécuter l'instruction l.print() affichera [ 1 2 3 ].

Lequel des deux fragments de code ci-dessus vous semble correct? Pourquoi l'autre imprime quand-même le même résulat?

Indice : qu'est-ce qui se passe si on exécute l'instruction print(Node(Node(Node(1))))? Pouvez-vous expliquer?

4.2.3   Imprimer une liste chaînée

Dans le code donné dans l'annexe Appendix - Source code of linked lists la méthode print() de la classe LinkedList imprime les éléments d'une liste chaînée, séparés par une espace. Par exemple:

>>> l = LinkedList()
>>> l.add(3)
>>> l.add(2)
>>> l.add(1)

>>> l.print()
[ 1 2 3 ]

Or, normalement la convention est de séparer les éléments d'une liste par des virgules. Ajoutez une nouvelle méthode print_avec_virgule() dans la classe LinkedList qui imprime la liste comme suite:

>>> l.print_avec_virgule()
[ 1, 2, 3 ]

Attention: il n'y a pas de virgule après le dernier élément ou si on imprime une liste vide.

>>> l = LinkedList()
>>> l.print_avec_virgule()
[ ]

4.2.4   Imprimer une liste chaînée (généralisation)

Généralisez la méthode print_avec_virgule de l'exercice précédente par une méthode print_avec_separateur qui peut prendre n'importe quelle séparateur. Par exemple:

>>> l = LinkedList()
>>> l.add(3)
>>> l.add(2)
>>> l.add(1)

>>> l.print_avec_separateur(", ")
[ 1, 2, 3 ]
>>> l.print_avec_separateur(" ")
[ 1 2 3 ]
>>> l.print_avec_separateur(" - ")
[ 1 - 2 - 3 ]

4.2.5   Initialiser une liste chaînée

4.2.6   Supprimer un élément

4.2.7   Ajouter un élément à la fin

Ajoutez à la classe LinkedList une méthode add_to_end(self, cargo) pour ajouter un noeud en queue de la liste. Ajoutez d'abord un nouvel attribut last dans la méthode d'initialisation pour garder une référence vers ce dernier élément. Changez ensuite la méthode add pour assigner cette référence lors de l'ajout du premier noeud, et la méthode remove pour remettre cette référence à None lorsque la liste est de nouveau vide. Implémentez ensuite la méthode add_to_end.

Étapes de l'ajout d'un noeud dans une liste chainée :

1. Créer un nouveau nœud (new_node) composé de la valeur à ajouter dans la liste.
2. Parcourir la structure pour identifier le nœud précédant l’emplacement où insérer new_node.
3. Pour ne pas perdre la référence vers le nœud suivant, faire pointer new_node.next vers le nœud qui suit le nœud courant .
4. Insérer new_node (cas général, attention aux cas particuliers), en faisant pointer le nœud courant vers new_node.
5. Mettre à jour les attributs de la classe le cas échéant (taille, tête de liste, etc.).

Pour plus de détails sur les étapes, allez voir le catalogue : Ajout d'un noeud dans une liste chainée .

4.2.8   Supprimer un élément à la fin

Est-ce facile d'implémenter une méthode remove_from_end(self, cargo) pour supprimer un élément de la queue d'une LinkedList? Expliquez en mots comment vous feriez.

4.2.9   Imbriquer une classe dans une autre

En Python il est possible d'imbriquer une classe dans une autre. Ceci peut être utile si une classe n'est utilise que par une seule autre classe. C'est le cas ici avec la classe Node. Ce n'est qu'une classe auxiliaire pour la classe LinkedList. Adaptez le code de votre classe LinkedList en imbriquant le code de la classe Node dedans. Il suffit d'indenter le code de la classe Node et de changer chaque référence à la classe Node à l'interieur de la classe LinkedList par self.Node.

Quels sont les avantages et désavantages d'imbriquer la classe Node dans la classe LinkedList?

4.2.10   Insérer un élément

Considérez qu'on désire utiliser la classe LinkedList pour stocker une liste de strings. On souhaite qu'elle soit en permanence en ordre alphabétique croissant.

1. Dessinez complètement une telle liste chainée contenant les trois strings "abc", "def" et "xyz".

2. Expliquez en français et dessinez les opérations à effectuer pour ajouter un Node contenant "aaa" dans cette liste.

3. Même question avec un Node contenant "ghi".

4. Même question avec un Node contenant "def".

5. Même question avec un Node contenant "zzz".

4.2.11   Tests unitaires

Lors de la mission précédente, les tests unitaires avec unittest ont été introduits. Créez un test unitaire pour tester la classe LinkedList. Ce test doit contenir des tests pour les différentes méthodes de la classe LinkedList comme size(), first() ou add(valeur) (code original), remove() (question 4.2.6), add_to_end(valeur) (question 4.2.7) ou insert(valeur) (question 4.2.10). Pour vous mettre sur le bon chemin, votre classe test aura la structure suivante:

import unittest

class LinkedListTest(unittest.TestCase):
    """Classe de test utilisé pour tester la classe LinkedList"""

    def test_size(self):
        """Test de la methode size() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_first(self):
        """Test de la methode first() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_add(self):
        """Test de la methode add(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

    def test_remove(self):
        """Test de la methode remove() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_add_to_end(self):
        """Test de la methode add_to_end(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

    def test_insert(self):
        """Test de la methode insert(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

if __name__ == '__main__':
    unittest.main()