Structure de liste

03-04-2023

Objectifs

  • connaître la structure de données liste

  • une première structure de données récursive

  • listes non mutables ou mutables

  • savoir en donner une implantation

  • savoir l’utiliser

Motivation

Structure de données importante en informatique :

  • les listes sont partout

Remarque

Les listes existent déjà dans Python. Alors pourquoi les étudier et en donner des implantations ?

Voici quelques éléments de réponse :

  1. Les listes en Python permettent un accès direct (du moins en apparence, car il faudrait voir ce qu’il en est réellement) à leurs éléments à l’aide d’indices. Ce qui fait que les listes de Python peuvent être utilisées comme ce que dans d’autres langages de programmation on appelle tableau (ou array).

    Les tableaux sont des structures de données statiques, c’est-à-dire dont l’occupation mémoire est fixé une fois pour toute. Un tableau à \(n\) éléments est une zone mémoire de taille \(n\times t\) octets consécutifs, \(t\) étant la taille (en octets) d’un élément de chacun des éléments du tableau. De cette façon si on connaît l’adresse en mémoire \(adr\) du premier élément du tableau, celui d’indice 0, alors l’élément d’indice \(i\) se trouve à l’adresse \(adr + i\times t\). C’est ce simple calcul qui explique la facilité d’accès à n’importe quel élément d’un tableau.

  2. Les listes ne sont a priori pas des structures de données statiques, mais plutôt des structures de données dynamiques. Rien ne détermine a priori le nombre d’éléments que peut contenir une liste.

    Il est intéressant de comprendre comment on peut gérer le caractère dynamique d’une structure de données.

  3. Vous êtes là pour apprendre !

Qu’est ce qu’une liste ?

Nous savons tous intuitivement ce qu’est une liste. Une liste est une collection finie d’éléments qui se suivent. C’est donc une structure de données séquentielle ou linéaire.

Une liste peut contenir un nombre quelconque d’éléments y compris nul (la liste vide).

Nous allons essayer de dégager une définition plus formalisée de ce qu’est une liste afin d’en dégager les opérations primitives et une structure essentielle qui nous permettra d’en donner des implantations.

Prenons une liste comme par exemple \(\ell_1 = [3, 1, 4]\). C’est une liste à trois éléments (ou de longueur trois) dont le premier est \(3\), le deuxième \(1\), et le dernier \(4\).

Une façon de redécrire cette liste consiste à dire que

  • la liste \(\ell_1\) possède un premier élément \(3\) qu’on nommera élément de tête,

  • et que vient après cet élément de tête la liste \(\ell_2 = [1, 4]\) des éléments qui suivent, liste qu’on nommera reste.

Ce qu’on vient de dire de la liste \(\ell_1\) peut être répété pour la liste \(\ell_2\) qui est donc constituée :

  • d’un élément de tête : \(1\),

  • et d’un reste : \(\ell_3 = [4]\).

À nouveau on peut répeter le même discours pour la liste \(\ell_3\) qui est donc constituée :

  • d’un élément de tête : \(4\),

  • et d’un reste : \(\ell_4 = []\).

La liste \(\ell_4\) étant vide, elle ne possède pas d’élement de tête, et ne peut donc pas être décomposée comme nous venons de le faire à trois reprises.

Si on convient d’utiliser la notation \((x,\ell)\) pour désigner le couple constitué de l’élément \(x\) de tête, et du reste \(\ell\) d’une liste, on peut alors écrire :

\[\ell_1 = (3, (1, (4, [])))\]

On conçoit aisément que ce qui vient d’être fait pour notre exemple de liste \(\ell_1\) peut être reproduit pour n’importe quelle liste.

On peut conclure cette approche en donnant une définition abstraite et formelle des listes d’éléments appartenant tous à un ensemble \(E\).

Définition

Une liste d’éléments d’un ensemble \(E\) est

  • soit la liste vide

  • soit un couple \((x,\ell)\) constitué d’un élément \(x\in E\) et d’une liste \(\ell\) d’éléments de \(E\).

Il ressort de cette définition que les listes peuvent être vues comme des structures de données récursives.

Opérations primitives sur les listes (non mutables)

En nous appuyant sur la définition formelle qui vient d’être établie, nous sommes en mesure de dégager les opérations primitives qui suivent.

Constructeur

D’après la définition, une liste est

  • soit la liste vide,

  • soit un couple constitué de l’élément de tête suivi de la liste des éléments qui suivent.

Le constructeur de liste doit donc permettre de produire une liste vide et pour cela aucun argument n’est nécessaire, soit produire une liste à partir de deux arguments.

class aplst.ApLst(*args)
Paramètres

args (tuple) –

Build

