Voilà un bon article qui fait l’introduction à ce qu’on nomme les listes chaînées. Par exemple, si nous prenons PHP, il est aisé de faire un tableau, de lui ajouter/supprimer/modifer des éléments, néanmoins, ce sympathique type est bien plus complexe en C. Si vous avez tenter de faire du C, l’une des règles élémentaires du C est de définir la taille d’un tableau directement pendant l’initialisation et sa taille reste fixe (d’ailleurs, on peut encore voir dans certains code la taille d’un tableau définie dans une macro #define ce qui accentue la caractéristique de constante). Mais en sachant que le PHP et fait à partir du langage C, d’où nous vient ce type array() dans PHP dont la taille peut être variable ? Ce n’est pas de la magie mais de la logique et c’est ce qu’on appelle les listes chaînées (l’implémentation de Python en C utilise aussi la notion de liste chaînées).
Une liste chaînée peut ce définir comme ceci: Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d’éléments de même type. C’est un peu lourd mais le concept est là, il faut toujours ce positionner sur la notion de gestion de la mémoire qui est omniprésente en C. La notion de liste chaînée s’expliquer par plusieurs valeurs auxquelles on leurs associe un pointeur. Ce pointeur ne va pas pointer dans le vide mais sur la prochaine valeur de la liste, c’est ainsi qu’on peut créer une liste d’ordonnée:
[A] -> [B] -> [C] -> ... -> [H]
C’est là où intervient le mot « chaînée » car en effet, ce sont les pointeurs qui représentent les chaînes de notre liste. Mais pourquoi nous ne pouvons pas tout simplement appliquer cette logique pour les tableaux en C. Quant il s’agit d’allouer la mémoire, on vous retourne l’emplacement où vous pouvez mettre votre valeur. Néanmoins, cette emplacement n’est pas déterminer par le développeur. Ainsi, quant il s’agit d’allouer la mémoire pour un tableau, on vous donne un bloc (qui peut contenir 10 valeurs par exemple). La particularité de ce bloc, c’est qu’il est ordonné et continu mais de taille fixe dans la mémoire, c’est à dire que si on vous retourne la case 20154, la prochaine valeur de votre tableau sera dans la case 20155 et ainsi de suite. Néanmoins, il ce pose un problème car après votre tableau, il peut y avoir d’autres valeurs de d’autres programmes d’où le fait qu’il nous est impossible en C d’ajouter une nouvelle valeur à un tableau tel qu’on le connait en PHP. On a donc bien un bloc d’une taille limitée par des bornes qu’on ne peut dépasser. Et c’est la principale différence avec les listes chaînées. Quand on créer un éléments dans une liste chaîné, c’est comme si on créait une variable (associé à un pointeur). On vous retourne la case 5646 pour l’élément A. Par contre, quant il s’agira de mettre l’élément B dans la liste, on créer notre variable B (comme une allocation de la mémoire dynamique normale) et on nous retournera comme case 2468. Cette valeur devra être insérer entant que pointeur dans notre élément A. Mais ce qu’on dénote c’est que la liste chaînée n’est pas continu dans la mémoire (
), néanmoins, elle est ordonnée par la présence d’un pointeur qui pointe sur l’élément suivant. D’une façon général, on pourrait dire que la liste chaînée (sa structure) ce compose de l’élément ainsi que d’un pointeur vers l’élément suivant de la liste. Il faut préciser aussi que le dernier élément d’une liste chaînée pointe vers la valeur NULL. Ce repère nous permettra de faire plusieurs actions sur la liste (comme connaître la taille d’une liste).
Il faut tout de même savoir qu’il est possible de modifier la taille d’un tableau en C, ajouter une valeur, supprimer. Néanmoins, les opérations nécessaires pour utiliser un tableau C comme en PHP sont fastidieuse car il s’agit de relouer la mémoire, y mettre le tableau avec/sans la nouvelle valeur et supprimer l’ancien tableau. C’est long, cela demande qu’on écrive dans la mémoire des blocs la liste chaînée propose un traitement rapide quant il s’agit de l’insertion ou de la suppression d’élément. Mais le point sur la rapidité sera vue un peu plus loin.
L’avantage est donc que la liste chaînée peut contenir autant de valeur que la mémoire peut contenir, la taille n’est plus fixe car concrètement chaque valeur de notre liste chaînée est à un endroit différent dans la mémoire de façon discontinue. Maintenant, on peut commencer à aborder le plan technique de la chose en C. On va donc créer une structure à partir du mot struct. Nous aborderons ici une représentation simple, il existe d’autres structures comme la liste doublement chaînée mais il n’est pas question ici de celle-ci et nous porterons notre réflexion sur la liste chaînée.
struct element
{
int value;
struct element *next;
};
typedef struct element element;
typedef struct element* list;
Voici donc la structure que nous utiliserons dans cet article. Le type de value n’est pas important, cela peut être n’importe quoi mais ici, j’utilise le type int pour une meilleur compréhension. Nous allons donc reprendre notre explication pour calculer la taille d’une liste chaînée (car sa taille est variable à la différence d’un tableau). Il faut savoir que calculer la taille d’un tableau en C est plus rapide puisque, comme il l’est dit, la taille d’un tableau est constante (avec le #define notamment) et toujours connue donc il n’y a pas d’opération pour le savoir. On peut opérer de façon récursive pour calculer la taille d’une liste chaînée. En effet, si notre liste équivaut à NULL, alors la taille est 0, sinon, sa taille équivaut à 1 + la taille de la liste pointée. Prenons une liste a qui ce compose de 
la valeur (en référence à la structure que l’on vient de faire en C) et 
, le pointeur. On déduit que la taille d’une liste équivaut à:
=\left\{\begin{array}{rcl}&0&\hfill si\ a=null\\&1&%2B\ len(a_{next})\end{array}\right.$$)
Au final, tant que l’on atteint pas le pointeur NULL (la fin de notre liste), on incrémente une variable t et si on atteint la valeur NULL, il nous suffit de retourner t. On remarque ici qu’on fait un parcours complet de la liste, on fait un comptage tout simplement mais celui-ci à le défaut d’avoir une complexité de )
avec n la taille de notre liste. On peut dire ici que le tableau est gagnant, néanmoins, il existe des méthodes pour être informer de la taille d’une liste sans pour autant devoir parcourir la liste en entier. Il s’agirait, selon vos objectifs, de créer une variable globale qu’on incrémenterait dès qu’il s’agira d’ajouter un nouvelle élément à notre liste par exemple. Il existe bien d’autres moyens pour obtenir la taille d’une liste mais celle-ci est générale et elle ne dépend que de notre structure de base (pour notre deuxième exemple, j’ai mentionner une variable globale ce qui peut rendre votre code mauvais). Après, c’est en fonction de vos objectifs que vous devrez adopter telle ou telle politique. Enfin, en code C, cela donne cette fonction:
int len(list a) {
if(a == NULL)
return 0;
return len(a->next) + 1;
}
Ce code correspond à notre attente, à savoir une structure conditionnelle ainsi que l’application d’une méthode récursive. Ici, je ne mentionne pas la variable t car il n’est pas nécessaire de le faire. Par contre, j’incrémente bien la valeur de retour. Néanmoins, savoir la taille pour une liste vide n’est pas intéressant, c’est pour cela que nous allons voir comment ajouter un élément à notre liste. On peut avoir recours à 2 méthodes pour ajouter un élément à une liste. Nous pouvons ajouter un l’élément à la fin de notre liste (cela équivaut à un push ou, en Python, à list.append(ma_valeur)) ou bien ajouter un élément au début de notre liste. Pour ce qui est d’ajouter un élément en début de liste, c’est très simple. Il faut d’abord allouer la mémoire pour un nouvelle élément. Comme dans le cas d’une liste chaînée, on fait une abstraction de la position de notre nouvelle élément dans notre mémoire, il nous suffit d’attribuer à la valeur la position dans la mémoire de notre ancienne liste. Ensuite, notre fonction retournera l’adresse de notre nouvelle élément pour informer que c’est notre nouveau premier élément:
Comme on le remarque ici, nous avons une variable a qui est une liste, on alloue la mémoire pour créer e en lui assignant par exemple la valeur 5, la prochaine valeur de e va devenir le premier élément de notre liste a (pour ranger e comme étant notre premier élément de notre nouvelle liste) et ensuite, la variable a nous dirigera vers e (comme étant le premier élément de notre liste). Ceci donne en C:
list push_before(list a, int value) {
element* e = malloc(sizeof(element));
e->value = value;
e->next = a;
return e;
}
On notera ici que la complexité quant il s’agit d’ajouter un élément en début de notre liste est de )
, il ne s’agit donc pas de traverser entièrement notre liste mais de juste faire une modification de nos références pour ajouter un nouvelle élément et c’est là la force de la liste chaînée. Cependant, on peut chercher à vouloir ajouter un élément à la fin de notre liste. Cela est un peu plus complexe que le code précédent (mais tout à fait abordable, rien de bien méchant). Pour ce faire, il faut ce référer à une caractéristique du dernier élément d’une liste, à savoir que 
équivaut à NULL. Et dans ce cas ci, il faudra parcourir notre liste à la recherche de notre dernier élément, c’est à dire atteindre tant que celui ci n’est pas NULL (note l’utilisation du mot clé tant que présent dans le langage algorithmique qui nous laisse donc penser à une itération). On peut donc expliquer ces instructions par cela:
, t_{next} = e)\end{array}\right.$$)
=\left\{\begin{array}{rcl}&a\ si\ a_{next} = null&\\&browse(a_{next})&\end{array}\right.$$)
C’est un peu plus compliqué comme vous le voyez. Il s’agit d’abord de créer un nouvelle élément e à l’aide de malloc, ensuite, si la liste est vide, il suffit de retourner e, sinon on parcourt la liste jusqu’à atteindre la référence à NULL (caractéristique du dernier élément d’une liste chaînée), on assigne donc la référence à notre dernier élément de notre liste à la variable t pour lui assigner dans son attribue next la référence de notre nouvelle élément e. Il faut remarque qu’on ne change pas, dans ce cas, la référence a (puisque le premier élément de notre liste ne change pas). Il faut noter aussi le fonctionnement de la fonction browse() qui est une fonction qui peut être récursive (ce qui est le cas avec le genre de représentation ci-dessus) mais aussi itérative. Dans notre cas, nous utiliserons la méthode itérative (avec le tant que) pour ne pas trop alourdir notre code. Néanmoins, on peut tout de même implémenter cette fonction qui renvoie le dernier élément d’une liste. Si vous suivez toujours, on peut passer à l’implémentation en C qui est:
list push_back(list a, int value) {
element* e = malloc(sizeof(element));
e->value = value;
e->next = NULL;
if(a == NULL)
return e;
else {
element* t = a;
while(t->next != NULL)
t = t->next;
t->next = e;
return a;
}
}
Si on revient sur ce code, on repère quant il s’agit d’allouer la mémoire (comme pour notre fonction push_before), ensuite nous avons une structure conditionnel pour vérifier si a est NULL ou pas. Dans le cas où a est NULL, on retourne le nouvelle élément e, sinon on utilise une implémentation itérative de la fonction browse() pour parvenir au dernier élément qu’on sauvegarde dans la variable t, et enfin on assigne comme référence à 
notre nouvelle élément e, on termine donc par retourner a. On remarque que l’ajout d’une valeur en fin d’une liste contient un parcours de la dite-liste ce qui nous amène à une complexité de ce qui n’est pas négligeable. Néanmoins, on peut encore donner l’avantage aux listes chaînées par rapport aux tableaux en inversant la liste donc en considérant que le début est la fin et vise-versa, cette représentation est à faire dans votre tête et pas réellement dans le code. En effet, ainsi, pour ajouter un élément à la fin, vous utiliserez notre première fonction pour obtenir une complexité et concernant la taille, que la liste soit dans un sens ou dans l’autre, cela ne change rien. Mais qui dit allocation dynamique dit aussi qu’on l’on doit vider ce qu’on a alloué ! Il faut donc bien vérifier que notre liste devienne vide à la fin, pour ce faire, c’est très simple et cela rentre plus dans le domaine technique que algorithmique. Il nous suffira de libérer la mémoire à l’aide de free tant que notre liste n’équivaut pas à NULL. Noter l’utilisation du mot clé tant que ce qui nous donne déjà une idée de comment nous allons implémenter cela.
void free_list(list a) {
while(a != NULL) {
element* t = a;
a = a->next;
free(t);
}
}
Ici, on parcours notre liste, et à chaque élément, on utilise la fonction free() pour libérer la mémoire. La variable t est une variable de temporisation car elle permet juste de garder une valeur pendant un temps déterminer pour ensuite faire une action sur celle-ci (la fonction free() notamment) quand toute les conditions nécessaires sont acquises (en outre, le passage à l’élément suivant de notre liste avec a = a->next). Vous pouvez désormais tester votre code en ajoutant des éléments et en notant la taille de votre liste pour ensuite la vider ! Concernant l’affichage de votre liste, ce n’est pas très compliqué, tant qu’une variable t n’équivaut pas à NULL, on affiche 
et on assigne à t la référence pour passer à l’élément suivant. Bien entendu, il faut initialiser t comme faisant référence à notre liste a ce qui donne en C:
void print(list a) {
element* t = a;
while(t != NULL) {
printf("%d ", t->value);
t = t->next;
}
printf("\n");
}
Il peut arriver qu’on veuille accéder à un élément distinct de notre liste. Dans le cas d’un tableau, il suffit de spécifier l’index, par exemple mon_tableau[4] renvoie la cinquième valeur de mon tableau (n’oubliez pas que l’index commence par 0). Mais dans une liste, comment on fait ? Eh bien, là aussi dans ce cas, le tableau à une complexité plus intéressante (puisqu’elle est de ) que celle de la liste qui est de avec n notre indice (c’est à dire, l’index + 1). Ainsi, si vous voulez accéder au premier élément de votre liste, vous aurez une complexité de , pour le deuxième )
, etc … Il s’agit donc de parcourir la liste jusqu’au n-ième élément. On peut faire l’analogie avec la fonction browse() vue plus haut. Sauf qu’on ne cherchera pas à atteindre le pointeur vers NULL (c’est à dire la fin de notre liste) mais à s’arrêter dès qu’on est fait n fois l’instruction t = t->next avec t la référence de notre liste à l’initialisation. Ce qui équivaut donc à:
 > n : a[n] = \left\{\begin{array}{rcl}&a&\hfill si\ i = n\\&a_{next}[n]&\hfill after\ (i = i %2B 1)\end{array}\right.$$)
