[Powered by Google Translate] Dans la programmation, nous avons souvent besoin de représenter des listes de valeurs, tels que les noms des élèves dans une section ou de leurs scores sur le dernier quiz. 

Dans le langage C, a déclaré tableaux peuvent être utilisés pour stocker des listes. Il est facile d'énumérer les éléments d'une liste stockées dans un tableau, et si vous avez besoin d'accéder à ou de modifier l'élément de liste ième pour un indice arbitraire I, qui peut être fait en temps constant, mais les tableaux présentent des inconvénients, aussi. 

Quand nous leur déclarons, nous sommes tenus de dire avant toute chose comment ils sont gros, qui est, combien d'éléments qu'ils peuvent stocker et la taille de ces éléments sont, ce qui est déterminé par leur type. Par exemple, int arr (10) peut stocker 10 articles qui sont de la taille d'un int. 

Nous ne pouvons pas changer la taille d'une baie après la déclaration. Nous devons faire un nouveau tableau, si nous voulons stocker plus d'éléments. La raison de cette limitation existe, c'est que notre programme stocke tout l'éventail comme un bloc contigu de mémoire. Dire que c'est la mémoire tampon où nous avons stocké dans notre tableau. Il pourrait y avoir d'autres variables situé juste à côté de la matrice dans la mémoire, donc nous ne pouvons pas juste faire le tableau plus grand. 

Parfois, nous aimerions échanger rapidement le tableau de la vitesse d'accès aux données pour un peu plus de souplesse. Entrez la liste chaînée, une autre structure de données de base vous pourriez ne pas être aussi familier avec. À un niveau élevé, une liste chaînée stocke des données dans une séquence de noeuds qui sont reliés les uns aux autres avec des liens, d'où le nom de «liste chaînée. Comme nous le verrons, cette différence de conception conduit à des avantages et des inconvénients différents qu'un tableau. 

Voici un peu de code C pour une liste très simple liée d'entiers. Vous pouvez voir que nous avons représenté chaque nœud dans la liste en tant que struct qui contient 2 choses, un entier pour stocker appelé 'val' et un lien vers le noeud suivant dans la liste que nous représentons comme un pointeur appelé "Suivant". De cette façon, nous pouvons suivre toute la liste avec juste un seul pointeur vers le nœud 1er et alors nous pouvons suivre les indications suivantes pour le 2ème noeud, pour le 3ème noeud, au nœud 4, et ainsi de suite, jusqu'à ce que nous arrivons à la fin de la liste. 

Vous pourriez être en mesure de voir ce qui a 1 avantage sur la structure de matrice fixe - avec une liste chaînée, nous n'avons pas besoin d'un gros morceau de la mémoire tout à fait. Le 1er noeud de la liste pourrait vivre à cet endroit dans la mémoire, et le 2ème noeud, pourrait être tout le chemin là-bas. Nous pouvons accéder à tous les nœuds, peu importe où ils sont dans la mémoire, car à partir du 1er noeud, pointeur à côté de chaque nœud nous dit exactement où aller. 

En outre, nous n'avons pas de dire à l'avance la taille d'une liste chaînée sera notre façon de faire avec les tableaux statiques, puisque nous ne pouvons continuer à ajouter des nœuds à un liste tant qu'il ya de la place quelque part en mémoire pour les nouveaux nœuds. Par conséquent, les listes chaînées sont faciles à redimensionner dynamiquement. Dire, plus tard dans le programme, nous devons ajouter d'autres noeuds à notre liste. Pour insérer un nouveau nœud dans notre liste à la volée, tout ce que nous avons à faire est d'allouer la mémoire pour ce nœud, plop dans la valeur de données, et ensuite le placer où l'on veut en ajustant les pointeurs appropriés. 

Par exemple, si nous voulions placer un nœud entre les deux les noeuds de 2e et 3e de la liste,  nous n'aurions pas à déplacer les noeuds de 2e ou 3e du tout. Disons que nous vous insérez ce nœud rouge. Tout ce que nous aurions à faire est de positionner le pointeur à côté du nouveau nœud pour pointer vers le 3ème noeud puis recâbler pointeur suivant le 2ème noeud de pour pointer vers notre nouveau noeud. Ainsi, nous pouvons redimensionner nos listes à la volée depuis notre ordinateur ne repose pas sur l'indexation, mais plutôt sur les liens entre l'utilisation de pointeurs pour les stocker. 

Listes Toutefois, un inconvénient de lien est que, contrairement à un tableau statique, l'ordinateur ne peut pas sauter au milieu de la liste. Depuis l'ordinateur doit se rendre dans chaque nœud de la liste chaînée pour arriver à la suivante, ça va prendre plus de temps pour trouver un nœud particulier que ce serait dans un tableau. Pour parcourir la liste entière prend un temps proportionnel à la longueur de la liste, ou O (n) en notation asymptotique. En moyenne, atteignant un nœud prend aussi du temps proportionnel à n. 

