Données Liste Implémentation

Identification

Infoforall

13 - Implémenter une Liste 2/3


Nous avons implémenter une liste sous forme d'une structure de données composée d'un tuple (tête, queue).

Nous allons faire la même chose avec un tableau aujourd'hui.

Principe du tableau

Prerequis : l'activité sur les Listes et la première implémentation sous forme de tuple (pour comprendre l'intérêt de celle-ci).

1 - Implémentation en tableau

Nous allons réaliser une autre implémentation, l'implémentation du type abstrait Liste en utilisant un tableau. C'est très utile si on lit plus souvent les données qu'on ne les insère ou les supprime.

Pourquoi ? Simplement car on lit les éléments d'un tableau en un temps constant : Θ(1)

Nous allons encore une fois réaliser ceci :

Principe de l'interface LISP entre l'utilisateur et les données

Dans le cadre de cette activité, je vous fournis l'interface de base que nous allons analyser. Ensuite, vous devrez créer l'interface souple.

Commençons par les 3 fonctions d'interface les plus simples : nouvelleListe, estVide et lireTete.

01° Mémoriser ces fonctions. Observer les 3 fonctions. Répondre ensuite à ces questions :

  1. comment se nomme dans Python le type (pas abstrait du coup) de la structure de données utilisée ici pour implémenter notre Liste abstraite ?
  2. Va-t-on avoir le droit d'utiliser toutes les méthodes qu'offre Python sur ce type ?
  3. L'utilisateur aura-t-il le droit d'utliser directement [index] pour lire le contenu de nos données ?

...CORRECTION...

Nous utilisons le type natif list.

Néanmoins, nous allons l'utiliser comme un simple tableau statique (déclaration d'un tableau de taille fixe, lecture et modification à coût constant, décalage à coût linéaire).

L'utilisateur devra se limiter à utiliser nos fonctions d'interface. D'ailleurs, notre fonction lireTete intégre une vérification de la taille du tableau. Cela permettra d'éviter certaines erreurs de tentative de lecture de l'index 0 sur un tableau vide ! C'est l'un des intêret de l'interface, elle est censée éviter un certain nombre de problèmes en vérifiant la validité des changements par exemple.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
'''Implémentation de type abstrait Liste en utilisant des tableaux''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tableau vide [] ''' return [] def estVide(lst) : '''Renvoie True si la liste est vide :: param lst(Liste) :: la Liste à tester :: return (bool) :: True si liste peut être vu comme une liste vide ''' return lst == [] def lireTete(lst) : '''Renvoie la tête de la liste, sans toucher à la liste elle-même :: param lst(Liste) :: la liste dont on désire lire la tête :: return (Elt) :: la tête voulue, None si la tête est vide ''' if not estVide(lst) : return lst[0]

Comment va-t-on gérer les insertions dans notre liste implémentée sous forme de tableau ?

Le choix a été fait de créer des listes non-mutables : il va donc falloir créer un deuxième tableau et de décaler les éléments vers la droite.

Exemple : on veut insérer l'élément 23 dans la liste intiale (5, 10, 15, 25, 30, 35) Principe de l'insertion dans une liste sur une implémentation tableau

On voit donc que le tableau implémentant la liste après insertion

  1. doit posséder une case en plus
  2. contient les éléments de la première liste mais avec un décalage de 1 vers la droite : les index sont plus grands de 1
  3. possède un nouvel élément à l'index 0

02° Rajouter maintenant la fonction insererTete :

