[Jouer de la musique] 

DOUG LLOYD: OK, donc au ce point dans le cours, nous avons couvert un grand nombre de bases de C. Nous savons beaucoup de choses sur les variables, les tableaux, pointeurs, toutes ces bonnes choses. Ceux-ci sont toutes sortes de bâti pour voir que les fondamentaux, mais nous pouvons faire plus, non? Nous pouvons combiner les choses ensemble de manière intéressante. 

Et nous allons donc le faire, nous allons commencer à se ramifier de ce qui C nous donne, et commencer à créer nos propres données structures utilisant ces bâtiments blocs ensemble pour faire quelque chose vraiment précieuse, utile. Une façon nous pouvons faire est pour parler de collections. Donc, jusqu'à présent, nous avons eu un type de données Structure pour représenter collections d'aimer valeurs, des valeurs similaires. Ce serait un tableau. Nous avons collections d'entiers, ou collections de caractères et ainsi de suite. 

Structures sont également une sorte de données la structure de collecte d'informations, mais pas pour la collecte comme valeurs. Il mêle généralement différents types de données ensemble à l'intérieur d'une seule boîte. Mais il ne se utilisé pour enchaîner ou connecter ensemble similaire articles, comme un tableau. Les tableaux sont grands pour élément regarder, mais le rappel qu'il est très difficile à insérer dans un tableau, à moins que nous insérer au la fin de ce tableau. 

Et le meilleur exemple que je possède pour ce qui est le tri par insertion. Si vous vous rappelez notre vidéo le tri par insertion, il y avait beaucoup de frais engagés pour avoir pour ramasser des éléments, et de les transférer sur la façon de tenir quelque chose dans le milieu de votre tableau. Tableaux souffrent également d'un autre problème, qui est l'inflexibilité. Lorsque nous déclarons un tableau, nous obtenons un coup à elle. Nous apprenons à dire, je veux ce nombre d'éléments. Peut-être 100, il pourrait être de 1000, il pourrait x où x est un nombre qui est l'utilisateur nous a donné à une invite ou à la commande ligne. 

Mais nous obtenons un seul projectile à lui, nous ne reçois pas de dire alors Oh, en fait je 101 nécessaire, ou je devais x plus 20. Trop tard, nous avons déjà déclaré la tableau, et si nous voulons obtenir 101 ou x plus 20, nous avons à déclarer un tableau tout à fait différent, copier tous les éléments de la matrice plus, et ensuite nous en avons assez. Et si nous sommes à nouveau mal, ce qui si nous avons réellement besoin 102, ou 40 x plus, nous devons le faire à nouveau. Donc ils sont très inflexible pour redimensionner nos données, mais si nous combinons réuni certains des bases que nous avons déjà appris sur les pointeurs et les structures, en particulier en utilisant la mémoire dynamique répartition avec malloc, nous peut mettre ces pièces ensemble pour créer une de nouvelles données isolément liste nous pourrions say-- liée qui nous permet de grandir et de réduire une collection de valeurs et nous ne serons pas avoir d'espace perdu. 

Encore une fois, nous appelons cette idée, cette notion, une liste chaînée. En particulier, dans cette vidéo, nous sommes parler de la liste chaînée, puis une autre vidéo nous allons parler listes propos doublement chaînées, qui est juste une variation sur un thème ici. Mais une liste chaînée est constitué de noeuds, nœuds juste être un term-- abstraite il est juste quelque chose que je vais appeler qui est une sorte de la structure, au fond, je suis? Tout va appeler cela un node-- et cela noeud a deux membres, ou deux domaines. Il dispose de données, généralement un entier, un flotteur de caractère, ou peut être un autre type de données que vous avez défini avec un def type. Et il contient un pointeur vers un autre noeud du même type. 

Nous avons donc deux choses à l'intérieur de ce nœud, les données et un pointeur à un autre noeud. Et si vous commencez à visualiser cela, vous pouvez penser comme une chaîne de nœuds sont reliés entre eux. Nous avons le premier noeud, il contient des données, et un pointeur au second noeud, qui contient données, et un pointeur vers le troisième noeud. Et voilà pourquoi nous l'appelons un liste chaînée, ils sont reliés entre eux. 

