La liste

Une liste est une amélioration de la structure de tableau et sont les conteneurs de base du langage python. Tout comme les tableaux ce sont des objets pouvant contenir une succession d'autres objets auxquels on peut accéder par un index, mais on peut facilement ajouter/supprimer un nombre infini d'éléments en fin de liste.

Définition de la structure

structure Liste<Type>:
    attributs:
        longueur: entier ← 0
        T: [Type] de longueur longueur
    méthodes:
        fonction get(i: entier) → Type:  # valeur ← self[i] = valeur ← self.get(i)
            rendre T[i]
        fonction set(i: indice, valeur: Type) → ∅:  # self[clé] ← valeur = self.set(clé, valeur)
            T[i] ← valeur

        fonction append(x: Type)  → ∅:
            si longueur == T.longueur:
                T2 ← T

                longueur ← 0
                T ← un nouveau tableau de Type de longueur 2 * T2.longueur
                pour chaque y de T2:
                    append(y)

                append(x)
            sinon:
                T[longueur] ← x
                longueur ← longueur + 1
        fonction pop()  → Type:
            longueur ← longueur - 1
            rendre T[longueur]

        fonction insert(pos: entier, x: Type) → ∅:
            self.append(T[-1])
            pour chaque i allant de T.longueur - 1 à pos + 1 par pas de -1:
                T[i] ← T[i-1]
            T[pos] ← x
        fonction delete(pos: entier) → Type:
            r ← T[pos]
            pour chaque i de [pos, T.longueur - 1[:
                T[i] ← T[i+1]
            self.pop()

            return r

Ceci permet d'utiliser une liste comme un tableau, en ajoutant en plus 4 méthodes permettant de modifier sa longueur :

• append qui ajoute un élément en fin de liste
• insert qui insère un élément à une position quelconque de la liste en décalant les éléments après vers la droite
• pop qui rend le dernier élément de la liste et le supprime de la liste
• delete qui rend un élément à une position quelconque de la liste et le supprime de la liste en décalant les éléments après vers la gauche

Lorsque la longueur du tableau devient trop petite pour contenir toutes les valeurs, on crée un tableau de longueur double : on peut ajouter autant d'éléments à une liste que l'on souhaite ! Le code suivant est donc légitime :

l ← Liste<entier>
pour chaque i de [0, 2^42]:
    l.append(i)

pour chaque i de [0, 2^42[:
    l[i] ← l[i + 1]

Complexités

Examinons les complexités des méthodes de listes.

Création

A la création de la liste, on crée un tableau de longueur $K$, une constante ni trop petite, ni trop grande :

Ajout d'un élément

L'ajout d'un élément en fin de liste va être de complexité $\mathcal{O}(T.\mbox{\small longueur})$ dans le pire des cas puisqu'il faut créer un nouveau tableau puis tout recopier. Notez bien que l'on ne peut pas faire mieux puisqu'il est impossible de contrôler l'endroit où l'on crée un nouveau tableau (on ne peut pas le coller à l'ancien tableau).

Cependant, on va y revenir plus tard, si l'on vient de créer un nouveau tableau $T$, il ne sera qu'à moitié plein : les $T.\mbox{\small longueur} / 2$ prochains ajout d'éléments se feront en $\mathcal{O}(1)$ opérations !

Si l'on insère un élément au milieu de la liste, on commence par faire l'algorithme précédent pour ajouter une case au tableau, puis on décale d'une case vers la droite les éléments à partir du $i$ème et enfin on affecte le nouvel élément à sa place. Comme il faut toujours déplacer des éléments :

Suppression d'un élément

Pour supprimer le dernier élément d'une liste on n'a qu'une opération à faire :

Si l'on supprime un élément au milieu de la liste, on commence par décaler d'une case vers la droite les éléments à partir du i+1 ème et enfin on fait $n=n-1$ :

Complexité d'ajout de $N$ éléments à la fin de la structure

Ajouter un élément à la fin de la structure peut très mal tomber : cela peut être juste au moment où l'on doit doubler la taille de la structure. C'est donc de complexité $\mathcal{O}(n)$ opérations s'il y avait $n$ élément dans la liste au moment de l'ajout... Mais ensuite, les $n-1$ suivants ajout vont forcément bien se passer et auront tous une complexité de $\mathcal{O}(1)$ opérations.

On a le résultat suivant :

On appelle ce genre de raisonnement analyse en complexité amortie et sera étudié un peu plus tard. C'est très utile lorsque la même opération (ici l'ajout d'un élément en fin de liste) peut prendre des complexité très différentes, mais pas de façon indépendante.

La structure de liste est un cas simple où la complexité amortie est très utile car elle permet de mieux estimer la complexité : lorsque l'on ajoute $n$ fois un élément, cette opération n'est coûteuse qu'un petit nombre de fois :

Bilan

La complexité des opérations de la liste commune avec un tableau (lecture écriture à index fixé) est de même complexité et on peut ajouter/supprimer des éléments se fait en $\mathcal{O}(1)$ en amorti.

Améliorations possibles

Gérer la suppression

Pour ne pas gâcher de la place, une amélioration courante des listes est de réduire la longueur du tableau si après la suppression du dernier élément de la liste, sa longueur $m$ est deux fois plus grande que le nombre $n$ d'éléments stockés.

Même si l'ajout en fin de liste et la suppression en fin de liste ont des complexités variables, ceci ne change cependant pas la complexité amortie (même si la preuve est autrement plus difficile à démontrer) de l'utilisation d'une liste :

La plupart des implémentations des listes ont cette implémentation, ceci en fait une structure idéale pour stocker des objets.

De combien augmenter la longueur ?

Doit-on augmenter la longueur du tableau de 2 ? De 1.5 ? D'autre chose ? La réponse à cette question est bien plus délicate qu'on ne le pense et dépend fortement de l'usage qu'on va avoir des listes. Regardez la vidéo ci-dessous pour vous en convaincre :

Utilisation

L'intérêt d'une liste par rapport à un tableau est que l'on peut modifier sa longueur en ajoutant et supprimant des éléments.

Si l'ajout et la suppression d'un élément en fin de liste est de complexité $\mathcal{O}(1)$, ce n'est pas garantie si on doit ajouter/supprimer des éléments en milieu de liste.

Nous allons voir ici différentes stratégies selon que l'ordre des éléments stockés nous intéresse ou non. Notez que l'ajoute d'un élément en milieu de liste se fait de la même manière.

algorithme suppression_indice(L: Liste<T>, i: indice) → ∅:
    pour chaque j de [i + 1, L.longueur[:
        L[j-1] ← L[j]
    L.pop()

Si l'on ne se préoccupe pas de l'ordre dans la liste, on peut très facilement supprimer un élément in place :

algorithme suppression_indice(L: Liste<T>, i: indice) → ∅:
    L[i], L[-1] ← L[-1], L[i]
    L.pop()

On veut maintenant supprimer tous les éléments de la liste égaux à une valeur donnée :

algorithme suppression_indice(L: Liste<T>, v: T) → ∅:
    j ← 0
    i ← 0
    tant que i + j < L.longueur:
        L[i] ← L[i + j]
        si L[i] == v:
            j ← j + 1
        sinon:
            i ← i + 1
            
    répéter j fois:
        L.pop()