1 2 3 4 5 6 7 8 9 10 11 12 13
def insererTete(x, lst) : '''Renvoie une nouvelle liste où x est la tête et liste la queue :: param x(Elt) :: un élément compatible avec votre liste qui devient la tête :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)+1)] # On crée une liste plus longue de 1 for index in range(len(lst)) : reponse[index+1] = lst[index] # Décalage vers la droite reponse[0] = x # On place la tête return reponse # On renvoie la nouvelle liste
  1. cette fonction modifie-t-elle la liste en place ou crée-t-elle une copie qu'elle renvoie ?
  2. pourquoi le tableau reponse (créé par compréhension ligne 9 ci-dessus) est-il créé avec une case supplémentaire par rapport au tableau reçu en paramètre ?
  3. comment est-on parvenu à décaler les bonnes valeurs dans le second tableau ? (attention : à savoir expliquer et refaire)
  4. Programmation interne : le développeur va-t-on avoir le droit d'utiliser toutes les méthodes qu'offre Python sur ce type list qu'on utilise pour nos tableaux ?
  5. Interface externe : l'utilisateur aura-t-il le droit d'utiliser directement [index] pour lire le contenu de nos données du coup ?

...CORRECTION...

  1. Pas d'effet de bord : on crée un tableau ayant une case en plus, on le remplit puis on le renvoie.
  2. On insère une nouvelle valeur, il vaut bien une case en plus non ?
  3. Voir Lignes 10-11 : à l'aide d'une boucle sur les index de la liste-tableau d'origine, on crée les cases de la copie en décalant de 1 vers la droite les valeurs. On rajoute donc 1 à l'index.
  4. Non, la personne qui code ces fonctions ne pourra pas utiliser toutes la panoplie des méthodes du type list-python. Si on décide d'utiliser des tableaux statiques, on ne devra pas par exemple utiliser append. Si on décide d'utiliser des tableaux dynamiques, on pourra cette fois rajouter et supprimer directement des cases. Le tout est de savoir comment on veut implémenter nos listes.
  5. Non, l'utilisateur n'en a pas le droit : cette utilisation ne figure pas explicitement dans l'interface fournie. Dans la description de l'interface, on aurait très bien pu remplacer lireTete par liste[0], mais on ne l'a pas fait. On respecte le travail et les choix de celui qui a conçu l'interface. Si ça tombe, il a une très bonne raison d'avoir sélectionné la première façon de faire.

On sait maintenant créer des listes, lire la tête et insérer des têtes. Reste à savoir supprimer les têtes.

Principe de la suppression dans une liste sur une implémentation tableau

03° Combien de cases va devoir avoir le tableau contenant la liste modifiée ? Va-t-on devoir décaler les cases vers la gauche (on diminue l'index) ou vers la droite (on augmente l'index) ?

...CORRECTION...

Une case en moins, puisqu'on supprime.

On voit bien qu'on va devoir décaler vers la gauche, en diminuant les index des éléments qu'on va déplacer.

04° Compléter le code de la fonction supprimerTete dont on vous donne le prototype et la documentation.

Attention, pensez d'abord à gérer le cas de la liste vide (on renvoie alors une liste vide) avant de commencer à déplacer les éléments.

Prototype

1
def supprimerTete(lst:Liste) -> Liste :

Code à compléter

1 2 3 4 5 6 7 8
def supprimerTete(lst) : '''Renvoie une nouvelle liste où on a supprimé la tête de l'ancienne :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' pass