Qu'est-ce que cette spéciale structure de noeud ressembler? Eh bien, si vous vous souvenez de notre vidéo sur la définition des types personnalisés, avec le type def, nous pouvons définir une structure-- et tapez définir une structure de ce type. tyepdef struct sllist, et puis je suis en utilisant la valeur de mot ici arbitrairement pour indiquer quel type de données vraiment. Vous pourriez passer un nombre entier ou un flotteur, vous pourriez avoir ce que vous voulez. Ça ne se limite pas à un peu entiers, ou quelque chose comme ça. Donc, la valeur est juste un arbitraire Type de données et puis un pointeur à un autre noeud du même type. 

Maintenant, il ya un peu de captures ici avec une structure définissant quand il est une structure auto-référentielle. Je dois avoir un temporaire nom pour ma structure. A la fin de la journée, je veulent clairement appeler noeud SLL, qui est en fin de compte la nouvelle nommer une partie de ma définition de type, mais je ne peux pas utiliser le noeud de SLL au milieu de ce produit. La raison étant, je ne ai pas créé un noeud de SLL de type appelé jusqu'à ce que je frappe ce dernier point ici. Jusqu'à ce point, je dois avoir un autre moyen de se référer à ce type de données. 

Et cela est une auto référentielle type de données. Il; s un type de données une structure qui contient des données, et un pointeur vers un autre structure du même type. Donc, je dois être en mesure de se référer à ce type de données au moins temporairement, de sorte qu'il donne un temporaire nom de struct sllist me permet de dire alors je veux un pointeur vers une autre structure sllist, une étoile struct sllist, puis après que je l'ai terminé la définition, Je peux maintenant appeler ce type d'un noeud de SLL. 

Voilà pourquoi vous voyez il ya un nom temporaire ici, mais un nom permanent ici. Parfois, vous pourriez voir les définitions de structure, par exemple, qui ne sont pas autoréférentiel, que ne pas avoir un nom de spécificateur ici. Il serait tout simplement dire typedef struct, ouvrir accolade, puis le définir. Mais si vous êtes struct est auto référentielle, que celui-ci est, vous devez spécifier un nom de type temporaire. Mais finalement, maintenant que nous avons fait cela, nous pouvons tout simplement se référer à ces nœuds, ces unités, en tant que noeuds à des fins SLL du reste de cette vidéo. 

Très bien, alors nous savons comment créer un nœud de liste chaînée. Nous savons comment définir un nœud de liste chaînée. Maintenant, si nous allons commencer les utiliser pour recueillir des informations, il ya un couple d'opérations nous besoin de comprendre et de travailler avec. Nous devons savoir comment créer une liste liée de l'air mince. Si il n'y a pas de liste déjà, nous voulons commencer un. Donc, nous devons être en mesure pour créer une liste chaînée, nous devons rechercher sans doute à travers la liste de liens pour trouver un élément que nous recherchons. Nous devons être en mesure d'insérer de nouvelles choses dans la liste, nous voulons que notre liste pour être en mesure de croître. Et de même, nous voulons être en mesure de supprimer les choses de notre liste, nous voulons que notre liste pour être en mesure de se rétrécir. Et à la fin de notre des programmes, en particulier si vous vous rappelez que nous sommes allocation dynamique de mémoire pour construire ces listes généralement, nous voulons libérer tous que la mémoire quand nous aurons fini de travailler avec elle. Et donc nous devons être en mesure de supprimer une toute liste liée à un échec coup. Donc, nous allons passer par certaines de ces opérations et comment nous pourrions les visualiser, parler en code pseudo spécifiquement. Donc, nous voulons créer un liste chaînée, alors peut-être nous vouloir définir une fonction avec ce prototype. SLL noeud étoiles, créer, et je suis de passage dans un argument, certaines données arbitraires tapez à nouveau, d'un certain type de données arbitraires. Mais je dois returning-- cette fonction revenez me voir un pointeur, à un seul nœud de liste chaînée. Encore une fois, nous essayons de créer une liste liée de l'air mince, donc je besoin d'un pointeur vers cette liste quand je suis fait. 

