Liste chainée simple

Une liste chaînée d’entiers est une structure de donnée représentant des suites d’entiers en faisant pointer chaque élément vers le suivant. On va utiliser la structure de pointeurs des listes pour les définir.

Récursivement, on a la définition suivante:

• La liste vide est une liste chaînée
• Pour L une liste chaînée et v un entier, alors [v, L] est une liste chaînée.

Par exemple, L = [42, [20, [3, [10, []]]]] est la liste représentant la suite 42, 20, 3, 10.

Pour toutes les fonctions suivantes, indiquez la complexité.

Length

Écrire une fonction length qui prend en argument une liste chaînée et qui retourne sa longueur.

Par exemple, length(L) retourne 4.

Get

Écrire une fonction get qui prend une liste chaînée et un entier \(i\) et qui retourne le \(i^\text{ème}\) élément de la liste.

Par exemple, get(L, 2) retourne 3.

Extract

Écrire une fonction extract qui prend une liste chaînée \(L\) et un entier \(i\) et qui retourne la liste chaînée qui débute à l’indice \(i\).

Par exemple extract(L, 1) retourne la liste chaînée [20, [3, [10, []]]].

Attention, vous devez avoir id(L[1]) == extract(L, 1)

Prepend

Écrire une fonction prepend qui prend une liste chaînée et qui ajoute à sa gauche une valeur, sans recopier la liste initiale.

Par exemple, prepend(L, 220) à L on obtient la liste suivante: [220, [42, [20, [3, [10, []]]]].

Votre fonction doit aussi vérifier que id(L) == id(prepend(L, 220)[1]), pour pas qu’il y ait de copie.

Append

Écrire une fonction append qui prend une liste chaînée et qui ajoute à sa droite une valeur, sans recopier la liste initiale. Attention, c’est une fonction en place, elle ne retourne rien.

Par exemple, append(L, 220) à L on obtient la liste suivante: [42, [20, [3, [10, [220, []]]]].

Votre fonction doit aussi vérifier que

i = id(L)
append(L, 220)
print(i == id(L))

Traceback (most recent call last):
  File "/home/cha/conf_files/utils/check_py_md", line 63, in repl
    exec(code, env)
  File "<string>", line 1, in <module>
NameError: name 'L' is not defined

Pop

Écrire une fonction pop qui prend une liste chaînée et un entier \(i\) et qui: - supprime de la liste l’élément à l’indice \(i\) de la liste - retourne sa valeur

Extend

Écrire une fonction extend qui prend deux listes chaînées \(L\) et \(K\) et ajoute \(K\) à la fin de \(L\). Attention, c’est une fonction en place, elle ne retourne rien.

Par exemple extend(L, [12, [13, []]]) retourne [42, [20, [3, [10, [12, [13, []]]]]]].

Sort

Implémenter un tri en place de votre choix pour les listes chaînées.

Une liste doublement chaînée circulaire (Difficile)

Dans une liste doublement chaînée circulaire, on a les propriétés suivantes:

• Chaque élément pointe vers l’élément suivant et l’élément précédent.
• L’élément précédant le premier élément de la liste est le dernier élément de la liste.
• L’élément suivant le dernier élément de la liste est le premier élément de la liste.

On définit les listes doublement chaînées en Python de la manière suivante:

Chaque élément de la liste est une list Python de taille 3 où: - Le premier élément est la valeur de la liste. - Le deuxième élément est la liste correspondant à l’élément suivant - Le troisième élément est la liste correspondant à l’élément précédent

Par exemple, la liste de taille 1 contenant la valeur 42 peut être définie ainsi:

L = [42]
L.append(L)
L.append(L)

La liste de taille 2 contenant 42 et 43 peut être définie ainsi:

L = [42]
K = [43]
L.append(K)
L.append(K)
K.append(L)
K.append(L)

La liste de taille 3 contenant 42, 43 et 44:

L = [42]
K = [43]
T = [44]
L.append(K)
K.append(T)
T.append(L)
L.append(T)
T.append(K)
K.append(L)

Refaire toutes les fonctions précédentes pour les listes doublement chaînées circulaires.