a new empty list if args is empty, or a list whose head is first element of args, and tail list is second element of args.

UC

len(args) in {0, 2} and if len(args) == 2, args[1] must be a ApLst

Raise

ApLstError if UC is not satisfied

>>> list = ApLst()
>>> list.is_empty()
True
>>> list.head()
Traceback (most recent call last):
  ...
ApLstError: head: empty list
>>> list2 = ApLst(1, list)
>>> list2.is_empty()
False
>>> list2.head()
1
>>> list2.tail().is_empty()
True
>>> print(ApLst(2, list2))
[2, 1]
>>> print(list2)
[1]
>>> len(ApLst(1, ApLst(2, ApLst(3, ApLst()))))
3

Sélecteurs

Les listes non vides possèdent une tête et un reste. Il nous faut les méthodes, appelées sélecteurs, pour accéder à ces deux composantes.

ApLst.head()
Renvoie

head element of self

Raise

ApLstError if self is empty

ApLst.tail()
Renvoie

tail list of self

Raise

ApLstError if self is empty

Prédicat

Un prédicat testant la vacuité d’une liste peut s’avérer nécessaire.

ApLst.is_empty()
Renvoie

  • True if self is empty

  • False otherwise

Type renvoyé

bool

UC

none

Remarque

Note

Voici quelques relations qu’on peut établir à partir de ces opérations primitives.

  • pour toute liste l et tout élément x, on a List(x, l).tail() == l et List(x, l).head() == x,

  • et pour toute liste non vide, on a List(l.head(), l.tail()) == l.

Exemples

Voici quelques exemples d’utilisation de ces opérations.

>>> l = List(3, List())
>>> l.head()
3
>>> l.is_empty()
False
>>> l.tail().is_empty()
True

Opérations primitives spécifiques aux listes mutables

Toutes les opérations primitives décrites ci-dessus permettent de travailler avec des listes non mutables, c’est-à-dire des listes dans lesquelles il est impossible

  • de changer la valeur d’un élément d’une liste,

  • et d’en changer la structure, en particulier sa longueur.

Les listes non mutables sont fréquentes dans les langages fonctionnels comme Haskell et OCaml.

Mais dans d’autres langages, les listes sont mutables. Par exemple en Python, on peut

  • changer la valeur d’un élément d’une liste : l[i] = x

  • changer l’ordre de tous les éléments : l.sort()

  • augmenter la longueur d’une liste : l.append(x)

  • diminuer la longueur d’une liste : l.pop() …

Si on veut des listes mutables, il nous faut des opérations primitives supplémentaires.

Implantation des listes

Pour trouver une implantation des listes, il suffit de s’en tenir à la définition récursive d’une liste : une liste est soit la liste vide, soit un couple constitué de la tête de la liste et du reste de la liste.

Nous allons vous fournir une classe List permettant de manipuler les listes. Vous ne connaissez pas encore les classes, mais vous en avez manipulées souvent (les entiers, les chaînes de caractères , les listes python, … sont des classes).

Il n’est pas nécessaire de savoir programmer une classes pour effectuer les exercices de TD et de TP, seulement de l’utiliser.

Nous allons quand même analyser certaines parties du code source de la classe.

Il semble assez naturel qu’un objet de classe List soit représenté par un attribut (privé) dont la valeur est

  • ̀`None`` pour la liste vide,

  • un couple ou un dictionnaire à deux champs pour une liste non vide.

Constructeurs

Nous choisissons un attribut __content dont la valeur est () (tuple vide) pour la liste vide, ou un couple (tuple à deux éléments) pour les listes non vides.

Prédicat

Le prédicat de test de vacuité d’une liste peut s’écrire très simplement même sans savoir comment une liste vide est implantée.

Sélecteurs

Les sélecteurs sont simples à écrire, mais il faut tenir compte du cas des listes vides par le biais d’un traitement de l’exception par exemple.

Exemples d’utilisation de ces opérations

Calcul de la longueur d’une liste

Voici une implantation possible d’une méthode donnant la longueur d’une liste.

>>> List().__len__()
0
>>> List(1, List(2, List(3, List()))).__len__()
3

Note

Remarque

Le calcul de la longueur effectué par la fonction ci-dessus nécessite un parcours complet de la liste. On pourrait envisager une implantation des listes avec un attribut contenant la longueur de la liste qui permettrait à la méthode __len__ d’avoir à parcourir l’intégralité de la liste.

Le nom de la méthode est encadré par deux blancs soulignés. Cela permet d’utiliser la fonction len de python avec nos listes.

Représentation sous forme d’une chaîne de caractères

>>> str(List())
'[]'
>>> print(List(1, List(2, List(3, List()))).__len__())
[1, 2, 3]