Alors, quelles sont les étapes à suivre ici? Eh bien, la première chose que je suis va faire est dynamiquement allouer de l'espace pour un nouveau noeud. Encore une fois, nous créons hors de minces l'air, nous avons donc besoin d'espace de malloc pour elle. Et bien sûr, immédiatement après que nous malloc, nous vérifions toujours de faire en sorte que notre pointer-- on n'a pas eu de retour nul. Parce que si nous essayons de déférence un pointeur NULL, nous allons souffrir d'une Segfault et nous ne voulons pas que. 

Ensuite, nous voulons remplir dans le domaine, nous voulons initialiser le champ de valeur et initialiser le champ suivant. Et puis nous voulons to-- finalement que le prototype de fonction indicates-- nous voulons pour retourner un pointeur vers un noeud de SLL. Alors, que faire cela ressemble visuellement? Eh bien, d'abord, nous allons dynamiquement allouer de l'espace pour un nouveau nœud de SLL, donc nous voilà malloc-- une représentation visuelle du nœud nous venons de créer. Et nous vérifions pour vous assurer ça ne null-- dans ce cas, l'image ne serait pas montré jusqu'à si elle était nulle, nous aurions à court de mémoire, Nous sommes donc bien d'y aller. Alors maintenant, nous sommes à l'étape C, initialiser le champ de valeur nœuds. Eh bien, sur la base de cette fonction Je l'appelle à l'aide ici, on dirait que je veux passer à 6, Alors je vais 6 dans le champ de valeur. Maintenant, initialiser le champ suivant. Eh bien, que vais-je faire là-bas, il n'y a rien à côté, à droite, ceci est la seule chose dans la liste. Alors, quelle est la prochaine chose dans la liste? 

Il ne devrait pas pointer vers quelque chose, droite. Il n'y a rien d'autre, si ce qui est le concept que nous savons de qui est nothing-- pointeurs à rien? Il devrait être peut-être que nous voulons de mettre un pointeur nul là-bas, et je représente la null pointeur comme juste une boîte rouge, nous ne pouvons pas aller plus loin. Comme nous le verrons un peu plus tard, nous aurons éventuellement des chaînes des flèches de liaison ces noeuds ensemble, mais quand vous frappez la boîte rouge, qui est nulle, nous ne pouvons pas aller plus loin, qui est la fin de la liste. 

Et enfin, nous voulons juste retourner un pointeur vers ce nœud. Donc, nous allons appelons nouvelle, et sera de retour nouvelle de sorte qu'il peut être utilisé dans quelle que soit la fonction créée. Donc là, nous allons, nous avons créé un seul nœud de liste liée de l'air mince, et maintenant nous avons une liste nous pouvons travailler avec. 

Maintenant, disons que nous avons déjà avoir une grande chaîne, et nous voulons trouver quelque chose en elle. Et nous voulons une fonction qui va retourner true ou false, selon si une valeur existe dans cette liste. Un prototype de fonction, ou déclaration pour cette fonction, pourrait ressembler this-- Bool trouver, et alors nous voulons transmettre dans deux arguments. 

Le premier est un pointeur sur la le premier élément de la liste chaînée. Ceci est en fait quelque chose que vous toujours envie de garder une trace de, et effectivement peut-être quelque chose qui même de mettre dans une variable globale. Une fois que vous créez une liste, vous toujours, toujours voulez garder une trace de la très premier élément de la liste. De cette façon, vous pouvez vous référer à tous les autres éléments en suivant simplement la chaîne, sans avoir à garder pointeurs intacte pour chaque élément. Vous avez seulement besoin de garder une trace de la première un si ils sont tous enchaînés. 

Et puis la deuxième chose nous passons à nouveau est some-- arbitrairement quel que soit le type de données que nous sommes la recherche car il est à l'intérieur de Heureusement, un des nœuds de la liste. Alors, quelles sont les étapes? Eh bien, la première chose que nous faisons est nous créons un pointeur transversal pointant à la tête des listes. Eh bien, pourquoi le faisons-nous, nous avons déjà avoir un pointeur à la tête des listes, pourquoi ne nous contentons pas de déplacer que personne autour? Eh bien, comme je viens de le dire, il est vraiment important pour nous de toujours garder la trace de la très premier élément dans la liste. Et il est donc fait mieux pour créer un double de ce que, et l'utiliser pour se déplacer de sorte que nous ne déplacer accidentellement loin, ou nous avons toujours avoir un pointeur à un point qui est à droite sur le premier élément de la liste. Donc, il est préférable de créer un seconde que nous utilisons pour se déplacer. 