Maintenant, nous allons écrire un peu de code qui travaille avec les listes chaînées. Disons que nous voulons une liste chaînée d'entiers. Nous pouvons représenter un nœud dans notre liste à nouveau comme une structure avec 2 champs, une valeur entière appelée 'val' et un pointeur à côté du nœud suivant de la liste. Eh bien, semble assez simple. 

Disons que nous voulons écrire une fonction qui traverse la liste et imprime le valeur stockée dans le dernier noeud de la liste. Eh bien, cela signifie que nous devrons parcourir tous les nœuds de la liste pour trouver la dernière, mais puisque nous ne sommes pas en ajoutant ou la suppression de quoi que ce soit, nous ne voulons pas changer la structure interne des pointeurs suivant dans la liste. 

Donc, nous aurons besoin d'un pointeur spécifiquement pour la traversée que nous appellerons «crawler». Il ramper à travers tous les éléments de la liste par suite de la chaîne de pointeurs à venir. Tout ce que nous avons stocké est un pointeur vers le nœud 1er ou «tête» de la liste. Points de la tête au 1er noeud. C'est un type de pointeur à nœud. 

Pour obtenir le véritable premier noeud dans la liste, nous devons déréférencer ce pointeur, mais avant que nous puissions déréférencez, nous devons vérifier si le pointeur est nulle premier. Si c'est nul, la liste est vide, et nous devons imprimer un message, parce que la liste est vide, il n'ya pas de dernier nœud. Mais, disons que la liste n'est pas vide. Si ce n'est pas le cas, alors nous devrions ramper à travers toute la liste jusqu'à ce que nous arrivons à la dernière station de la liste, et comment pouvons-nous savoir si nous nous penchons sur le dernier nœud dans la liste? 

Eh bien, si le pointeur à côté d'un nœud est nulle, nous savons que nous sommes à la fin car le pointeur suivant dernier aurait aucun noeud suivant dans la liste pour pointer vers. C'est une bonne habitude de toujours garder pointeur à côté du dernier nœud de initialisées à null d'avoir une foncière uniformisée qui nous prévient quand nous avons atteint la fin de la liste. 

Donc, si chenilles → prochaine est nulle, rappelez-vous que la syntaxe flèche est un raccourci pour le déréférencement un pointeur vers une struct, puis en accédant son champ suivant équivalente à la maladroite: (* Crawler). Suivante. Une fois que nous avons trouvé le dernier nœud, nous voulons imprimer sur chenilles → val, la valeur du noeud courant que nous savons être la dernière. Dans le cas contraire, si nous ne sommes pas encore au dernier nœud dans la liste, nous devons passer au nœud suivant dans la liste et vérifier si c'est la dernière. Pour ce faire, nous venons de mettre notre pointeur sur chenilles pour pointer vers la prochaine valeur du nœud courant, qui est, le noeud suivant dans la liste. Cela se fait par la mise en crawler crawler = → prochaine. Ensuite, nous répétons ce processus, avec une boucle par exemple, jusqu'à ce qu'on trouve le dernier nœud. Ainsi, par exemple, si chenilles pointait à la tête, nous avons mis au point à chenilles chenilles → prochaine, qui est la même que la trame suivante de la première noeud. Donc, maintenant que notre robot se dirige vers le 2ème noeud, et, encore une fois, nous répétons cela avec une boucle, jusqu'à ce que nous avons trouvé le dernier nœud, c'est-à- où pointeur suivant du noeud pointe sur null. Et là, nous l'avons, nous avons trouvé le dernier nœud dans la liste, et d'imprimer sa valeur, nous utilisons simplement sur chenilles → val. 

Déplacement n'est pas si mal, mais ce que sur l'insertion? Disons que nous voulons insérer un entier dans la 4ème position dans une liste d'entiers. C'est entre les nœuds actuels 3e et 4e. Encore une fois, nous devons parcourir la liste juste pour accéder à la 3ème élément, celui que nous insérant après. Donc, nous créons un pointeur sur chenilles à nouveau pour parcourir la liste, vérifier si notre pointeur de tête est nulle, et si ce n'est pas le cas, pointer notre pointeur sur chenilles au nœud de tête. Donc, nous sommes au 1er élément. Nous devons aller de l'avant plus de 2 éléments avant de pouvoir insérer, afin que nous puissions utiliser une boucle for int i = 1; i <3; i + + et dans chaque itération de la boucle, progresser notre pointeur sur chenilles avant par nœud 1 en vérifiant si le champ à côté du nœud courant est nul, et si ce n'est pas le cas, déplacez le pointeur de notre robot d'exploration vers le nœud suivant en le définissant égale à pointeur suivant du nœud courant. Donc, puisque notre boucle pour dit de le faire deux fois, nous avons atteint le 3ème noeud, et une fois que notre robot d'exploration pointeur a atteint le nœud après que nous voulons insérer notre nouveau entier, comment pouvons-nous réellement ne l'insertion? 