Remarque : on remarquera que Python ne connait pas notre type "Liste". Le module typing permet par contre de le faire et donc ensuite de vérifier les préconditions avec des assertions si on veut.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14
def supprimerTete(lst) : '''Renvoie une nouvelle liste où on a supprimé la tête de l'ancienne :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' if estVide(lst) : # la liste envoyée est [] return nouvelleListe() else : reponse = [0 for x in range(len(lst)-1)] # On crée une liste moins longue de 1 for index in range(1,len(lst)) : reponse[index-1] = lst[index] # Décalage vers la gauche return reponse # On renvoie la nouvelle liste

Voilà. Nous sommes parvenus à implémenter nos listes sous forme interne de tableaux.

Voici le code final de notre implémentation du type abstrait LISTE en utilisant des tableaux et en fournissant l'interface de base d'accès uniquement à la tête. Notre interface possède les 5 fonctions de base plus une fonction optionnelle d'affichage globale de la liste.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
'''Implémentation de type abstrait Liste en utilisant des tableaux Liste désigne la structure de données que nous utilisons pour gérer les listes. Elt désigne la structure de données pouvant être un élément de nos listes. Description rapide de l'interface : ----------------------------------- 1 ::: nouvelleListe() -> Liste 2 ::: estVide(liste:Liste) -> bool 3 ::: lireTete(liste:Liste) -> Elt 4 ::: insererTete(x:Elt, liste:Liste) -> Liste 5 ::: supprimerTete(liste:Liste) -> Liste 6 ::: afficherListe(liste:Liste) -> str ''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tableau vide [] ''' return [] def estVide(lst) : '''Renvoie True si la liste est vide :: param lst(Liste) :: la liste à tester :: return (bool) :: True si liste peut être vu comme une liste vide ''' return lst == [] def lireTete(lst) : '''Renvoie la tête de la liste, sans toucher à la liste elle-même :: param lst(Liste) :: la liste dont on désire lire la tête :: return (Elt) :: la tête voulue, None si la tête est vide ''' if not estVide(lst) : return lst[0] def insererTete(x, lst) : '''Renvoie une nouvelle liste où x est la tête et liste la queue :: param x(Elt) :: un élément compatible avec votre liste qui devient la tête :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)+1)] # On crée une liste plus longue de 1 for index in range(len(lst)) : reponse[index+1] = lst[index] # Décalage vers la droite reponse[0] = x # On place la tête return reponse # On renvoie la nouvelle liste def supprimerTete(lst) : '''Renvoie une nouvelle liste où on a supprimé la tête de l'ancienne :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' if estVide(lst) : # la liste envoyée est [] return nouvelleListe() else : reponse = [0 for x in range(len(lst)-1)] # On crée une liste moins longue de 1 for index in range(1,len(lst)) : reponse[index-1] = lst[index] # Décalage vers la gauche return reponse # On renvoie la nouvelle liste def afficherListe(lst) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: return (str) :: un string représentant notre liste ''' return str(tuple(lst))

05° Mettre les fonctions en mémoire. Utiliser l'interface pour créer une liste, rajouter des têtes, observer la liste, supprimer la tête et observer à nouveau la liste.

L'utilisateur n'utilisant que les fonctions d'interface pourra-t-il se rendre compte de l'implémentation interne réalisée sur le type abstrait Liste ?

...CORRECTION...

>>> a = nouvelleListe() >>> afficherListe(a) '()' >>> a [] >>> a = insererTete(5, a) >>> afficherListe(a) '(5,)' >>> a [5] >>> a = insererTete(15, a) >>> afficherListe(a) '(15, 5)' >>> a [15, 5] >>> a = supprimerTete(a) >>> afficherListe(a) '(5,)' >>> a [5]

Comme on peut le voir sur les exemples, l'utilisateur ne peut utiliser normalement que la fonction afficherListe et ne voit donc que la représentation de la liste comme une séquence ordonnée. Il ne peut donc pas savoir sous quelle forme elle est réellement implémentée. Sauf à demander directement l'accès à la variable, mais dans ce cas, il décide de passer au dessus de l'interface.

Nous avons réalisé l'interface basique ne gèrant que la tête. Passons à l'interface plus souple, bien pratique pour gérer véritablement des listes comme on le désire.

06° Compléter le code de la fonction lireElement dont on vous donne le prototype et la documentation.

On veut pouvoir accéder directement à la valeur d'un élément. Il faudra bien entendu utiliser la lecture directe du tableau dans le code interne : c'est l'avantage majeur d'un tableau : l'accès à coût constant aux éléments.

Prototype

1
def lireElement(lst:Liste, position:int) -> Elt :

Code à compléter