Puis nous comparons simplement si le champ de valeur à ce noeud est ce que nous recherchons, et si elle est pas, nous passons juste pour le noeud suivant. Et nous continuons à faire ce que Encore et encore et encore, jusqu'à ce que nous trouvons l'élément, ou nous avons touché null-- nous avons atteint la fin de la liste et il n'y est pas. Cela devrait nous l'espérons sonner une cloche à vous comme simplement la recherche linéaire, nous ne faisons que reproduire dans une structure de liste chaînée au lieu d'utiliser un tableau pour le faire. 

Alors, voici un exemple de une liste chaînée. Celui-ci se compose de cinq nœuds, et nous avons un pointeur vers la tête de la liste, qui est appelé liste. La première chose que nous voulons faire est à nouveau, créer ce parcours pointeur. Donc, nous avons maintenant deux pointeurs ce point à la même chose. 

Maintenant, remarquez ici aussi, je ne l'ai pas avoir à malloc tout espace pour trav. Je ne dis pas trav égale malloc quelque chose, ce nœud existe déjà, que l'espace dans la mémoire existe déjà. Donc, tout ce que je suis en train de faire est création d'un autre pointeur vers elle. Je ne suis pas allouer de l'supplémentaires espace, venons de deux pointeurs pointant vers la même chose. 

Donc, est-ce que 2 je cherche? Eh bien, non, donc je suis à la place passer à la suivante. Donc, fondamentalement, je dirais, trav trav est égal suivante. Est de 3 ce que je suis à la recherche, non. Je continue donc à aller à travers, jusqu'à ce que finalement arrive à 6, qui est ce que je suis à la recherche pour la base de l'appel de fonction Je dois au sommet là, et je suis fait. 

Maintenant, si l'élément que je suis cherchez est pas dans la liste, est ce que ça va encore travailler? Eh bien, vous remarquerez que la liste ici est subtilement différent, et ceci est une autre chose qui est importante avec les listes chaînées, vous ne disposez pas de préserver les dans un ordre particulier. Vous pouvez si vous le voulez, mais vous avez peut-être déjà remarqué que nous ne sommes pas garder la trace de ce que l'élément numéro nous en sommes. 

Et qui est en quelque sorte d'un commerce que nous avoir avec liste chaînée versets tableaux, est-ce nous ne disposons pas accès aléatoire plus. Nous ne pouvons pas simplement dire que je veux pour aller à l'élément 0, ou le sixième élément de ma matrice, que je peux faire dans un tableau. Je ne peux pas dire que je veux aller à la Élément 0, ou le 6ème élément, ou l'élément 25 de ma liste chaînée, il n'y a aucun indice associé avec eux. Et donc il n'a pas vraiment d'importance si nous préservons notre liste dans l'ordre. Si vous voulez vous Certainement, mais il ya aucune raison pourquoi ils doivent être conservé dans un ordre quelconque. Encore une fois, nous allons essayer de trouver 6 dans cette liste. Eh bien, nous commençons à la en commençant, nous ne trouvons pas 6, puis nous continuons à ne pas trouver 6, jusqu'à ce que nous obtenons ici. Donc points de droit maintenant trav au noeud contenant 8, et six est pas là. 

Donc, la prochaine étape serait pour aller à la prochaine pointeur, donc dire trav trav égale prochaine. Eh bien, trav côté, indiqué par la boîte rouge, il est nul. Donc il n'y a nulle part ailleurs où aller, et donc à ce stade nous pouvons conclure que nous avons atteint la fin de la liste liée, et 6 est pas là. Et il serait renvoyé faux dans ce cas. 

OK, comment pouvons-nous insérons un nouveau noeud dans la liste chaînée? Donc, nous avons été en mesure de créer une liste liée de nulle part, mais nous voulons probablement construire une chaîne et non créer un tas de listes distinctes. Nous voulons avoir une seule liste qui a un tas de noeuds en elle, pas un tas de listes avec un seul nœud. Donc, nous ne pouvons pas continuer à utiliser l'Créer fonction, nous avons défini plus tôt, maintenant nous vouloir insérer dans un liste qui existe déjà. 