Il faut d’abord savoir si on demande bien un élément qui est dans notre liste. C’est à dire l’indice d’un élément qui soit strictement inférieur à la taille de notre liste. On peut aussi arrêter les instructions quand 
, c’est à dire quand on a atteint la fin de la liste. Ensuite, si i équivaut à n (à l’indice que l’on recherche), alors on retourne a. Sinon on passe à l’élément suivant avec 
(noter le [n] qui refait appelle à notre structure conditionnelle, c’est la récursivité) après avoir incrémenter i de 1. Ici, nous choisirons d’écrire la fonction par la méthode itérative car l’intérêt de la récursivité n’y est pas et qu’on peut très bien s’en sortir avec une boucle for.
list element_i(list a, int n) {
int i = 0;
while(i < n && a != NULL) {
a = a->next;
++i;
}
if(a == NULL)
return NULL;
else
return a;
}
Cette fonction ne correspond pas en tout point à notre représentation plus haut. En effet, déjà, notre représentation plus haut suggère d’utiliser une méthode récursive (notamment en rappelant la même fonction) alors qu’ici, nous utilisons une méthode itérative (avec while). Ensuite, notre représentation suggère d’utiliser comme nom de fonction l’opérateur [] alors qu’ici, on fait appelle à la fonction element_i. À ma connaissance, il est impossible en C de modifier un opérateur d’une structure tel que [] (mais peut être que je me trompe). Dans notre représentation, nous utilisons [] pour faire l’analogie avec les tableaux (qui utilisent cet opérateur) et comprendre son objectif final (enfin je l’espère) donc ne soyez pas perturber par cela. On peut maintenant décrire le code si dessus. Il s’agit d’une valeur i qu’on incrémente tant que (while) celle ci est inférieur à l’indice recherché n et tant que notre liste a n’équivaut pas à NULL (ce qui reviendrait à arrêter l’instruction while quant on a atteint la fin de notre liste). Ensuite, si a équivaut à NULL (si on a atteint notre liste), on retourne NULL. Sinon on retourne a qui est l’élément qui correspond à notre indice n. Attention cette fonction doit être vérifier. En effet, l’écriture du type element_i(a, 5)->value est à proscrire si on n’est pas sûr de la taille de notre liste car la fonction peut retourner NULL et cela engendre un segment fault (puisque NULL ne contient pas value). Dans ce cas, on peut très bien choisir de retourner le dernier élément de notre liste dans le cas où i serait supérieur ou égal à n (après, tout dépend de votre programme et de vos objectifs) pour éviter à faire une nouvelle structure conditionnel qui devrait vérifier si ce que retourne cette fonction est bien différent de NULL. Si tel est notre objectif, on allège un peu notre code ce qui donne:
list element_i(list a, int n) {
int i = 0;
while(i < n && a->next != NULL) {
a = a->next;
++i;
}
return a;
}
Ici, il suffit de s’arrêter au dernier élément de notre liste et retourner a dans tout cas, c’est à dire quand on à atteint l’indice n ou quand on a atteint la dernière valeur de notre liste. L’instruction element_i(a, 5)->value devient donc juste et retournera soit a[n], soit a[len(a) - 1] dans le cas ou on demande un indice supérieur ou égal à la taille de notre tableau. Ceci montre que mes exemples ne sont pas à prendre à la lettre et qu’on peut très bien s’amuser à les modifier pour qu’ils conviennent à nos objectifs, mais ça, c’est à vous de voir. Au final, on a une complexité de dans le pire des cas, on parle ici d’un accès arbitraire à un élément de la liste et le tableau a l’avantage sur ce coup car il propose un accès arbitraire avec une complexité de . Pourquoi ? Tout simplement parce que pour accéder au cinquième élément d’un tableau, on prend la référence du premier élément de notre tableau et on y ajoute 4 puisque, je le rappelle, la caractéristique d’un tableau est d’être représenter dans la mémoire de façon continue. On a maintenant des fonctions sur l’écriture, sur l’affichage mais aucune sur la suppression (on a quand même free_list mais cette fonction est plus de l’ordre technique … c’est une fonction tout de même importante). Ces fonctions de suppression sont pas très complexes et ressemblent aux fonctions d’ajouts sauf qu’au lieu d’utiliser malloc, on utilisera free. On va donc ici passer directement au code sans prendre le temps de bien expliquer ces fonctions que vous pouvez comprendre avec tout ce que vous avez vue:
list pop_before(list a) {
if(a != NULL) {
element* e = a->next;
free(a);
return e;
} else
return NULL;
}
list pop_back(list a) {
if(a == NULL)
return NULL;
if(a->next == NULL) {
free(a);
return NULL;
}
element* e = a;
element* t = a;
while(e->next != NULL) {
t = e;
e = e->next;
}
t->next = NULL;
free(e);
return a;
}
La principale différence qu’on peut trouver par rapport aux autres fonctions, c’est l’utilisation non seulement de la fonction free pour libérer la mémoire mais aussi l’ajout d’une nouvelle structure conditionnel qui permet de vérifier si la liste est NULL. Ensuite, le fonctionnement est très basique. Les notions sont expliquées plus haut (comme pour la boucle while dans la fonction pop_back) et je n’y reviendrais pas. Nous allons maintenant parler des fonctions utiles pour les fonctions comme la concaténation. Pour ceux qui ne le savent pas, la concaténation permet de mettre bout à bout au moins deux ensemble (ici deux listes). On peut faire l’analogie avec les suffixes et les préfixes qui viennent s’ajouter à un mot pour changer notamment son sens. Ici, c’est pareil, on va ajouter les éléments d’une liste à une autre liste pour former une nouvelle liste. Pour le cas de deux tableaux, c’est simple, il suffit de savoir la taille de notre tableau a puis celle de notre tableau b pour ensuite créer un tableau c de taille  %2B len(b))
. Il suffit ensuite d’insérer tout les éléments de a dans c et les éléments de b dans c à partir de )
. Pour le cas d’une liste, on peut très bien faire l’analogie avec push_before. En effet, ajouter une liste a au début d’une liste b équivaut à modifier la référence du dernier élément de a. Ainsi, on déduit que la complexité de cette algorithme est de ))
. Il suffit d’utiliser par la méthode itérative notre fonction browse() pour atteindre le dernier élément de a et modifier comme étant égal à 
:
, t_{next} = b)
Et sous forme de code, cela donne:
list concat(list a, list b) {
if(a != NULL) {
element* t = a;
while(t->next != NULL)
t = t->next;
t->next = b;
return a;
} else
return b;
}
Comme on peut le voir, j’ai rajouter une structure conditionnel pour savoir si a n’équivaut pas à NULL, si c’est le cas, alors on peut parcourir a et atteindre son dernier élément pour changer la référence. Sinon, on retourne b (puisque a est NULL). Et dans le cas où b serait NULL cela n’influencerait en rien le code puisque si a et b sont NULL, on retourne NULL et si c’est seulement b qui est NULL, on retourne a (car on aura changer la référence du dernier élément de a en NULL ce qui ne change rien …). Ici, nous avons à faire à un effet de bord car en effet, on modifie la liste a en lui rajoutant la liste b. En d’autres termes, l’état de la variable a n’est plus le même après la fonction et dans le cas où vous voudriez utiliser la liste générer par cette fonction ainsi que la liste a (celle avant l’appel de la fonction concat) vous utiliseriez en faite la même liste. L’avantage, c’est qu’on alloue pas la mémoire, l’inconvénient c’est que dans une portée restreinte tel que la fonction main (c’est à dire en ne sachant pas le fonctionnent de concat car il est présent dans un autre fichier obscur de votre système) où nous ne pouvons pas avoir accès à la fonction concat, on peut avoir un comportement implicite (qui ne se voit pas) sur nos variables ce qui peut engendrer des erreurs (cela ce complique réellement dans l’utilisation de thread). Le moyen pour éviter cela est de cette fois, allouer la mémoire pour véritablement créer une nouvelle liste indépendante de A. Pour procéder, nous allons tester d’abord si A n’est pas NULL, dans ce cas, nous allons appliquer 2 instructions qui utilisent push_before et concat. Noter que nous avons à faire à de la récursivité. concat va s’occuper d’un ensemble de liste A qui ce trouve après le premier élément de A et push_before va ajouter le premier élément de la liste A au résultat de la fonction concat. On peut décrire le code de cette façon:
 = \left\{\begin{array}{rcl}&b\hfill si\ a = null&\\&e\ after\ (e_{value} = a_{value}, e_{next} = concat(a_{next}, b))\end{array}\right.$$)
