Plusieurs manières de faire pour créer un tableau de taille éléments :
class Liste:
def __init__(self, taille: int):
self.liste = [None]*taille
self.taille = taille
On peut également utiliser une liste par compréhension :
class Liste:
def __init__(self, taille: int):
self.liste = [None for i in range(taille)]
self.taille = taille
class Liste:
def __init__(self, taille: int):
self.liste = [None]*taille
self.taille = taille
def get(self, indice):
return self.liste[indice]
def set(self, indice, valeur):
self.liste[indice] = valeur
On ne gère pas les cas où les indices sont en dehors du tableau, puisque Python signalera dans ce cas une erreur...ce qui, encore une fois, ne sera pas le cas en C/C++ !
Si on veut vraiment être aussi proche que possible de ces langages, on peut rajouter des assertions :
...
def get(self, indice):
assert indice >=0 and indice < len(self.liste), "Index out of range !"
return self.liste[indice]
def set(self, indice, valeur):
assert indice >=0 and indice < len(self.liste), "Index out of range !"
self.liste[indice] = valeur
Comme on doit créer une nouvelle liste d'un élément de plus que précédemment, il est nécessaire de stocker dans un attribut la taille de la liste :
class Liste:
def __init__(self, taille: int):
self.taille = taille
self.liste = [None]*self.taille
def append(self, valeur):
#dans le cas ou la liste n'est pas encore pleine
if self.get(self.taille-1)==None:
i=self.taille-1
#on détermine l'indice du dernier None dans le tableau python (en partant de la fin)
while(self.get(i)==None):
i=i-1
self.set(i+1,valeur)
#dans le cas ou la liste est pleine
else:
nv_liste = Liste(self.taille+1)
for i in range(self.taille) :
nv_liste.set(i,self.get(i))
nv_liste.set(self.taille,valeur)
# la liste est la nouvelle liste
self.taille = nv_liste.taille
self.liste = nv_liste.liste
Complexité : il est nécessaire de faire n opérations de recopies élémentaires pour chaque élément de la liste → complexité en O(n)
class Liste:
def __init__(self, taille: int):
self.taille = taille
self.liste = [None]*self.taille
def insert(self, indice, valeur):
self.taille += 1
nv_liste = liste(self.taille) # création d'une nouvelle liste d'une unité de plus en taille
for i in range(0, indice): # recopie de la première partie de la liste ( de 0 à indice-1 )
nv_liste.get(i) = self.get(i)
nv_liste[indice] = valeur # on intercale le nouvel élément ( indice )
for i in range(indice+1, self.taille): # recopie de la deuxième partie de la liste ( de indice à self.taille-1 )
nv_liste.get(i) = self.get(i-1)
self.liste = nv_liste # la liste est la nouvelle liste
Complexité : idem ( O(n) ).
class Liste:
def __init__(self, taille: int):
self.taille = taille
self.liste = [None]*self.taille
def append(self, valeur):
# dans le cas ou la liste n'est pas encore pleine
if self.get(self.taille-1) == None:
i = self.taille-1
# on détermine l'indice du dernier None dans le tableau python (en partant de la fin)
while (self.get(i) == None):
i = i-1
self.set(i+1,valeur)
# dans le cas ou la liste est pleine
else:
nv_liste = Liste(self.taille+1)
for i in range(self.taille) :
nv_liste.set(i,self.get(i))
nv_liste.set(self.taille,valeur)
# la liste est la nouvelle liste
self.taille = nv_liste.taille
self.liste = nv_liste.liste
def insert(self, indice, valeur):
self.taille += 1
nv_liste = liste(self.taille) # création d'une nouvelle liste d'une unité de plus en taille
for i in range(0, indice): # recopie de la première partie de la liste ( de 0 à indice-1 )
nv_liste.get(i) = self.get(i)
nv_liste[indice] = valeur # on intercale le nouvel élément ( indice )
for i in range(indice+1, self.taille): # recopie de la deuxième partie de la liste ( de indice à self.taille-1 )
nv_liste.get(i) = self.get(i-1)
self.liste = nv_liste
On ne passe aucun argument au constructeur de la classe Liste :
l = Liste()
Attention, plus délicat : il faut passer comme argument au constructeur de la liste la structure entière des maillons de cette dernière :
l = Liste(Maillon(2, Maillon(5, Maillon(68, Maillon(3)))))
Pour chaque maillon, il faut bien passer la valeur de l'élément stocké + la suite des maillons, qui se retrouvent ainsi "imbriqués" les uns dans les autres : c'est le concept !
Par contre, pas la peine de préciser None pour le dernier maillon : il est automatiquement rajouté par le constructeur des objets Maillon.
Ce doit bien sûr être une méthode de la classe Liste. Il suffit de tester si la tête de la liste est None ou pas :
class Maillon:
def __init__(self, valeur, suivant = None):
self.valeur = valeur
self.suivant = suivant
class Liste:
def __init__(self, tete = None):
self.tete = tete
def is_empty(self):
return self.tete is None
l1 = Liste()
l2 = Liste(Maillon(2, Maillon(5, Maillon(68, Maillon(3)))))
print(l1.is_empty()) # True
print(l2.is_empty()) # False
On utilise une manière particulière pour tester si l'objet self.tete est None; on aurait pu tout aussi bien écrire :
...
return self.tete == None
Il existe une très subtile différence entre ces deux écritures; celle utilisée ici l'est principalement parce qu'elle est beaucoup plus proche du langage naturel !
def insert_first(self, elt):
if self.is_empty(): # si la liste est vide,
self.tete = Maillon(elt) # on crée simplement son maillon de tête.
else:
maillon = Maillon(elt) # création d'un nouveau maillon
maillon.suivant = self.tete # le nouveau maillon pointe vers la tête
self.tete = maillon # on remplace la tête par le nouveau maillon ( l'ancienne tête est donc devenue le deuxième maillon de la liste )
On peut simplifier ces 3 étapes en une seule :
def insert_first(self, elt):
if self.is_empty():
self.tete = Maillon(elt)
else:
self.tete = Maillon(elt, self.tete)
Voire même, ne pas faire de test du tout pour savoir si la liste est vide ou pas :
def insert_first(self, elt):
self.tete = Maillon(elt, self.tete)
En effet, si la liste est vide, self.tete est None, que l'on passe alors en argument au constructeur de la classe Maillon, mais ce n'est pas un problème...
Complexité : on ne fait qu'un nombre donné d'affectations ( 3 dans la première version ), donc en O(1), indépendant du nombre d'éléments dans la liste ( = en temps constant ).
def pop_first(self):
assert not self.is_empty(); "La liste est vide !" # renvoi d'erreur si la liste est déja vide !
t = self.tete.valeur # on stocke l'élément en tête pour pouvoir le renvoyer
self.tete = self.tete.suivant # on remplace simplement la tête par sa suite -> l'élément en tête disparaît !
return t # renvoi de l'élément supprimé
Complexité : là aussi, on ne fait qu'un nombre donné d'affectations, donc aussi en O(1).
On arrive en fin de liste lorsque le champ suivant du maillon courant est None.
Pour passer d'un maillon au suivant, il suffit de remplacer le maillon courant par son champ suivant, qui contient effectivement la référence vers le maillon suivant, donc la suite de la liste :
def len(self):
if self.is_empty(): # cas particulier de la liste vide
return 0
maillon = self.tete # référence vers la tête de la liste
n = 1 # nombre d'éléments initialisé à 1
while maillon.suivant is not None: # tant que l'on n'a pas atteint la fin de la liste...
n += 1 # ... on incrémente de 1 le nombre d'éléments
maillon = maillon.suivant # et on remplace le maillon par sa suite
return n # renvoi du nombre d'éléments
Complexité : on parcourt toute la liste, donc en O(n).
def __str__(self):
maillon = self.tete # référence vers la tête de la liste
if not self.is_empty():
t = str(maillon.valeur) + ' ' # nouvelle chaîne, initialisée avec le champ 'valeur' de la tête
while maillon.suivant is not None: # tant que l'on n'a pas atteint la fin de la liste...
maillon = maillon.suivant # ...on remplace le maillon en cours par son champ 'suivant', c'est à dire la suite de la liste; 'maillon' contient l'élément courant, donc en fin de boucle, le dernier de la liste
t += str(maillon.valeur) + ' ' # et on ajoute à la chaîne le champ 'valeur' de l'élément courant
else:
t = '[]' # chaîne renvoyée au cas où la liste est vide
return t # renvoi du résultat
Complexité : on parcourt toute la liste, donc en O(n).
On va utiliser le paramètre indice comme compteur, que l'on décrémente à chaque nouveau maillon : quand le compteur est arrivé à 0, on a alors atteint l'indice recherché :
def get(self, indice):
maillon = self.tete
while indice != 0: # tant que l'on n'a pas atteint l'indice recherché
maillon = maillon.suivant # on avance d'un maillon
if maillon == None: # si on est arrivés en fin de liste,
return "Index out of range !" # c'est que l'indice recherché est en dehors de la liste !
indice -= 1 # décrémentation de l'indice/du compteur
return maillon.valeur # arrivé à l'indice recherché, on renvoie la valeur du maillon courant
Complexité : on parcourt toute la liste ( au pire ), donc en O(n).
def append(self, elt):
if self.is_empty(): # si la liste est vide,
self.tete = Maillon(elt) # on crée simplement son maillon de tête.
else:
maillon = self.tete # référence vers la tête de la liste
while maillon.suivant is not None: # tant que l'on n'a pas atteint la fin de la liste...
maillon = maillon.suivant # ...on remplace le maillon par sa suite.
maillon.suivant = Maillon(elt) # création d'un nouveau maillon une fois la fin de liste atteinte
Complexité : on parcourt toute la liste, donc en O(n) même si l'insertion proprement dite se fait en O(1).
Pour lever ce problème, certaines implémentations, en plus de garder une référence vers la tête ( = premier maillon ) gardent également une référence vers le dernier maillon, ce qui fait qu'une insertion en fin de liste peut se faire dans ce cas en O(1).
On va se servir là aussi de l'indice de compteur pour "avancer" jusqu'à l'indice recherché, sauf qu'il faut ici "s'arrêter" une position avant pour insérer au "bon endroit" :
def insert(self, indice, elt):
if self.is_empty():
self.tete = Maillon(elt)
else:
maillon = self.tete # référence vers la tête
while indice != 1: # parcours de la liste jusqu'à la position indice-1 !
indice -= 1 # décrémentation du compteur
maillon = maillon.suivant # passage au maillon suivant
new = Maillon(elt) # création d'un nouveau maillon
new.suivant = maillon.suivant # la suite du nouveau maillon pointe vers la suite du maillon courant ( donc la suite de la liste )
maillon.suivant = new # le maillon courant pointe vers le nouveau maillon
On peut là aussi simplifier la création du maillon inséré :
def insert(self, indice, elt):
if self.is_empty():
self.tete = Maillon(elt)
else:
maillon = self.tete # référence vers la tête
while indice != 1: # parcours de la liste jusqu'à la position indice-1 !
indice -= 1 # décrémentation du compteur
maillon = maillon.suivant # passage au maillon suivant
maillon.suivant = Maillon(elt, maillon.suivant)
Complexité : on parcourt toute la liste ( au pire ), donc en O(n) même si l'insertion proprement dite se fait en O(1).
Dans la boucle de parcours de la liste, le maillon courant est désigné par maillon.suivant; le maillon suivant sera donc désigné par maillon.suivant.suivant ( = la "suite de la suite " ! )
L'avant-dernier maillon est donc atteint quand maillon.suivant.suivant est égal à None.
def pop_last(self):
assert not self.is_empty(); "La liste est vide !"
maillon = self.tete # référence vers la tête
if maillon.suivant is None: # si la liste n'a qu'un seul élément,
t = maillon.valeur # on stocke la valeur de cet élément,
self.tete = None # et on "vide" la liste.
else:
while maillon.suivant.suivant is not None: # parcours de la liste jusqu'à l'avant dernier élément
maillon = maillon.suivant # 'maillon' = élément courant, donc l'avant-dernier de la liste en fin de boucle
t = maillon.suivant.valeur # on stocke la valeur de l'élément qui va être supprimé
maillon.suivant = None # on remplace la suite de l'avant-dernier maillon par 'None' : le dernier élément disparaît !
return t
def pop(self, indice):
assert not self.is_empty(); "La liste est vide !"
maillon = self.tete # référence vers la tête
if maillon.suivant is None: # si la liste n'a qu'un seul élément,
t = maillon.valeur # on stocke la valeur de cet élément,
self.tete = None # et on "vide" la liste.
else:
while indice != 1: # parcours de la liste jusqu'à la position indice-1
indice -= 1
maillon = maillon.suivant
t = maillon.suivant.valeur
maillon.suivant = maillon.suivant.suivant # on remplace la suite du maillon courant par la "suite de sa suite" : l'élément en position n ( = la "suite" ) est donc supprimé
return t
class Maillon:
def __init__(self, valeur, suivant = None):
self.valeur = valeur
self.suivant = suivant
class ListeRec:
def __init__(self, tete = None):
self.tete = tete
def is_empty(self):
return self.tete is None
# Affichage de la liste
def _str(self, maillon):
if maillon.suivant is None:
return str(maillon.valeur)
return str(maillon.valeur) + ' ' + self._str(maillon.suivant)
def __str__(self):
if self.tete is None:
return '[]'
return self._str(self.tete)
# Insertion en tête ( identique à la version itérative )
def insert_first(self, elt):
self.tete = Maillon(elt, self.tete)
# Suppression en tête ( identique à la version itérative )
def pop_first(self):
assert not self.is_empty(); "La liste est vide !"
t = self.tete.valeur
self.tete = self.tete.suivant
return t
# Nombre d'éléments
def _len(self, maillon):
if maillon.suivant is None:
return 1
return 1 + self._len(maillon.suivant)
def len(self):
return self._len(self.tete)
# Accès à un élément
def _get(self, indice, maillon):
if maillon is None:
return "Index out of range !"
if indice == 0:
return maillon.valeur
return self._get(indice-1, maillon.suivant)
def get(self, indice):
return self._get(indice, self.tete)
# Insertion à la fin
def _append(self, maillon, elt):
if maillon.suivant is None:
maillon.suivant = Maillon(elt)
else:
self._append(maillon.suivant, elt)
def append(self, elt):
if self.is_empty():
self.tete = Maillon(elt)
else:
self._append(self.tete, elt)
# Insertion en un indice
def _insert(self, maillon, indice, elt):
if indice == 1:
maillon.suivant = Maillon(elt, maillon.suivant)
else:
self._insert(maillon.suivant, indice-1, elt)
def insert(self, indice, elt):
if self.is_empty():
self.tete = Maillon(elt)
else:
self._insert(self.tete, indice, elt)
# Suppression en fin
def _pop_last(self, maillon):
if maillon.suivant.suivant is None:
t = maillon.suivant.valeur
maillon.suivant = None
return t
return self._pop_last(maillon.suivant)
def pop_last(self):
assert not self.is_empty(); "La liste est vide !"
maillon = self.tete
if maillon.suivant is None:
t = maillon.valeur
self.tete = None
return t
else:
return self._pop_last(maillon)
# Suppression en un indice
def _pop(self, maillon, indice):
if indice == 1:
t = maillon.suivant.valeur
maillon.suivant = maillon.suivant.suivant
return t
return self._pop(maillon.suivant, indice-1)
def pop(self, indice):
assert not self.is_empty(); "La liste est vide !"
maillon = self.tete
if maillon.suivant is None:
t = maillon.valeur
self.tete = None
return t
else:
return self._pop(maillon, indice)
Le code complet des classes Liste et ListeRec est ici.
La correction de ces exercices est donnée sous forme itérative :
from liste_chainee import Liste, Maillon
def is_in(liste, valeur)->bool:
maillon = liste.tete
while maillon is not None: # il faut bien aller jusqu'"après" le dernier élément de la liste !
if maillon.valeur == valeur:
return True
maillon = maillon.suivant
return False
l = Liste(Maillon(2, Maillon(56, Maillon(6, Maillon(89, Maillon(78))))))
print(is_in(l, 87)) # False
print(is_in(l, 78)) # True
Une version "naïve" de cette fonction serait de simplement utiliser la méthode append() de la classe Liste écrite précédemment :
def python_2_linked(tab):
L = Liste() # liste vide
for elt in tab: # pour chaque élément du tableau
L.append(elt) # on l'insère en fin de liste
return L # renvoi de la liste
C'est d'ailleurs une méthode "standard" pour construire un tableau avec l'implémentation Python des listes ( tableaux dynamiques ).
Mais, dans le cas des listes chaînées :
Pour améliorer cette complexité, on peut parcourir le tableau ET la liste en même temps, et ramener ainsi la complexité à O(n) :
def python_2_linked(tab):
L = Liste() # liste vide
L.tete = Maillon(tab[0]) # premier élément du tableau -> tête de la liste
maillon = L.tete # référence vers la tête de la liste
for i in range(1, len(tab)): # pour chacun des éléments du tableau, en partant du DEUXIÈME
new = Maillon(tab[i]) # on créé un nouveau maillon dont la valeur est celle de l'élément du tableau
maillon.suivant = new # le maillon courant pointe vers le nouveau maillon
maillon = maillon.suivant # le maillon courant = le nouveau maillon ( donc le dernier de la liste )
return L # renvoi de la liste
Ceci illustre bien un des intérêts de la liste chaînée : une insertion à une position donnée ne coûte "rien"; ici on insère toujours à la fin, sans jamais revenir au début de la liste, c'est donc très efficace !
def occurrences(L, valeur):
maillon = L.tete # référence vers la tête de la liste
c = 0 # initialisation d'un compteur d'occurrence
while maillon.suivant is not None: # tant que l'on n'a pas atteint la fin de la chaîne
if maillon.valeur == valeur: # est-ce que la valeur du maillon courant est égale à la valeur recherchée ?
c = c + 1 # si oui, on incrémente le compteur
maillon = maillon.suivant # dans tous les cas, on passe au maillon suivant ( donc en dehors de la condition ! )
return c
def reverse(L):
L2 = Liste() # création d'une nouvelle liste
m = L.tete # référence vers le premier élément
L2.insert_first(m.valeur) # on insère cet élément en tête de la nouvelle liste
while m.suivant is not None: # puis on parcourt la liste à inverser
m = m.suivant
L2.insert_first(m.valeur) # et on insère EN TÊTE de la nouvelle liste les éléments de la première
return L2 # renvoi de la nouvelle liste
L'insertion en tête de liste chaînée est toujours en O(1), il est donc tout à fait légitime d'utiliser ici la méthode insert_first().
Très simple : on fait pointer le champ suivant du dernier maillon de la première liste vers la tête de la deuxième !
def concatenate(l1, l2):
maillon = l1.tete # référence vers la tête de la liste
while maillon.suivant is not None: # tant que l'on n'a pas atteint la fin de la chaîne
maillon = maillon.suivant # on passe au maillon suivant
maillon.suivant = l2.tete # et une fois le dernier maillon atteint, on fait pointer son champ 'suivant' vers la tête de la deuxième liste
return l1
On part du principe que, quelque soit son nombre d'éléments, la liste est déjà triée. Pour insérer un élément à sa bonne place, il faut donc parcourir la liste depuis sa tête, jusqu'à trouver un élément dont la valeur est supérieure à celle de l'élément à insérer; on insère alors l'élément AVANT cette position.
Pour cela, il faut donc, tester la valeur du maillon SUIVANT le maillon courant à chaque étape du parcours ( en commençant bien sûr par un test sur la valeur du maillon de tête ! )
def insert_sort(L, elt):
if L.is_empty(): # insertion dans une liste vide
L.tete = Maillon(elt) # on ne fait que créer une nouvelle tête
elif L.tete.valeur > elt: # insertion EN TETE de liste
new = Maillon(elt)
new.suivant = L.tete # dans ce cas, on insère l'élément AVANT cette tête
L.tete = new # l'élément inséré devient donc la nouvelle tête
else:
maillon = L.tete # dans les autres cas, on parcourt la liste...
while maillon.suivant is not None and maillon.suivant.valeur < elt : #...tant que l'on n' pas trouvé la "bonne" position d'insertion
maillon = maillon.suivant
if maillon is None: # si on est alors arrivé APRÈS le dernier maillon,
maillon.suivant = Maillon(elt) # alors on insère EN FIN de liste
else:
new = Maillon(elt) # sinon on insère à la position courante
new.suivant = maillon.suivant
maillon.suivant = new
Maintenant que l'on dispose d'une fonction insérant automatiquement un élément à sa "bonne" place, c'est un jeu d'enfant de créer une fonction de tri insertion.
Si vous ne voyez pas tout de suite pourquoi cela va être facile, peut-être faut-il revoir le principe du tri par insertion ? 😎
def tri_insertion(L):
L_triee = Liste() # nouvelle liste vide
maillon = L.tete # référence vers la tête de a liste à trier
insert_sort(L_triee, maillon.valeur) # on insère la tête de liste
while maillon.suivant is not None: # tant que l'on n'est pas arrivé à la fin de la liste à trier
maillon = maillon.suivant # on passe au maillon suivant
insert_sort(L_triee, maillon.valeur)# et on insère sa valeur à la bonne place dans la liste triée
return L_triee # renvoi de la liste triée
(defun produit(a b)
(* a b)
)
(write (produit 12 5)) # 60
Ici, les opérations logiques se font à l'aide de fonctions : elles doivent donc être en tête de liste dans une expression booléenne en Lisp :
(defun bissext(n)
(if (or (and (= (mod N 4) 0) (/= (mod N 100) 0)) (= (mod N 400) 0))
T
NIL
)
)
(write (bissext 2023)) ; NIL
(write (bissext 2016)) ; T
(defun somme(n)
(if (= N 0)
0
(+ N (somme (- N 1)))
)
)
(write (somme 10)) ; 55
(defun somme-list (L)
(if (null L)
0
(+ (first L) (somme-list (rest L)))
)
)
(setf l '(12 56 3 7 89 15))
(write (somme-list l)) ; 182
(defun len-list(L)
(if (null L)
0
(+ 1 (len-list (rest L)))
)
)
(setf l '(12 56 3 7 89 15))
(write (len-list l)) ; 6
(defun get-element(L indice)
(if (null L)
nil
(if (= indice 0)
(first L)
(get-element (rest L) (- indice 1))
)
)
)
(setf l '(12 56 3 7 89 15))
(write (get-element l 3)) ; 7