L'information est partout autour de nous.

Dans le monde des logiciels, la manière dont nous choisissons d'organiser nos informations représente la moitié de la bataille. Mais voici le problème: il y a tellement de façons de résoudre un problème. Et lorsqu'il s'agit d'organiser nos données, il existe de nombreux outils qui pourraient fonctionner pour le travail. L'astuce est de savoir quel outil est le bon à utiliser.

Quelle que soit la langue dans laquelle nous commençons à coder, l'une des premières choses que nous rencontrons sont les structures de données , qui sont les différentes façons dont nous pouvons organiser nos données; les variables , les tableaux , les hachages et les objets sont tous des types de structures de données. Mais ce ne sont encore que la pointe de l'iceberg en ce qui concerne les structures de données; il y en a beaucoup plus, dont certains commencent à sembler super compliqués à mesure que vous en entendez parler.

Une de ces choses compliquées pour moi a toujours été les listes chaînées . Je connais les listes chaînées depuis quelques années maintenant, mais je ne peux jamais tout à fait les garder dans ma tête. Je ne pense vraiment à eux que lorsque je prépare (ou parfois, au milieu) un entretien technique, et que quelqu'un me pose des questions à leur sujet. Je vais faire un peu de recherche et penser que je comprends de quoi il s'agit, mais après quelques semaines, je les oublie à nouveau. Tout cela est assez inefficace, et tout cela vient du fait que je sais qu'ils existent, mais je ne les comprends pas fondamentalement ! Il est donc temps de changer cela et de répondre à la question: qu'est-ce qu'une liste chaînée, de toute façon?

Structures de données linéaires

Si nous voulons vraiment comprendre les bases des listes chaînées, il est important de parler de leur type de structure de données.

Une caractéristique des listes chaînées est qu'elles sont des structures de données linéaires , ce qui signifie qu'il existe une séquence et un ordre dans la manière dont elles sont construites et parcourues. Nous pouvons penser à une structure de données linéaire comme un jeu de marelle : pour arriver à la fin de la liste, nous devons parcourir tous les éléments de la liste dans l'ordre, ou séquentiellement . Les structures linéaires, cependant, sont le contraire des structures non linéaires. Dans les structures de données non linéaires , les éléments n'ont pas besoin d'être organisés dans l'ordre, ce qui signifie que nous pouvons traverser la structure de données de manière non séquentielle .

Nous ne le réalisons peut-être pas toujours, mais nous travaillons tous avec des structures de données linéaires et non linéaires tous les jours! Lorsque nous organisons nos données en hachages (parfois appelés dictionnaires ), nous implémentons une structure de données non linéaire. Les arbres et les graphiques sont également des structures de données non linéaires que nous traversons de différentes manières, mais nous en parlerons plus en détail plus tard dans l'année.

De même, lorsque nous utilisons des tableaux dans notre code, nous implémentons une structure de données linéaire! Il peut être utile de penser que les tableaux et les listes chaînées sont similaires dans la manière dont nous séquencons les données. Dans ces deux structures, l' ordre est important . Mais qu'est-ce qui différencie les tableaux et les listes chaînées?

Gestion de la mémoire

Le plus grand différenciateur entre les tableaux et les listes chaînées est la façon dont ils utilisent la mémoire dans nos machines. Ceux d'entre nous qui travaillent avec des langages à typage dynamique comme Ruby, JavaScript ou Python n'ont pas à penser à la quantité de mémoire utilisée par un tableau lorsque nous écrivons notre code au jour le jour car il y a plusieurs couches d'abstraction qui finissent par avec nous n'avons pas du tout à nous soucier de l'allocation de mémoire.

Mais cela ne signifie pas que l'allocation de mémoire ne se produit pas! L'abstraction n'est pas de la magie, c'est juste la simplicité de cacher des choses que vous n'avez pas besoin de voir ou de gérer tout le temps. Même si nous n'avons pas à penser à l'allocation de mémoire lorsque nous écrivons du code, si nous voulons vraiment comprendre ce qui se passe dans une liste chaînée et ce qui la rend puissante, nous devons passer au niveau rudimentaire.

