>> [Jouer de la musique]
DOUG LLOYD: Très bien.
Donc, si vous venez de terminer ce que vidéo sur les listes simplement liés désolé
Je vous ai laissé partir en peu d'un cliffhanger.
Mais je suis heureux que vous soyez ici pour terminer l'histoire d'une liste doublement chaînée.
>> Donc, si vous vous souvenez de que la vidéo, nous avons parlé
comment simplement chaînée listes font participer notre capacité
à traiter des informations où le nombre d'éléments
ou le nombre d'éléments dans une liste peut augmenter ou diminuer.
Nous pouvons maintenant faire face à quelque chose comme ça, où
nous ne pouvions pas traiter avec elle avec les tableaux.
>> Mais ils ne souffrent d'un limitation critique qui
est que, avec un seul liée liste, nous ne pouvons jamais déplacer
dans une seule direction à travers la liste.
Et la seule situation réelle où cela peut devenir un problème
était quand nous essayions de supprimer un seul élément.
Et on n'a même pas discuter de la façon de le faire dans une liste simplement chaînée en pseudo.
Il est certainement faisable, mais il peut être un peu de tracas.
Donc, si vous vous trouvez dans une situation où
vous essayez de supprimer éléments individuels de la liste
ou il va être nécessaire que vous serez supprimez
éléments simples de la liste, vous voudrez peut-
envisager d'utiliser un doublement chaînée la liste à la place d'une liste simplement chaînée.
Parce liste doublement chaînée vous permettent de déplacer les deux avant et en arrière
la liste au lieu de juste en avant à travers la films--
tout en ajoutant un élément supplémentaire à notre définition de la structure
pour le noeud de la liste doublement chaînée.
>> Encore une fois, si vous ne allez pas être la suppression d'éléments simples
de la films-- parce que nous ajoutons un champ supplémentaire à notre structure
définition, les noeuds eux-mêmes pour une liste doublement chaînée
vont être plus grande.
Ils vont prendre jusqu'à plusieurs octets de mémoire.
Et si cela est pas quelque chose vous allez avoir besoin de faire,
vous pourriez décider qu'il est ne vaut pas le compromis
avoir à dépenser le supplément octets de mémoire nécessaire
pour une liste doublement liée si vous n'êtes pas va être la suppression d'éléments simples.
Mais ils sont aussi très cool pour d'autres choses aussi.
>> Donc, comme je le disais, nous avons juste à ajouter Un seul champ de notre structure
definition-- cette notion d'un pointeur précédente.
Donc, avec une liste simplement chaînée, nous avoir la valeur et le pointeur suivante,
de sorte que la liste doublement liée vient une manière de se déplacer vers l'arrière ainsi.
>> Maintenant, dans le simplement chaînée Liste vidéo, nous avons parlé
sur ces cinq des principales choses que vous devez être
capable de faire pour travailler avec les listes chaînées.
Et pour la plupart d'entre eux, le fait qu'il est une liste doublement chaînée
est pas vraiment un grand saut.
Nous pouvons encore parcourir par tout aller de l'avant, du début à la fin.
Nous pouvons toujours créer un noeud sur l'air mince, à peu près de la même façon.
Nous pouvons supprimer les listes jolie de la même manière aussi.
Les seules choses qui sont subtilement différent,
vraiment, sont l'insertion nouveaux noeuds dans la liste,
et nous allons enfin parlons de la suppression un seul élément de la liste ainsi.
Encore une fois, à peu près les trois autres, nous sommes
ne vais pas en parler maintenant, car ils sont tout simplement
tweaks très mineurs sur les idées discutées dans la liste vidéo simplement chaînée.
>> Donc, nous allons insérer un nouveau noeud dans une liste doublement chaînée.
Nous avons parlé de faire ce pour listes simplement chaînée ainsi,
mais il ya un couple d'extra prises avec une liste doublement chaînée.
Ont été [? passant?] dans la tête de la énumérer ici et une valeur arbitraire,
et nous voulons obtenir le nouveau chef de la liste sur cette fonction.
Voilà pourquoi il renvoie une star dllnode.
Alors, quelles sont les étapes?
Ils sont, à nouveau, très similaire à des listes simplement chaînée
avec un ajout supplémentaire.
Nous voulons alloue de l'espace pour une nouvelle nœud et assurez-vous qu'il est valide.
Nous voulons combler ce noeud jusqu'à avec toutes les informations que nous
vouloir mettre dedans.
La dernière chose que nous devons l'do-- chose supplémentaire que nous devons faire, rather--
est de fixer le pointeur précédente de l'ancien chef de la liste.
Rappelez-vous que parce listes de doublement chaînée,
nous pouvons aller de l'avant et qui backwards--
signifie que chaque noeud indique effectivement à deux autres noeuds au lieu d'un seul.
Et donc nous avons besoin de fixer l'ancien chef de la liste
pour pointer vers l'arrière pour le nouveau chef de la liste chaînée, qui était quelque chose
nous ne devons pas faire avant.
Et comme avant, nous revenons juste un pointeur vers la nouvelle tête de liste.
>> Alors, voici une liste.
Nous voulons insérer 12 dans cette liste.
Notez que le schéma est légèrement différente.
Chaque nœud contient trois fields-- données, et un pointeur suivante en rouge,
et un pointeur précédente en bleu.
Rien ne vient avant le noeud 15, de sorte que son pointeur précédent est nulle.
Il est le début de la liste.
Il n'y a rien devant elle.
Et rien ne vient après le nœud 10 et il est donc pointeur suivant est nulle ainsi.
>> Ajoutons donc 12 à cette liste.
Nous avons besoin de [inaudible] l'espace pour le noeud.
Nous avons mis 12 à l'intérieur de celui-ci.
Et là encore, nous devons être vraiment attention à ne pas briser la chaîne.
Nous voulons réorganiser la pointeurs dans l'ordre correct.
Et parfois, cela pourrait mean-- comme nous le verrons en particulier
avec delete-- que nous avons une certaine pointeurs redondant, mais qui est OK.
>> Alors, que voulons-nous faire en premier?
Je recommanderais le choses que vous devriez probablement
faire sont à remplir les pointeurs de la 12 noeud avant de toucher quelqu'un d'autre.
Alors qu'est-ce 12 va pointer vers la prochaine?
15.
Ce qui vient avant le 12?
Rien.
Maintenant, nous avons rempli le informations supplémentaires dans 12
il a donc Précédent, Suivant, et la valeur.
>> Maintenant, nous pouvons avoir cette 15-- supplémentaire étape nous parlions about-- nous
peut avoir 15 points de retour à 12.
Et maintenant, nous pouvons déplacer la tête de la liste chaînée d'être aussi 12.
Donc, il est assez similaire à ce que nous ont été faites avec les listes simplement liées,
sauf pour l'étape supplémentaire de reliant la vieille tête de la liste
revenir à la nouvelle tête de liste.
>> Maintenant, nous allons supprimer définitivement un nœud d'une liste chaînée.
Alors disons que nous avons une autre fonction que
est de trouver un nœud nous voulons supprimer et nous a donné un pointeur exactement
le nœud que nous voulons supprimer.
Nous ne disons même pas l'need-- la tête est encore déclarée à l'échelle mondiale.
Nous ne devons pas la tête ici.
Tout cette fonction fait est que nous avons trouvé un pointeur exactement à la nous node
veulent se débarrasser de.
Mettons-nous en débarrasser.
Il est beaucoup plus facile avec listes doublement liée.
First-- il est fait seulement une ou deux choses.
Nous avons juste besoin de fixer les environs Les pointeurs de noeuds afin qu'ils sauter
le nœud nous voulons supprimer.
Et puis nous pouvons supprimer ce nœud.
Encore une fois, nous allons tout simplement par ici.
Nous avons apparemment décidé que nous voulons supprimer le nœud X.
Et encore une fois, ce que je suis faire ici-- par le way--
est un cas général pour une noeud qui se trouve au milieu.
Il ya un couple de mises en garde supplémentaires que vous
besoin de considérer lorsque vous supprimez le début de la liste
ou la fin de la liste.
Il ya un couple de spéciale cas de coin pour faire face aux il.
>> Donc, cela fonctionne pour supprimer un nœud au milieu de l'une films-- que
a un pointeur légitime de l'avant et un pointeur légitime vers l'arrière,
légitime pointeur précédent et suivant.
Encore une fois, si vous travaillez avec les extrémités, vous
besoin de gérer les un peu différemment,
et on ne va pas à parler que maintenant.
Mais vous pouvez probablement déterminer ce qui doit
à faire juste en regardant cette vidéo.
>> Donc, nous avons isolé X. X est le noeud nous voulons supprimer de la liste.
Qu'est-ce qu'on fait?
Tout d'abord, nous devons réorganiser les pointeurs à l'extérieur.
Nous devons réorganiser 9 est à côté de sauter plus de 13
et le point à qui 10-- est ce que nous venons de faire.
Et nous devons aussi réorganiser de 10 précédente
signaler à 9 au lieu de pointer à 13.
>> Encore une fois, ce fut la schéma pour commencer.
Ce fut notre chaîne.
Nous avons besoin de sauter plus de 13, mais nous devons aussi préserver
l'intégrité de la liste.
Nous ne voulons pas perdre tout l'information dans les deux sens.
Donc, nous devons réorganiser les pointeurs soigneusement
afin de ne pas rompre la chaîne du tout.
>> Donc nous pouvons dire pointeur de 9 Suivant des points au même endroit
que de treize Suivant pointeur souligne dès maintenant.
Parce que nous sommes finalement va vouloir sauter par-dessus 13.
Alors, où 13 points suivante, vous veulent neuf à y pointer la place.
Alors voilà.
Et puis, où 13 points de retour à, tout ce qui vient avant le 13,
nous voulons 10 pour pointer pour qu'au lieu de 13.
Maintenant, remarquez, si vous suivez les flèches, on peut déposer 13
sans perdre effectivement toute information.
Nous avons gardé l'intégrité de la liste, le déplacement vers l'avant et vers l'arrière.
Et puis nous pouvons juste une sorte de nettoyer un peu
en tirant la liste ensemble.
Donc, nous avons réorganisé le pointeurs de chaque côté.
Et puis nous avons libéré l'X qui contenait noeud 13,
et nous ne brisons pas la chaîne.
Donc nous avons fait bonne.
>> Note finale ici, sur les listes chaînées.
Donc, à la fois par des liaisons simples et doublement chaînée listes, comme nous l'avons vu,
soutien insertion réellement efficace et la suppression d'éléments.
Vous pouvez très bien le faire il en temps constant.
Qu'avons-nous avons à faire pour supprimer un élément juste une seconde il ya?
Nous avons déménagé un pointeur.
Nous avons déménagé une autre pointeur.
Nous avons libéré X- a fallu trois opérations.
Il faut toujours trois opérations à supprimer cette node-- pour libérer un noeud.
>> Comment pouvons-nous insérons?
Eh bien, nous sommes juste toujours vireur sur le début
si nous voulons insérer efficacement.
Nous devons donc rearrange-- en fonction de si elle est
une des liaisons simples ou doublement chaînée liste, nous pourrions avoir besoin de faire trois
ou quatre opérations max.
Mais encore une fois, il est toujours trois ou quatre.
Il n'a pas d'importance combien de éléments sont dans notre liste,
il est toujours trois ou quatre operations-- tout comme la suppression est toujours
trois ou quatre opérations.
Il est temps constant.
Voilà donc vraiment super.
>> Avec des tableaux, nous faisions quelque chose comme le tri par insertion.
Vous vous souvenez sans doute que l'insertion Trier est pas un algorithme de temps constant.
Il est en fait assez cher.
Donc, cela est beaucoup mieux pour l'insertion.
Mais comme je l'ai mentionné dans le simplement chaînée liste vidéo,
nous avons ici un inconvénient aussi, non?
Nous avons perdu la capacité de accéder au hasard éléments.
Nous ne pouvons pas dire, je veux élément numéro quatre ou numéro de l'élément 10 d'une liste chaînée
de la même manière que nous pouvons le faire avec un tableau
Ou nous pouvons simplement directement index dans l'élément de notre gamme.
>> Et donc essayer de trouver un élément dans une films-- liée
si la recherche est important-- peut maintenant prendre le temps linéaire.
Comme la liste est longue, plus il pourrait prendre une étape supplémentaire
pour chaque élément dans la liste Afin de trouver ce que nous cherchons.
Donc, il ya des arbitrages.
Il ya un peu d'un pro et con élément ici.
>> Et une liste doublement chaînée ne sont pas les dernier type de combinaison de structure de données
que nous allons parler, prenant tout l'édifice de base
C un des blocs de mettre ensemble.
Car en fait, nous pouvons même faire mieux que cela
à créer une structure de données qui vous pourriez être en mesure de chercher dans
en temps constant aussi.
Mais plus que dans une autre vidéo.
>> Je suis Doug Lloyd.
Ceci est CS50.