1 2 3 4 5 6 7 8 9
def lireElement(lst, position) : '''Renvoie la valeur stockée à la position voulue :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la valeur voulue ''' pass

...CORRECTION...

1 2 3 4 5 6 7 8 9
def lireElement(lst, position) : '''Renvoie la valeur stockée à la position voulue :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la valeur voulue ''' return lst[position]

Un peu plus dur : l'insertion. Un exemple d'insertion d'un élément valant 23 sur l'index 2 dans une liste stockée dans la variable a :

>>> insererElement(23, a, 2)
Principe de l'insertion dans une liste sur une implémentation tableau

07° Compléter le code de la fonction insererElement dont on vous donne le prototype et la documentation.

Demandez-vous ce qu'on ne doit pas bouger, ce qu'on doit insérer et ce qu'on doit déplacer.

vous pourrez vous inspirer du code de insererTete.

Prototype

1
def insererElement(x:Elt, lst:Liste, position:int) -> Liste :

Code à compléter

1 2 3 4 5 6 7 8 9 10
def insererElement(x, lst, position) : '''Renvoie une Liste en insérant x à la position position. :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' pass

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def insererElement(x, lst, position) : '''Renvoie une Liste en insérant x à la position position. :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)+1)] # On crée une liste plus longue de 1 for index in range(position) : reponse[index] = lst[index] # copie à l'identique reponse[position] = x # On place l'élément for index in range(position, len(lst)) : reponse[index+1] = lst[index] # Décalage vers la droite return reponse # On renvoie la nouvelle liste

Dernière fonctionnalité : la suppression.

Principe de la suppression dans une liste sur une implémentation tableau

08° Compléter le code de la fonction supprimerPosition dont on vous donne le prototype et la documentation.

Attention, pensez d'abord à gérer le cas de la liste vide (on renvoie alors une liste vide) avant de commencer à déplacer les éléments.

Prototype

1
def supprimerPosition(lst:Liste, position:int) -> Liste :

Code à compléter

1 2 3 4 5 6 7 8 9
def supprimerPosition(lst, position) : '''Renvoie une nouvelle liste où on a supprimé l'élément situé à la position fournie :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' pass

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def supprimerPosition(lst, position) : '''Renvoie une nouvelle liste où on a supprimé l'élément situé à la position fournie :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)-1)] # On crée une liste plus courte de 1 for index in range(position) : reponse[index] = lst[index] # copie à l'identique for index in range(position, len(reponse)) : reponse[index] = lst[index+1] # Décalage vers la gauche return reponse # On renvoie la nouvelle liste

09° Estimer les coûts (complexité) dans le pire des cas de nos quatre fonctions lecture-modification-insertion-suppression en considérant que l'implémentation Python du type natif list correspond à un tableau dynamique.

...CORRECTION...

Lecture : coût constant (on va directement en mémoire, sans passer par la lecture des autres valeurs)

Insertion : coût linéaire, il faut déplacer l'intégralité des données une par une.

Suppression : coût linéaire pour les mêmes raisons.

Coût de l'implémentation en tableau

On notera donc que dans le pire des cas :

  • La lecture d'une valeur est à coût constant (Θ(1))
  • L'insertion et la suppression est à coût linéaire (Θ(n))
Rappel : coût de l'implémentation en tuple (tête, queue)

On notera donc que dans le pire des cas :

  • La lecture est à coût linéaire (Θ(n))
  • L'insertion et la suppression est à coût linéaire (Θ(n))

Notre nouvelle implémentation en tableau est donc strictement identique pour l'utilisateur vis à vis de l'interface (il ne peut pas savoir laquelle il utilise). Par contre, l'implémentation tableau aura de meilleurs performances en lecture.