Nous avons déjà appris le binaire et comment les données peuvent être divisées en bits et octets. Tout comme les caractères, les nombres, les mots, les phrases nécessitent des octets de mémoire pour les représenter, il en va de même pour les structures de données.

Lorsqu'un tableau est créé, il a besoin d'une certaine quantité de mémoire. Si nous avions 7 lettres que nous devions stocker dans un tableau, nous aurions besoin de 7 octets de mémoire pour représenter ce tableau. Mais, nous aurions besoin de toute cette mémoire dans un bloc contigu . C'est-à-dire que notre ordinateur aurait besoin de localiser 7 octets de mémoire libre, un octet à côté de l'autre, tous ensemble, au même endroit.

D'autre part, lorsqu'une liste chaînée est née, elle n'a pas besoin de 7 octets de mémoire en un seul endroit. Un octet pourrait vivre quelque part, tandis que l'octet suivant pourrait être stocké à un autre endroit en mémoire! Les listes liées n'ont pas besoin de prendre un seul bloc de mémoire; au lieu de cela, la mémoire qu'ils utilisent peut être dispersée partout .

La différence fondamentale entre les tableaux et les listes liées est que les tableaux sont des structures de données statiques , tandis que les listes liées sont des structures de données dynamiques . Une structure de données statique a besoin que toutes ses ressources soient allouées lorsque la structure est créée; cela signifie que même si la structure devait grossir ou diminuer en taille et que des éléments devaient être ajoutés ou supprimés, elle a toujours besoin d'une taille et d'une quantité de mémoire données. Si plus d'éléments devaient être ajoutés à une structure de données statique et qu'elle ne disposait pas de suffisamment de mémoire, vous devrez copier les données de ce tableau, par exemple, et le recréer avec plus de mémoire, afin de pouvoir ajouter des éléments à il.

D'un autre côté, une structure de données dynamique peut rétrécir et croître en mémoire. Il n'a pas besoin d'une quantité définie de mémoire pour être allouée pour exister, et sa taille et sa forme peuvent changer, et la quantité de mémoire dont elle a besoin peut également changer.

À présent, nous pouvons déjà commencer à voir des différences majeures entre les tableaux et les listes liées. Mais cela soulève la question: qu'est - ce qui permet à une liste chaînée d'avoir sa mémoire dispersée partout? Pour répondre à cette question, nous devons examiner la manière dont une liste chaînée est structurée.

Parties d'une liste chaînée

Une liste chaînée peut être petite ou énorme, mais quelle que soit sa taille, les parties qui la composent sont en fait assez simples. Une liste chaînée est constituée d'une série de nœuds , qui sont les éléments de la liste.

Le point de départ de la liste est une référence au premier nœud, qui est appelé la tête . Presque toutes les listes chaînées doivent avoir une tête, car c'est effectivement le seul point d'entrée de la liste et de tous ses éléments, et sans elle, vous ne sauriez pas par où commencer! La fin de la liste n'est pas un nœud, mais plutôt un nœud qui pointe vers null ou une valeur vide.

Un seul nœud est également assez simple. Il ne comporte que deux parties: les données ou les informations contenues dans le nœud et une référence au nœud suivant .

Si nous pouvons comprendre cela, nous en sommes à mi-chemin. La façon dont les nœuds fonctionnent est super importante et super puissante, et pourrait être résumée comme suit:

Un nœud ne connaît que les données qu'il contient et qui est son voisin.

Un seul nœud ne sait pas combien de temps dure la liste chaînée, et il ne sait même pas nécessairement où elle commence ni où elle se termine. Tout ce qui concerne un nœud, ce sont les données qu'il contient et le nœud auquel son pointeur fait référence - le nœud suivant dans la liste.

Et c'est la raison même pour laquelle une liste chaînée n'a pas besoin d'un bloc de mémoire contigu. Parce qu'un seul nœud a «l'adresse» ou une référence au nœud suivant, ils n'ont pas besoin de vivre les uns à côté des autres, comme les éléments doivent le faire dans un tableau. Au lieu de cela, nous pouvons simplement nous fier au fait que nous pouvons parcourir notre liste en nous appuyant sur les références du pointeur vers le nœud suivant, ce qui signifie que nos machines n'ont pas besoin de bloquer un seul morceau de mémoire pour représenter notre liste.