Donc ce cas, nous allons de passer en deux arguments, le pointeur à la tête de cette liste que nous voulons ajouter à lié. Encore une fois, voilà pourquoi il est si important que nous avons toujours garder une trace de celui-ci, parce il est la seule façon vraiment se référer à l'ensemble de la liste est simplement par un pointeur vers le premier élément. Donc, nous voulons transmettre dans un pointeur vers ce premier élément, et quelle que soit la valeur que nous vouloir ajouter à la liste. Et finalement, cette fonction va retourner un pointeur à la nouvelle tête d'une liste chaînée. 

Quelles sont les étapes à suivre ici? Eh bien, tout comme avec créer, nous avons besoin d'allouer dynamiquement espace pour un nouveau noeud, et assurez- sûr que nous ne courons pas de mémoire, encore une fois, parce que nous sommes avec malloc. Ensuite, nous voulons remplir et insérez le noeud, alors mettez le nombre, quel que soit val est, dans le nœud. Nous voulons insérer le nœud à le début de la liste chaînée. 

Il ya une raison que je vouloir faire cela, et il pourrait être utile de prendre un second pour mettre en pause la vidéo ici, et de réfléchir à la raison pour laquelle je voudrais insérer au début d'une lié liste. Encore une fois, je l'ai mentionné plus tôt qu'il n'a pas vraiment Peu importe si nous préservons dans toute Afin, donc peut-être qui est un indice. Et vous avez vu ce qui se passerait si nous voulu to-- ou d'une seconde Il ya quand nous allions grâce à la recherche que vous pourraient voir ce qui pourrait passerait-il si nous essayions à insérer à la fin de la liste. Parce que nous ne disposons pas d'un pointeur vers la fin de la liste. 

Donc la raison pour laquelle je ne voudrais à insérer au début, est parce que je peux le faire immédiatement. Je dois un pointeur au début, et nous verrons cela dans un visuel dans une seconde. Mais si je veux insérer à la fin, Je dois commencer par le commencement, parcourir tout le chemin à la fin, puis virer sur. Donc, cela voudrait dire que l'insertion, à la fin de la liste deviendrait une des n o opération, revenir à notre discussion sur complexité de calcul. Il était devenu un des n o opération, où que la liste est devenu plus grand et plus gros, et plus grand, il va devenir de plus en plus difficile de virer de bord quelque chose sur à la fin. Mais il est toujours très facile à virer quelque chose sur au début, vous êtes toujours au début. 

Et nous allons voir un visuel de ce nouveau. Et puis une fois que nous aurons terminé, une fois nous avons inséré le nouveau nœud, nous voulons revenir à notre pointeur la nouvelle tête d'une liste chaînée, qui puisque nous sommes à l'insertion en commençant, sera effectivement un pointeur vers le nœud nous venons de créer. Disons Visualiser cette, parce que je pense que ça va aider. 

Alors, voici notre liste, il se compose de quatre éléments, contenant un noeud 15, qui pointe vers un noeud contenant neuf, qui des points à un noeud contenant 13, qui pointe vers un noeud contenant 10, qui a la null pointeur comme sa prochaine pointeur Voilà donc la fin de la liste. Donc, nous voulons insérer un nouveau noeud avec la valeur 12 au début de cette liste, que faisons-nous? Eh bien, d'abord, nous malloc espace pour le noeud, et puis nous avons mis 12 là-dedans. 

Alors maintenant, nous avons atteint un point de décision, non? Nous avons un couple de pointeurs que nous pourrions déplacer, ce qui devrait nous faire le premier pas? Devrions-nous faire 12 points à le nouveau chef de l'films-- ou excusez-moi, devrions-nous faire 12 signaler à l'ancien chef de la liste? Ou devrions-nous dire que le liste commence maintenant à 12. Il ya une distinction là, et nous regarderons ce qui se passe à la fois en une seconde. 

Mais cela conduit à une grand sujet pour la barre latérale, qui est celui de la plus délicates choses avec les listes chaînées est d'arranger les pointeurs dans le bon ordre. Si vous déplacez les choses de l'ordre, vous pouvez vous retrouver accidentellement orphelins le reste de la liste. Et voici un exemple de cela. Allons donc avec l'idée de-- Eh bien, nous venons de créer 12. Nous savons 12 va être le nouveau chef de la liste, et alors pourquoi ne nous avançons pas seulement le pointeur de liste pour y pointer. 