La totalité du code pour mémoire :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
'''Implémentation de type abstrait Liste en utilisant des tableaux Liste désigne la structure de données que nous utilisons pour gérer les listes. Elt désigne la structure de données pouvant être un élément de nos listes. Description rapide de l'interface : ----------------------------------- 1 ::: nouvelleListe() -> Liste 2 ::: estVide(liste:Liste) -> bool 3 ::: lireElement(liste:Liste, index:int) -> Elt 4 ::: insererElement(x:Elt, liste:Liste, position:int) -> Liste 5 ::: supprimerPosition(liste:Liste, position:int) -> Liste 6 ::: afficherListe(liste:Liste) -> str ''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tableau vide [] ''' return [] def estVide(lst) : '''Renvoie True si la liste est vide :: return (bool) :: True si liste peut être vu comme une liste vide ''' return lst == [] def lireElement(lst, index) : '''Renvoie la valeur stockée à l'index voulu :: param lst(Liste) :: une liste :: param index(int) :: une valeur d'index valide pour cette liste :: return (Elt) :: la valeur située à cette index ''' return lst[index] def insererElement(x, lst, position) : '''Renvoie une Liste en insérant x à la position position. :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)+1)] # On crée une liste plus longue de 1 for index in range(position) : reponse[index] = lst[index] # copie à l'identique reponse[position] = x # On place l'élément for index in range(position, len(lst)) : reponse[index+1] = lst[index] # Décalage vers la droite return reponse # On renvoie la nouvelle liste def supprimerPosition(lst, position) : '''Renvoie une nouvelle liste où on a supprimé l'élément situé à la position fournie :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [0 for x in range(len(lst)-1)] # On crée une liste plus courte de 1 for index in range(position) : reponse[index] = lst[index] # copie à l'identique for index in range(position, len(reponse)) : reponse[index] = lst[index+1] # Décalage vers la gauche return reponse # On renvoie la nouvelle liste def afficherListe(lst) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: return (str) :: un string représentant notre liste ''' return str(tuple(lst))

2 - Implémentation en utilisant directement list de Python

Si le type natif list se nomme ainsi, c'est bien qu'il permet l'implémentation de Liste. Par contre, en interne, il s'agit d'une tableau dynamique qui possède plus de fonctions d'interface que celle du type abstrait TABLEAU DYNAMIQUE. La structure de données nommée list est donc un savant mélange de fonctionnalités des tableaux et des listes.

Voici comment on pourrait créer notre interface en utilsant les Pythonneries associées à ce type natif.

Insertion de nouveaux éléments via les outils présents dans Python

Vous connaissez déja la méthode append qui permet de rajouter un nouvel élément à la fin de nos objets de type natif list-Python.

Attention, append modifie la variable sur laquelle on agit MAIS elle ne renvoie rien : il faudra donc l'utiliser sur une copie du tableau et renvoyer cette copie ensuite.

Votre fonction devra toujours renvoyer la copie modifiée.

Mais il existe également une méthode nommée insert qui permet de faire la même chose MAIS en choississant la position de l'insertion.

1 2 3 4 5 6 7 8 9 10 11 12
def insererElement(x, lst, position) : '''Renvoie une Liste en insérant x à la position position. :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [element for element in lst] reponse.insert(position, x) return reponse
ERREUR COURANTE

Ne faites donc jamais ceci : insert étant une fonction-procédure, comme append, vous allez renvoyer ... None.

1 2
reponse = [element for element in lst] return reponse.insert(position, x)

Suppression d'un élément via les outils présents dans Python

De la même façon, il existe une méthode nommée pop qui permet d'extraire un élément (la méthode renvoie l'élément) et modifie le tableau en place.

On peut donc l'utiliser pour juste modifier le tableau, sans mémoriser la valeur extraite.

1 2 3 4 5 6 7 8 9 10 11
def supprimerPosition(lst, position) : '''Renvoie une nouvelle liste où on a supprimé l'élément situé à la position fournie :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [element for element in lst] reponse.pop(position) return reponse
Erreur courante