Eh bien, notre nouvelle entier doit être inséré dans la liste dans le cadre de sa structure propre nœud, car c'est vraiment une séquence de nœuds. Donc, nous allons faire un nouveau pointeur vers le nœud appelé «nouveau_noeud, ' et réglez-le pointer vers la mémoire que nous avons maintenant allouer sur le tas pour le noeud lui-même, et combien de mémoire faut-il allouer? Eh bien, la taille d'un nœud, et nous voulons définir son champ val à l'entier que nous voulons insérer. Disons, 6. Maintenant, le nœud contient notre valeur entière. C'est aussi une bonne pratique pour initialiser champ suivant du nouveau nœud pour pointer vers null, mais maintenant, quoi? 

Nous devons changer la structure interne de la liste et les pointeurs suivants figurent dans la liste existante de Nœuds 3e et 4e. Depuis les pointeurs prochaines déterminer l'ordre de la liste, et puisque nous sommes l'insertion de notre nouveau noeud en plein milieu de la liste, il peut être un peu délicat. C'est parce que, souvenez-vous, notre ordinateur ne connaît que l'emplacement des nœuds dans la liste en raison des pointeurs stockés dans les prochains noeuds précédents. Donc, si jamais on a perdu la trace d'un de ces endroits, dire en modifiant l'un des pointeurs prochains dans notre liste, Par exemple, disons que nous avons changé champ suivant le 3ème noeud de pour pointer vers un nœud ici. Nous serions hors de la chance, parce que nous ne serions pas aucune idée où se trouve le reste de la liste, et c'est évidemment très mauvais. Donc, nous devons faire très attention à l'ordre dans lequel on manipule des pointeurs nos prochains cours de l'insertion. 

Donc, pour simplifier, disons que nos 4 premiers noeuds sont appelés A, B, C, et D, les flèches représentant la chaîne de pointeurs qui relient les nœuds. Donc, nous devons insérer notre nouveau noeud entre les noeuds C et D. Il est essentiel de le faire dans le bon ordre, et je vais vous montrer pourquoi. 

Penchons-nous sur la bonne façon de le faire en premier. Hé, nous savons que le nouveau noeud doit venir juste après C, nous allons donc positionner le pointeur à côté de C pour pointer vers nouveau_noeud. Très bien, semble correct, il suffit de finir maintenant par faire le point du nouveau nœud pointeur à côté de D, mais attendez, comment pouvons-nous le faire? La seule chose qui pouvait nous dire où D est, le pointeur suivant a été précédemment stocké dans C, mais nous avons réécrit ce pointeur pour pointer vers le nouveau nœud, de sorte que nous n'avons plus aucune idée où D est en mémoire, et nous avons perdu le reste de la liste. Pas bon du tout. 

Alors, comment pouvons-nous faire de ce droit? Tout d'abord, pointer pointeur à côté du nouveau nœud à D. Maintenant, pointeurs à la fois le nouveau nœud et C de prochaines pointent vers le même nœud, D, mais c'est très bien. Maintenant, nous pouvons pointer pointeur à côté de C au nouveau noeud. Donc, nous avons fait cela sans perdre de données. Dans le code, C est le noeud courant que la traversée pointeur pointe sur chenilles, et D est représenté par le noeud pointé par le champ suivant du noeud courant, ou sur chenilles → prochaine. Donc, nous avons d'abord positionner le pointeur à côté du nouveau nœud pour pointer vers chenilles → prochaine, de la même manière que nous avons dit pointeur suivant doit nouveau_noeud de pointer à D dans l'illustration. Ensuite, on peut positionner le pointeur à côté du nœud courant à notre nouveau noeud, tout comme nous avons dû attendre jusqu'au point C à nouveau_noeud dans le dessin. Maintenant tout est en ordre, et nous n'avons pas perdu le suivi de toutes les données, et nous avons été en mesure de simplement tenir notre nouveau nœud dans le milieu de la liste sans avoir à reconstruire le tout ou même déplacer des éléments la façon dont nous aurions dû avec un tableau de longueur fixe. 

Ainsi, les listes chaînées sont une base, mais important, de la structure de données dynamique qui ont à la fois des avantages et des inconvénients par rapport aux tableaux et d'autres structures de données, et comme c'est souvent le cas en informatique, il est important de savoir quand utiliser chaque outil, vous pouvez donc choisir le bon outil pour le bon emploi. 

Pour plus de pratique, essayez d'écrire des fonctions pour supprimer des nœuds d'une liste chaînée - n'oubliez pas de faire attention à l'ordre dans lequel vous réorganisez vos prochaines pointeurs pour vous assurer de ne pas perdre un morceau de votre liste - ou une fonction pour compter les noeuds dans une liste chaînée, ou un amusement, d'inverser l'ordre de tous les noeuds dans une liste chaînée. 

Mon nom est Jackson Steinkamp, ​​c'est CS50.