OK, ce qui est bien. Alors maintenant d'où vient 12 prochain point? Je veux dire, nous pouvons voir visuellement ce qu 'il pointera à 15, comme les humains, il est vraiment évident pour nous. Comment l'ordinateur sait? Nous ne disposons pas quoi que ce soit pointant à 15 plus, non? 

Nous avons perdu toute capacité à se référer à 15. Nous ne pouvons pas dire nouvelle flèche à côté égaux quelque chose, il n'y a rien là-bas. En fait, nous avons orphelins le reste de la liste ce faisant, nous avons accidentellement brisé la chaîne. Et nous ne voulons certainement pas faire cela. 

Donc, nous allons revenir et essayer encore une fois. Peut-être la bonne chose à faire est de fixer le pointeur suivant de 12 à l'ancien chef de la première liste, alors nous pouvons nous déplacer sur la liste. Et de fait, qui est la bon ordre que nous nécessité de suivre lorsque nous sommes travailler avec la liste chaînée. Nous voulons toujours connecter la nouvel élément dans la liste, avant de prendre ce genre de étape importante de l'évolution où le chef de la liste chaînée est. Encore une fois, que ce soit une chose fondamentale, nous ne voulons pas perdre la trace. 

Donc, nous voulons faire en sorte que tout est enchaîné ensemble, avant de passer ce pointeur. Et alors ce serait le bon ordre, qui est de connecter 12 à la liste, puis dire que la liste commence un 12. Si nous dit que la liste commence à 12 et alors essayé de se connecter 12 à la liste, nous avons déjà vu ce qui se passe. Nous perdons la liste par erreur. 

OK, donc plus qu'une chose à parler. Que faire si nous voulons pour se débarrasser de toute une liste liée à la fois? Encore une fois, nous allons allouer de tout cet espace, et nous besoin de libérer quand nous aurons fini. Alors maintenant, nous voulons supprimer toute la liste chaînée. Eh bien, que voulons-nous faire? 

Si nous avons atteint le pointeur NULL, nous vouloir arrêter, sinon, il suffit de supprimer le reste de la liste, puis me libérer. Supprimer le reste de la liste, puis libérer le noeud courant. Qu'est-ce que cela ressemble, quelle technique avons nous avons parlé fait précédemment à propos de ce que cela ressemble? Supprimer tout le monde, puis revenir et supprimer moi. 

Voilà la récursivité, nous avons fait la problème d'un peu plus petit, nous disons supprimer tout le monde d'autre, alors vous pouvez me supprimer. Et plus loin sur la route, ce noeud diront, supprimez tout le monde. Mais finalement, nous allons arriver à la point où la liste est nulle, et voilà notre scénario de base. 

Donc, nous allons jeter un oeil à cela, et comment cela pourrait fonctionner. Alors, voici notre liste, il est le même liste que nous venons de parler, et il ya les étapes. Il ya beaucoup de texte ici, mais Espérons que la visualisation aidera. 

Donc, nous have-- et je également tiré notre cadres de pile illustration de notre vidéo sur des piles d'appels, et nous espérons que tout cela ainsi va vous montrer ce qui se passe. Alors, voici notre code pseudo. Si nous arrivons à un null pointeur, arrêtez, sinon, supprimer le reste de la liste, puis libérer le noeud courant. Donc maintenant, films-- le pointeur que nous sommes passant de détruire des points à 12. 12 est pas un pointeur NULL, donc nous sommes va supprimer le reste de la liste. 

Ce qui est la suppression de la reste d'entre nous impliqués? Eh bien, cela signifie faire un appeler à détruire, en disant 15 qui est le début de la reste de la liste que nous voulons détruire. Et si l'appel à détruire 12 est une sorte de en attente. Il y est gelé, en attendant le appeler à détruire 15, pour terminer son travail. 

Eh bien, 15 est pas un pointeur NULL, et donc il va dire, tout droit, ainsi, supprimer le reste de la liste. Le reste de la liste commence à 9, et donc nous allons simplement attendre jusqu'à ce que vous supprimez tout ce qui des trucs, puis revenir et supprimer moi. Eh bien 9 qui va se dire, eh bien, Je ne suis pas un pointeur NULL, donc supprimer le reste de la liste à partir d'ici. Et donc essayer de détruire 13. 13 dit, je ne suis pas pointeur NULL, même chose, il renvoie la balle. 10 ne pointeur NULL, 10 contient un pointeur NULL, mais 10 est pas en soi une pointeur NULL en ce moment, et il renvoie la balle trop. 