Nous aurions pu faire cela, même si on ne désire pas stocker la valeur extraite :

1 2 3
reponse = [element for element in lst] valeur_extraite = reponse.pop(position) return reponse

Mais, il ne faut pas faire ceci :

1 2
reponse = [element for element in lst] return reponse.pop(position)

Avec ce code, vous allez renvoyer l'élément supprimé et pas le nouveau tableau !

Au final, nous allons obtenir le même effet pour l'utilisateur, si ce n'est que le code utilise les fonctionnalités de Python et que nous ne connaissons pas les coûts de ces fonctions. A priori, elles sont performantes mais il faudrait aller voir le code interne de Python pour le savoir.

On notera qu'il est pénible de devoir fournir la position lorsqu'on veut placer ou supprimer le dernier élément. Comment faire pour simplifier la démarche de l'utilisateur ? Utiliser des valeurs par défaut pour ce paramètre.

Index -1 avec Python

Le code ci-dessous profite d'une Pythonnerie que vous n'avez pas à connaître : un index de -1 est normalement impossible. En Python, il sera compris comme voulant dire : le dernier élément.

L'index -2 correspond donc à l'avant-dernier élément, ect ...

10° Placer cette nouvelle implémentation ci-dessous en mémoire. Utilisez alors les fonctions pour vous convaincre qu'un utilisateur ne peut pas savoir quel code interne implémente le type abstrait Liste.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
'''Implémentation 3 de type abstrait Liste en utilisant le type natif liste de Python Liste désigne la structure de données que nous utilisons pour gérer les listes. Elt désigne la structure de données pouvant être un élément de nos listes. Description rapide de l'interface : ----------------------------------- 1 ::: nouvelleListe() -> Liste 2 ::: estVide(liste:Liste) -> bool 3 ::: lireElement(liste:Liste, index:int) -> Elt 4 ::: insererElement(x:Elt, liste:Liste, position:int) -> Liste 5 ::: supprimerPosition(liste:Liste, position:int) -> Liste 6 ::: afficherListe(liste:Liste) -> str ''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tableau vide [] ''' return [] def estVide(lst) : '''Renvoie True si la liste est vide :: return (bool) :: True si liste peut être vu comme une liste vide ''' return lst == [] def lireElement(lst, index=-1) : '''Renvoie la valeur stockée à l'index voulu :: param lst(Liste) :: une liste :: param index(int) :: une valeur d'index valide pour cette liste :: return (Elt) :: la valeur située à cette index ''' return lst[index] def insererElement(x, lst, position=-1) : '''Renvoie une Liste en insérant x à la position position. :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [element for element in lst] reponse.insert(position, x) return reponse def supprimerPosition(lst, position=-1) : '''Renvoie une nouvelle liste où on a supprimé l'élément situé à la position fournie :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' reponse = [element for element in lst] reponse.pop(position) return reponse def afficherListe(lst) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: return (str) :: un string représentant notre liste ''' return str(tuple(lst))

3 - FAQ

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

Oui. Petit rappel bientôt.

Nous venons donc de voir clairement qu'un utilisateur ne peut pas savoir comment est implémenter un type de données dont on lui fournit juste l'interface.

Par contre, chaque implémentation va avoir des avantages et des défauts.

  • Version 1 Tuple (tête, queue) : bien si on désire souvent manipuler les queues, mais coûts linéaires en lecture, insertion et suppression.
  • Version 2 tableaux : bien si on a plus souvent des accès en lecture (coût constant) qu'en insertion ou suppression (coût linéaire).
  • Version 3 list Python : comme au dessus, seul le code interne change. Les méthodes Python sont certainement optimisées par rapport à ce qu'on a créé sur la version 2.

La fois prochaine, nous verrons une dernière implémentation du type abstrait LISTE : la liste chaînée. L'avantage ? Un temps constant en insertion ou suppression. Par contre, la lecture a un coût linéaire...

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