C'est aussi l'explication de la raison pour laquelle les listes chaînées peuvent croître et rétrécir dynamiquement pendant l'exécution d'un programme. Ajouter ou supprimer un nœud avec une liste chaînée devient aussi simple que de réorganiser certains pointeurs, plutôt que de copier les éléments d'un tableau! Cependant, les listes chaînées présentent également certains inconvénients que je ne vous mentionne pas encore - mais plus sur ceux de la semaine prochaine.

Pour l'instant, nous nous réjouirons de la beauté des listes liées!

Listes pour toutes les formes et tailles

Même si les parties d'une liste chaînée ne changent pas, la façon dont nous structurons nos listes chaînées peut être très différente. Comme la plupart des logiciels, selon le problème que nous essayons de résoudre, un type de listes chaînées peut être un meilleur outil pour le travail qu'un autre.

Les listes chaînées individuelles sont le type de liste chaînée le plus simple, basé uniquement sur le fait qu'elles ne vont que dans une seule direction. Il y a une seule piste dans laquelle nous pouvons parcourir la liste; on commence à la tête noeud, et parcourt depuis la racine jusqu'à ce que le dernier noeud, qui se termine à un vide nulle valeur.

Mais tout comme un nœud peut référencer son nœud voisin suivant, il peut également avoir un pointeur de référence vers son nœud précédent! C'est ce que nous appelons une liste doublement chaînée , car il y a deux références contenues dans chaque nœud: une référence au nœud suivant , ainsi qu'au nœud précédent . Cela peut être utile si nous voulons pouvoir parcourir notre structure de données non seulement dans une seule piste ou direction, mais aussi vers l'arrière.

Par exemple, si nous voulions pouvoir sauter entre un nœud et le nœud précédent sans avoir à revenir au tout début de la liste , une liste doublement chaînée serait une meilleure structure de données qu'une liste liée individuellement. Cependant, tout nécessite de l'espace et de la mémoire, donc si notre nœud devait stocker deux pointeurs de référence au lieu d'un seul, ce serait une autre chose à considérer.

Une liste chaînée circulaire est un peu étrange en ce qu'elle ne se termine pas par un nœud pointant vers une valeur nulle. Au lieu de cela, il a un nœud qui agit comme la queue de la liste (plutôt que le nœud principal conventionnel), et le nœud après le nœud de queue est le début de la liste. Cette structure d'organisation facilite grandement l'ajout de quelque chose à la fin de la liste, car vous pouvez commencer à la parcourir au nœud de queue , car le premier élément et le dernier élément se pointent l'un vers l'autre. Les listes chaînées circulaires peuvent commencer à devenir vraiment folles car nous pouvons transformer à la fois une liste chaînée unique et une liste double chaînée en une liste chaînée circulaire!

Mais quelle que soit la complexité d'une liste chaînée, si nous pouvons nous souvenir des principes fondamentaux d'un nœud, de son fonctionnement et de la structure des différentes références de pointeurs de notre liste, il n'y a pas de liste chaînée que nous ne pouvons pas aborder!

La semaine prochaine, dans la deuxième partie de cette série, nous nous pencherons sur la complexité spatio-temporelle des listes chaînées et sur leur comparaison avec leur cousin, le tableau. Je promets que c'est en fait beaucoup plus amusant qu'il n'y paraît!

Ressources

Si vous pensez que les listes liées sont super cool, consultez ces ressources utiles.

1. Différences entre les tableaux et les listes liées , Damien Wintour
2. Structures de données: tableaux vs listes liées , mycodeschool
3. Listes liées: The Basics , Dr Edward Gehringer
4. Introduction aux listes liées , Dr Victor Adamchik
5. Structures et implémentations de données , Dr. Jennifer Welch
6. Structures de données statiques vs structures de données dynamiques , Ayoma Gayan Wijethunga