Comme on peut le voir, on a à faire à une fonction récursive. Dans le cas où a serait NULL, on retourne b (il n’y a pas de concaténation à faire). Sinon, on retourne e après qu’on est renseigner comme faisant référence à )
(bien entendu, il faut aussi renseigner 
aussi). Au final, cet appel de fonction va rajouter le deuxième élément à b qui va refaire appel à la fonction pour ajouter le troisième élément de a à b, ainsi de suite … Cette fonction récursive a la particularité de, non seulement faire un parcours de la liste a (en spécifiant toujours comme argument) mais aussi d’appliquer la fonction push_before. En effet, les instructions )
ressemble aux instructions qu’on retrouve dans la fonction push_before mais où value est a->value et notre liste est concat(a->next, b). Ainsi, on ne change pas l’état de la variable a (on y accède seulement en lecture) et seul b est modifié. L’effet de bord n’est plus. Et pour ce qui est du code, c’est très simple:
int concat(list a, list b) {
if(a == NULL)
return b;
else
return push_before(concat(a->next, b), a->value);
}
Donc ici, comme on peut le voir, on utilise la fonction puhs_before qui va rajouter le premier élément de a à concat(a->next, b). Cette fonction concat(a->next, b) va s’occuper d’ajouter récursivement tout les éléments situés après a, c’est à dire en commençant par a->next. On peut visualiser cette récursivité dans 2 sens. Le premier, c’est le parcours de a jusqu’à que a équivaut à NULL. Arriver à ce point, on peut maintenant, dans le sens inverse (du dernier élément de a au premier), ajouter les éléments de a avec push_before à b. On peut noter que, en comparaison avec les tableaux, la concaténation d’une liste a avec une liste b dépend que de la taille de a. Je vous rappelle que la concaténation d’un tableau à une complexité de  %2B len(b)))
, ici, c’est une complexité de seulement. Donc on peut dire que l’avantage de la concaténation d’une liste ce retrouve quant il s’agit d’ajouter une petite liste à une autre qui est grande. Par rapport à notre première fonction, la grande différence ce que la première reprend directement le fonctionnement de push_before avec comme valeur toute la liste a. Dans notre deuxième fonction, on utilise push_before pour chaque élément de a (on fait de la copie) ce qui assure que l’état de a reste inchangé. Nous allons maintenant faire une dernière fonction (enfin!) où cette fois, on va s’intéresser aux éléments par rapport à un critère. Par exemple, dans ma liste de nombres, je ne veux que les éléments dont leurs valeurs équivaut à 4. On va, ici, utiliser ce qu’on appelle un prédicat. C’est à dire une fonction mettant en œuvre un ou plusieurs arguments, utilisée pour déclarer quelque chose concernant notre élément courant, et dont le résultat est true ou false. C’est à dire que nous allons vérifier si notre élément courant (par exemple a[5]) contient comme valeur 4. Si c’est le cas, on retourne true, sinon false. L’utilisation des prédicats est courante et cette notion peut devenir très complexe quant il s’agit de connaître une relation entre 2 objets différents. Ici, ce n’est pas très complexe de trouver la relation qu’il peut y avoir entre le nombre 4 et notre liste a. Nous allons donc créer une nouvelle liste qui intègre la position de tout les éléments de notre liste a dont leurs valeurs équivaut à 4 (toujours dans notre exemple). Il suffit donc de parcourir notre liste a et de tester si l’élément courant de a (qu’on pourrait être noter a[i]) est égal à 4. Il s’agit ensuite d’ajouter (par le biais de push_before et non pas en modifiant la référence sinon on aura un effet de bord) i (la position courante) à notre nouvelle liste ce qui donne directement en code:
list search(list a, int value) {
list r = NULL;
list t = a;
int i = 0;
while(t != NULL) {
if(t->value == value)
r = push_before(r, i);
++i;
t = t->next;
}
return r;
}
Puisque la fonction push_before a une complexité de , la complexité de notre fonction search est de avec n la taille de notre liste a (puisqu’on fait un parcours dans cette liste). L’algorithme n’est pas très complexe et il ne s’agit que de parcourir notre liste et par une structure conditionnel, ajouter ou non la valeur courante de i à notre nouvelle liste, i étant l’indice courant de notre liste a. Ainsi, si on recherche tout les éléments dont leurs valeurs est 4, on obtient une liste r et cette instruction devrait renvoyer 4: a[r[0]] si len(r) est strictement supérieur à 0 (c’est à dire si notre fonction search trouve au moins une fois la valeur 4 dans notre liste a). Pour le cas d’un tableau, comme la modification de la taille d’un tableau est très couteuse, on ne peut ce permettre de modifier la taille du tableau r (ajouter un nouvelle élément) dès qu’on trouve un élément dans a dont la valeur est 4 (pour rester dans notre exemple). Il serait possible de compter le nombre d’éléments dont la valeur est 4 pour ensuite créer un tableau dont la taille conviendrait à notre recherche et refaire une boucle pour insérer les positions dans notre nouveau tableau. On fait donc deux boucles qui tourne n fois avec n la taille de notre tableau a. La complexité de cette algorithme reste puisque cela reste proportionnel à n mais il reste tout de même plus lent que celui avec les listes. Ensuite, si vous appliquer l’algorithme search pour les listes mais cette fois ci avec les tableaux, je vous ai dit qu’on ne pouvait ce permettre de le faire puisque la modification de la taille d’un tableau est trop couteuse. Néanmoins, il est intéressant de comprendre la complexité algorithmique dans ce cas car c’est là où on voit l’intérêt des structures de donner pour un même algorithme. En effet, comme la complexité algorithmique de push_before pour un tableau est de (puisqu’il s’agit de recréer un tableau b à partir d’un tableau a dont la taille serait  %2B 1)
et d’insérer tout les anciens éléments de a plus le nouvelle élément), et que notre boucle tourne n fois, on aura une complexité de )
donc une complexité quadratique.
Vous savez enfin manipuler les listes chaînées et les complexités de certains algorithmes basiques. Néanmoins, ne prenez pas mes exemples à la lettre car il faut tout d’abord prendre conscience de ce que vous avez besoin (car en effet, le tableau est parfois plus judicieux que les listes chaînées). Mais je n’ai pas développé tout ce qu’on pouvait faire avec les listes (il existe plein d’autres choses plus ou moins complexes, à vous de les trouver). Ce qu’il faut bien comprendre, c’est d’établir en fonction de ses besoins une structure de données qui ne dégrade pas la qualité de votre tableau. Mais attention, votre choix ne devrait pas être décisif et il sera peut être courant de jouer entre plusieurs structures de données. C’est là où intervient la notion de conversion (qui n’a jamais eu la problème de vouloir passer d’un int à un char* et vice-versa). Il s’agit donc de bien définir la structure de votre programme. Concernant mes affirmations sur PHP et Python concernant les listes, disons que ces tableaux on un comportement un peu bizarre par rapport à ce qu’on a appris. Le tout, c’est de renseigner, notamment avec la documentation, sur la complexité des opérations que l’on peut faire avec. Après, il s’agit de bien prendre conscience qu’une complexité de pour l’ajout d’un élément par exemple dans l’un de vos super algorithmes complexes peut entraîner des dégâts et dégrader votre programme. Il ne s’agit donc pas seulement de savoir la complexité de notre algorithme mais aussi de prendre en compte la complexité des autres algorithmes (plus simples que vous pouvez sûrement considérer comme des opérations naturels) que vous utilisez. Après, comme il est dit, on peut jouer entre les structures quant il s’agit de faire des opérations que, par exemple, les tableaux gèrent mieux que les listes.
C’est terminer pour cette article un peu trop long je pense ! Bonne programmation.