Et maintenant, la liste des points là, il serait vraiment pointer vers some-- si je devais plus d'espace dans l'image, il rappelle à l'espace aléatoire que nous ne savons pas ce qu'il est. Il est le pointeur NULL si, la liste est littéralement maintenant réglée, il est des valeurs nulles. Il est pointant vers la droite dans cette boîte rouge. Nous avons atteint un pointeur NULL, donc nous pouvons nous arrêter, et nous allons faire. 

Et pour que purple frame est maintenant-- au haut de stack-- qui est du cadre actif, mais il l'a fait. Si nous avons atteint un pointeur NULL, arrêter. Nous ne faisons rien, nous ne peut pas libérer un pointeur NULL, nous ne sommes pas tout malloc espace, et donc nous avons fini. Alors que cadre de fonction est détruit, et nous resume-- nous ramassons où nous avons laissé off avec le plus élevé suivant une, qui est ce cadre bleu foncé ici. Donc, nous ramassons là où nous nous sommes quittés. Nous avons supprimé le reste de la liste déjà, alors maintenant nous sommes va libérer les noeuds de courant. Alors maintenant, nous pouvons libérer ce noeud, et maintenant nous avons atteint la fin de la fonction. Et pour que cadre de fonction est détruite, et nous chercher à le bleu clair. 

Donc, il says-- Je l'ai déjà done-- de supprimer le reste de la liste, de sorte libérer le noeud courant. Et maintenant le cadre jaune est retour au sommet de la pile. Et comme vous le voyez, nous sommes maintenant détruire la liste de droite à gauche. 

Que serait-il arrivé, si, si nous avions fait les choses dans le mauvais sens? Tout comme quand nous avons essayé à ajouter un élément. Si nous foiré la chaîne, si nous ne relions pas les pointeurs dans le bon ordre, si nous juste libéré du premier élément, si nous avons juste libéré les tête de la liste, maintenant nous aurait aucun moyen de se référer à le reste de la liste. Et si nous aurions tout orphelins, nous aurions eu ce qui est appelé une fuite de mémoire. Si vous vous souvenez de notre vidéo sur l'allocation dynamique de la mémoire, ce ne est pas très bonne chose. 

Donc, comme je le disais, il Plusieurs opérations que nous devons utiliser pour travailler avec liste liée de manière efficace. Et vous avez peut-être remarqué que je omis un, la suppression d'un élément unique à partir d'un lien liste. La raison pour laquelle je l'ai fait est il est en fait assez difficile de penser à la façon de supprimer un seul élément à partir d'un seul liste chaînée. Nous devons être en mesure de sauter quelque chose dans la liste, qui signifie que nous arrivons à un nous point-- vouloir supprimer ce node-- mais dans le but de faire en sorte que nous ne perdez aucune information, nous avons besoin de connecter ce noeud plus ici, ici. 

Donc, je l'ai fait de mal sans doute à partir d'un point de vue visuel. Donc, nous sommes au début de notre liste, nous allons procéder par le biais, nous voulons supprimer ce noeud. Si nous venons de supprimer, nous avons brisé la chaîne. Ce nœud ici se réfère à tout le reste, il contient la chaîne à partir de maintenant. 

Donc, ce que nous devons faire effectivement après nous arrivons à ce point, est que nous devons prendre du recul un, et connecter ce noeud plus à ce nœud, afin que nous puissions ensuite supprimer l'une au milieu. Mais les listes simplement liés ne le font pas nous fournir un moyen de revenir en arrière. Nous devons donc soit conserver deux pointeurs, et les déplacer sorte d'étape au large, les uns derrière les d'autres que nous allons, ou arrivez à un point puis envoyer un autre pointeur à travers. Et comme vous pouvez le voir, il peut obtenir un peu désordonné. Heureusement, nous avons une autre façon de résoudre cela, lorsque nous parlons de listes doublement chaînées. 

Je suis Doug Lloyd, cela est CS50.