Listes chaînées

Frédéric Herbreteau, Bordeaux INP/LaBRI (frederic.herbreteau@bordeaux-inp.fr)

Liste chaînée

Définition: Une liste chaînée LinkedList est

soit la liste vide None

soit une cellule Cell(v, l) munie d’une valeur v et d’une liste chaînée l

Une liste est donc une chaîne de cellules éventuellement vide
Le type LinkedList est un type récursif
La valeur v de Cell(v, l) est souvent nommée la tête de liste (head hd)
La liste l de Cell(v, l) s’appelle la queue de liste (tail tl)

NB: Python fournit une implémentation de listes chaînées List

Définir et représenter des listes

Exercice 1

Définir les listes [], [1] et [1, 2, 3], et les représenter
Représenter les listes obtenues après chacune des opérations suivantes:

l1 = Cell(1, None)
l2 = Cell(2, l1)
l3 = Cell(3, l1)

Que pensez-vous des listes l1, l2 et l3 ainsi obtenues?

Calculer la longueur d’une liste

Exercice 2

Écrire une fonction qui calcule la longueur (le nombre de cellules) d’une liste chaînée:

def listLength(l: LinkedList) -> int:

Fournir une mise en oeuvre itérative et une mise en oeuvre récursive
Prouver la terminaison et la correction des deux mises en oeuvre
Évaluer la complexité en temps et en espace des deux mises en oeuvre.

Recherche d’un élément dans une liste

Exercice 3

Écrire une fonction qui indique si une valeur v appartient à une liste l

def listFind(l: LinkedList, v: int) -> bool:

Fournir une mise en oeuvre itérative et une mise en oeuvre récursive
Prouver la terminaison et la correction des deux mises en oeuvre
Évaluer la complexité en temps et en espace des deux mises en oeuvre.

Cloner une liste

Exercice 4

Écrire une fonction qui clone une liste chaînée l.

def cloneList(l: LinkedList) -> LinkedList:

Mettre en oeuvre la fonction cloneList de manière récursive
Prouver la terminaison et la correction de votre mise en oeuvre
Évaluer la complexité en temps et en espace de votre mise en oeuvre
Quelle difficulté rencontrez-vous pour une mise en oeuvre itérative?

Retirer une valeur d’une liste

Exercice 5

Écrire une fonction qui retire la valeur v d’une liste l.

def listRemove(l: LinkedList) -> LinkedList:

Fournir une mise en oeuvre récursive
Prouver la terminaison et la correction de votre mise en oeuvre
Évaluer la complexité en temps et en espace de votre mise en oeuvre.

Concaténer deux listes

Exercice 6

Écrire une fonction listConcat qui retourne la liste obtenue en concaténant la liste l2 à la liste l1.

def listConcat(l1: LinkedList, l2: LinkedList) -> LinkedList:

Fournir une mise en oeuvre itérative ou une mise en oeuvre récursive
Prouver la terminaison et la correction de votre mise en oeuvre
Évaluer la complexité en temps et en espace de votre mise en oeuvre.

Renverser une liste

Exercice 7

Écrire une fonction listReverse qui retourne la liste obtenue en renversant la liste l.

def listReverse(l: LinkedList) -> LinkedList:

Fournir une mise en oeuvre itérative ou une mise en oeuvre récursive
Prouver la terminaison et la correction de votre mise en oeuvre
Évaluer la complexité en temps et en espace de votre mise en oeuvre.

Tri fusion (merge sort)

Principe: pour trier une liste l

diviser l en deux parties égales l1 et l2 (à 1 élément près)
trier l1 et l2 (plus petits problèmes)
fusionner l1 et l2

def listMergeSort(l: LinkedList) -> LinkedList:

Exercice 8

Implémenter la fonction listMergeSort
Prouver sa terminaison, sa correction, et évaluer ses complexités temporelle et spatiale

Tri rapide (quick sort)

Principe: pour trier une liste l,

choisir un pivot p, par exemple le premier élément de l
diviser l en trois: lt les valeurs < p, eq les valeurs = p et gt les valeurs > p
trier lt et gt (plus petits problèmes)
fusionner lt, eq et gt

def listQuickSort(l: LinkedList) -> LinkedList:

Exercice 9

Implémenter listQuickSort, justifier sa terminaison et sa correction.
Calculer sa complexité en temps. Comment l’améliorer avec un autre type de liste?

Exercices supplémentaires

Exercice 10

Écrire une fonction qui affiche les éléments d’une liste. On utilisera la fonction print pour afficher la valeur (ex: print(v))

PRECOND: True
POSTCOND: toutes les valeurs de l ont été affichées

def listPrint(l: LinkedList) -> None:

prouver la terminaison et la correction de listPrint
évaluer la complexité temporelle de listPrint en supposant que la fonction print est de complexité $\Omicron(1)$

Exercice 3

Écrire une fonction qui calcule la somme des valeurs d’une liste chaînée:

def listSum(l: LinkedList) -> int:

Fournir une mise en oeuvre itérative, une mise en oeuvre récursive et une mise en oeuvre récursive terminale
Prouver la terminaison et la correction des trois mises en oeuvre
Évaluer la complexité en temps et en espace des trois mises en oeuvre.

Exercice 11

Écrire une fonction qui vérifie si deux listes l1 et l2 sont égales: mêmes éléments, en même nombre et dans le même ordre.

PRECOND: True
POSTCOND: retourne True si l1 et l2 sont la même séquence de valeur, False sinon

def listEqual(l1: LinkedList, l2: LinkedList) -> bool:

prouver la terminaison et la correction de listEqual
évaluer les complexités temporelle et spatiale de listEqual

Exercice 12

Écrire une fonction récursive qui insère une valeur dans une liste triée.

PRECOND: l est une liste triée
POSTCOND: la liste retournée est triée et elle contient les éléments que l et v

def listInsertSorted(l: LinkedList, v: int) -> LinkedList:

prouver la terminaison et la correction de listInsertSorted
évaluer les complexités temporelle et spatiale de listInsertSorted

Exercice 13

Écrire une fonction qui créé une liste chaînée de longueur n contenant des valeurs aléatoires entre 0 et n. Utiliser la fonction randint(l, h) du module random pour générer un entier pseudo-aléatoire entre l et h inclus.

def newRandomList(n: int) -> LinkedList:

Fournir une mise en oeuvre itérative ou une mise en oeuvre récursive
Prouver la terminaison et la correction de votre mise en oeuvre
Évaluer la complexité en temps et en espace de votre mise en oeuvre. On supposera que randint s’exécute en temps et espace $\Omicron(1)$