1
00:00:00,000 --> 00:00:03,381
>> [Jouer de la musique]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Très bien.

4
00:00:05,520 --> 00:00:07,860
Donc, si vous venez de terminer ce que
vidéo sur les listes simplement liés désolé

5
00:00:07,860 --> 00:00:09,568
Je vous ai laissé partir en
peu d'un cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Mais je suis heureux que vous soyez ici pour terminer
l'histoire d'une liste doublement chaînée.

7
00:00:12,790 --> 00:00:15,250
>> Donc, si vous vous souvenez de
que la vidéo, nous avons parlé

8
00:00:15,250 --> 00:00:18,500
comment simplement chaînée
listes font participer notre capacité

9
00:00:18,500 --> 00:00:22,090
à traiter des informations
où le nombre d'éléments

10
00:00:22,090 --> 00:00:24,442
ou le nombre d'éléments dans
une liste peut augmenter ou diminuer.

11
00:00:24,442 --> 00:00:26,400
Nous pouvons maintenant faire face à
quelque chose comme ça, où

12
00:00:26,400 --> 00:00:28,310
nous ne pouvions pas traiter avec elle avec les tableaux.

13
00:00:28,310 --> 00:00:30,560
>> Mais ils ne souffrent d'un
limitation critique qui

14
00:00:30,560 --> 00:00:33,790
est que, avec un seul liée
liste, nous ne pouvons jamais déplacer

15
00:00:33,790 --> 00:00:36,200
dans une seule direction à travers la liste.

16
00:00:36,200 --> 00:00:39,010
Et la seule situation réelle
où cela peut devenir un problème

17
00:00:39,010 --> 00:00:41,250
était quand nous essayions de
supprimer un seul élément.

18
00:00:41,250 --> 00:00:46,000
Et on n'a même pas discuter de la façon de le faire
dans une liste simplement chaînée en pseudo.

19
00:00:46,000 --> 00:00:48,797
Il est certainement faisable, mais
il peut être un peu de tracas.

20
00:00:48,797 --> 00:00:50,630
Donc, si vous vous trouvez
dans une situation où

21
00:00:50,630 --> 00:00:53,175
vous essayez de supprimer
éléments individuels de la liste

22
00:00:53,175 --> 00:00:55,430
ou il va être nécessaire
que vous serez supprimez

23
00:00:55,430 --> 00:00:57,970
éléments simples de
la liste, vous voudrez peut-

24
00:00:57,970 --> 00:01:02,090
envisager d'utiliser un doublement chaînée
la liste à la place d'une liste simplement chaînée.

25
00:01:02,090 --> 00:01:06,320
Parce liste doublement chaînée vous permettent
de déplacer les deux avant et en arrière

26
00:01:06,320 --> 00:01:09,340
la liste au lieu de
juste en avant à travers la films--

27
00:01:09,340 --> 00:01:13,950
tout en ajoutant un élément supplémentaire
à notre définition de la structure

28
00:01:13,950 --> 00:01:16,690
pour le noeud de la liste doublement chaînée.

29
00:01:16,690 --> 00:01:19,770
>> Encore une fois, si vous ne allez pas
être la suppression d'éléments simples

30
00:01:19,770 --> 00:01:24,810
de la films-- parce que nous ajoutons
un champ supplémentaire à notre structure

31
00:01:24,810 --> 00:01:28,340
définition, les noeuds eux-mêmes
pour une liste doublement chaînée

32
00:01:28,340 --> 00:01:29,550
vont être plus grande.

33
00:01:29,550 --> 00:01:31,600
Ils vont prendre
jusqu'à plusieurs octets de mémoire.

34
00:01:31,600 --> 00:01:34,160
Et si cela est pas quelque chose
vous allez avoir besoin de faire,

35
00:01:34,160 --> 00:01:36,300
vous pourriez décider qu'il est
ne vaut pas le compromis

36
00:01:36,300 --> 00:01:39,360
avoir à dépenser le supplément
octets de mémoire nécessaire

37
00:01:39,360 --> 00:01:43,940
pour une liste doublement liée si vous n'êtes pas
va être la suppression d'éléments simples.

38
00:01:43,940 --> 00:01:46,760
Mais ils sont aussi très cool
pour d'autres choses aussi.

39
00:01:46,760 --> 00:01:51,260
>> Donc, comme je le disais, nous avons juste à ajouter
Un seul champ de notre structure

40
00:01:51,260 --> 00:01:55,360
definition-- cette notion
d'un pointeur précédente.

41
00:01:55,360 --> 00:01:58,620
Donc, avec une liste simplement chaînée, nous
avoir la valeur et le pointeur suivante,

42
00:01:58,620 --> 00:02:02,850
de sorte que la liste doublement liée vient
une manière de se déplacer vers l'arrière ainsi.

43
00:02:02,850 --> 00:02:04,960
>> Maintenant, dans le simplement chaînée
Liste vidéo, nous avons parlé

44
00:02:04,960 --> 00:02:07,210
sur ces cinq des
principales choses que vous devez être

45
00:02:07,210 --> 00:02:09,449
capable de faire pour travailler avec les listes chaînées.

46
00:02:09,449 --> 00:02:12,880
Et pour la plupart d'entre eux, le fait
qu'il est une liste doublement chaînée

47
00:02:12,880 --> 00:02:14,130
est pas vraiment un grand saut.

48
00:02:14,130 --> 00:02:17,936
Nous pouvons encore parcourir par tout
aller de l'avant, du début à la fin.

49
00:02:17,936 --> 00:02:20,810
Nous pouvons toujours créer un noeud sur
l'air mince, à peu près de la même façon.

50
00:02:20,810 --> 00:02:23,591
Nous pouvons supprimer les listes jolie
de la même manière aussi.

51
00:02:23,591 --> 00:02:25,340
Les seules choses qui
sont subtilement différent,

52
00:02:25,340 --> 00:02:28,970
vraiment, sont l'insertion
nouveaux noeuds dans la liste,

53
00:02:28,970 --> 00:02:33,722
et nous allons enfin parlons de la suppression
un seul élément de la liste ainsi.

54
00:02:33,722 --> 00:02:35,430
Encore une fois, à peu près
les trois autres, nous sommes

55
00:02:35,430 --> 00:02:37,888
ne vais pas en parler
maintenant, car ils sont tout simplement

56
00:02:37,888 --> 00:02:43,920
tweaks très mineurs sur les idées discutées
dans la liste vidéo simplement chaînée.

57
00:02:43,920 --> 00:02:46,292
>> Donc, nous allons insérer un nouveau noeud
dans une liste doublement chaînée.

58
00:02:46,292 --> 00:02:48,750
Nous avons parlé de faire ce pour
listes simplement chaînée ainsi,

59
00:02:48,750 --> 00:02:52,020
mais il ya un couple d'extra
prises avec une liste doublement chaînée.

60
00:02:52,020 --> 00:02:55,280
Ont été [? passant?] dans la tête de la
énumérer ici et une valeur arbitraire,

61
00:02:55,280 --> 00:02:58,600
et nous voulons obtenir le nouveau chef
de la liste sur cette fonction.

62
00:02:58,600 --> 00:03:01,414
Voilà pourquoi il renvoie une star dllnode.

63
00:03:01,414 --> 00:03:02,330
Alors, quelles sont les étapes?

64
00:03:02,330 --> 00:03:04,496
Ils sont, à nouveau, très similaire
à des listes simplement chaînée

65
00:03:04,496 --> 00:03:05,670
avec un ajout supplémentaire.

66
00:03:05,670 --> 00:03:08,900
Nous voulons alloue de l'espace pour une nouvelle
nœud et assurez-vous qu'il est valide.

67
00:03:08,900 --> 00:03:11,510
Nous voulons combler ce noeud jusqu'à
avec toutes les informations que nous

68
00:03:11,510 --> 00:03:12,564
vouloir mettre dedans.

69
00:03:12,564 --> 00:03:15,480
La dernière chose que nous devons l'do--
chose supplémentaire que nous devons faire, rather--

70
00:03:15,480 --> 00:03:19,435
est de fixer le pointeur précédente
de l'ancien chef de la liste.

71
00:03:19,435 --> 00:03:21,310
Rappelez-vous que parce
listes de doublement chaînée,

72
00:03:21,310 --> 00:03:23,110
nous pouvons aller de l'avant
et qui backwards--

73
00:03:23,110 --> 00:03:27,080
signifie que chaque noeud indique effectivement
à deux autres noeuds au lieu d'un seul.

74
00:03:27,080 --> 00:03:29,110
Et donc nous avons besoin de fixer
l'ancien chef de la liste

75
00:03:29,110 --> 00:03:32,151
pour pointer vers l'arrière pour le nouveau chef de
la liste chaînée, qui était quelque chose

76
00:03:32,151 --> 00:03:33,990
nous ne devons pas faire avant.

77
00:03:33,990 --> 00:03:37,420
Et comme avant, nous revenons juste un
pointeur vers la nouvelle tête de liste.

78
00:03:37,420 --> 00:03:38,220
>> Alors, voici une liste.

79
00:03:38,220 --> 00:03:40,144
Nous voulons insérer 12 dans cette liste.

80
00:03:40,144 --> 00:03:42,060
Notez que le schéma
est légèrement différente.

81
00:03:42,060 --> 00:03:47,710
Chaque nœud contient trois fields--
données, et un pointeur suivante en rouge,

82
00:03:47,710 --> 00:03:50,170
et un pointeur précédente en bleu.

83
00:03:50,170 --> 00:03:54,059
Rien ne vient avant le noeud 15,
de sorte que son pointeur précédent est nulle.

84
00:03:54,059 --> 00:03:55,350
Il est le début de la liste.

85
00:03:55,350 --> 00:03:56,560
Il n'y a rien devant elle.

86
00:03:56,560 --> 00:04:03,350
Et rien ne vient après le nœud 10 et
il est donc pointeur suivant est nulle ainsi.

87
00:04:03,350 --> 00:04:05,616
>> Ajoutons donc 12 à cette liste.

88
00:04:05,616 --> 00:04:08,070
Nous avons besoin de [inaudible] l'espace pour le noeud.

89
00:04:08,070 --> 00:04:11,480
Nous avons mis 12 à l'intérieur de celui-ci.

90
00:04:11,480 --> 00:04:14,840
Et là encore, nous devons être vraiment
attention à ne pas briser la chaîne.

91
00:04:14,840 --> 00:04:17,144
Nous voulons réorganiser la
pointeurs dans l'ordre correct.

92
00:04:17,144 --> 00:04:19,519
Et parfois, cela pourrait mean--
comme nous le verrons en particulier

93
00:04:19,519 --> 00:04:24,120
avec delete-- que nous avons une certaine
pointeurs redondant, mais qui est OK.

94
00:04:24,120 --> 00:04:25,750
>> Alors, que voulons-nous faire en premier?

95
00:04:25,750 --> 00:04:28,290
Je recommanderais le
choses que vous devriez probablement

96
00:04:28,290 --> 00:04:35,350
faire sont à remplir les pointeurs de la 12
noeud avant de toucher quelqu'un d'autre.

97
00:04:35,350 --> 00:04:38,640
Alors qu'est-ce 12 va pointer vers la prochaine?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
Ce qui vient avant le 12?

100
00:04:42,430 --> 00:04:43,640
Rien.

101
00:04:43,640 --> 00:04:46,280
Maintenant, nous avons rempli le
informations supplémentaires dans 12

102
00:04:46,280 --> 00:04:49,320
il a donc Précédent, Suivant, et la valeur.

103
00:04:49,320 --> 00:04:53,505
>> Maintenant, nous pouvons avoir cette 15-- supplémentaire
étape nous parlions about-- nous

104
00:04:53,505 --> 00:04:56,590
peut avoir 15 points de retour à 12.

105
00:04:56,590 --> 00:04:59,634
Et maintenant, nous pouvons déplacer la tête de
la liste chaînée d'être aussi 12.

106
00:04:59,634 --> 00:05:02,550
Donc, il est assez similaire à ce que nous
ont été faites avec les listes simplement liées,

107
00:05:02,550 --> 00:05:06,940
sauf pour l'étape supplémentaire de
reliant la vieille tête de la liste

108
00:05:06,940 --> 00:05:09,810
revenir à la nouvelle tête de liste.

109
00:05:09,810 --> 00:05:12,170
>> Maintenant, nous allons supprimer définitivement
un nœud d'une liste chaînée.

110
00:05:12,170 --> 00:05:14,350
Alors disons que nous avons
une autre fonction que

111
00:05:14,350 --> 00:05:18,080
est de trouver un nœud nous voulons supprimer
et nous a donné un pointeur exactement

112
00:05:18,080 --> 00:05:19,710
le nœud que nous voulons supprimer.

113
00:05:19,710 --> 00:05:22,360
Nous ne disons même pas l'need--
la tête est encore déclarée à l'échelle mondiale.

114
00:05:22,360 --> 00:05:23,590
Nous ne devons pas la tête ici.

115
00:05:23,590 --> 00:05:26,830
Tout cette fonction fait est que nous avons
trouvé un pointeur exactement à la nous node

116
00:05:26,830 --> 00:05:28,090
veulent se débarrasser de.

117
00:05:28,090 --> 00:05:28,940
Mettons-nous en débarrasser.

118
00:05:28,940 --> 00:05:31,859
Il est beaucoup plus facile avec
listes doublement liée.

119
00:05:31,859 --> 00:05:33,650
First-- il est fait
seulement une ou deux choses.

120
00:05:33,650 --> 00:05:38,760
Nous avons juste besoin de fixer les environs
Les pointeurs de noeuds afin qu'ils sauter

121
00:05:38,760 --> 00:05:40,240
le nœud nous voulons supprimer.

122
00:05:40,240 --> 00:05:43,484
Et puis nous pouvons supprimer ce nœud.

123
00:05:43,484 --> 00:05:45,150
Encore une fois, nous allons tout simplement par ici.

124
00:05:45,150 --> 00:05:49,625
Nous avons apparemment décidé que
nous voulons supprimer le nœud X.

125
00:05:49,625 --> 00:05:51,500
Et encore une fois, ce que je suis
faire ici-- par le way--

126
00:05:51,500 --> 00:05:54,580
est un cas général pour une
noeud qui se trouve au milieu.

127
00:05:54,580 --> 00:05:56,547
Il ya un couple de
mises en garde supplémentaires que vous

128
00:05:56,547 --> 00:05:59,380
besoin de considérer lorsque vous supprimez
le début de la liste

129
00:05:59,380 --> 00:06:01,040
ou la fin de la liste.

130
00:06:01,040 --> 00:06:03,730
Il ya un couple de spéciale
cas de coin pour faire face aux il.

131
00:06:03,730 --> 00:06:07,960
>> Donc, cela fonctionne pour supprimer un nœud
au milieu de l'une films-- que

132
00:06:07,960 --> 00:06:11,550
a un pointeur légitime de l'avant
et un pointeur légitime vers l'arrière,

133
00:06:11,550 --> 00:06:14,460
légitime pointeur précédent et suivant.

134
00:06:14,460 --> 00:06:16,530
Encore une fois, si vous travaillez
avec les extrémités, vous

135
00:06:16,530 --> 00:06:18,500
besoin de gérer les
un peu différemment,

136
00:06:18,500 --> 00:06:19,570
et on ne va pas à
parler que maintenant.

137
00:06:19,570 --> 00:06:21,319
Mais vous pouvez probablement
déterminer ce qui doit

138
00:06:21,319 --> 00:06:24,610
à faire juste en regardant cette vidéo.

139
00:06:24,610 --> 00:06:28,910
>> Donc, nous avons isolé X. X est le noeud
nous voulons supprimer de la liste.

140
00:06:28,910 --> 00:06:30,140
Qu'est-ce qu'on fait?

141
00:06:30,140 --> 00:06:32,800
Tout d'abord, nous devons réorganiser
les pointeurs à l'extérieur.

142
00:06:32,800 --> 00:06:35,815
Nous devons réorganiser
9 est à côté de sauter plus de 13

143
00:06:35,815 --> 00:06:38,030
et le point à qui 10--
est ce que nous venons de faire.

144
00:06:38,030 --> 00:06:41,180
Et nous devons aussi
réorganiser de 10 précédente

145
00:06:41,180 --> 00:06:44,610
signaler à 9 au lieu de pointer à 13.

146
00:06:44,610 --> 00:06:46,490
>> Encore une fois, ce fut la
schéma pour commencer.

147
00:06:46,490 --> 00:06:47,730
Ce fut notre chaîne.

148
00:06:47,730 --> 00:06:51,027
Nous avons besoin de sauter plus de 13,
mais nous devons aussi préserver

149
00:06:51,027 --> 00:06:52,110
l'intégrité de la liste.

150
00:06:52,110 --> 00:06:54,680
Nous ne voulons pas perdre tout
l'information dans les deux sens.

151
00:06:54,680 --> 00:06:59,620
Donc, nous devons réorganiser
les pointeurs soigneusement

152
00:06:59,620 --> 00:07:02,240
afin de ne pas rompre la chaîne du tout.

153
00:07:02,240 --> 00:07:05,710
>> Donc nous pouvons dire pointeur de 9 Suivant
des points au même endroit

154
00:07:05,710 --> 00:07:08,040
que de treize Suivant
pointeur souligne dès maintenant.

155
00:07:08,040 --> 00:07:10,331
Parce que nous sommes finalement
va vouloir sauter par-dessus 13.

156
00:07:10,331 --> 00:07:13,750
Alors, où 13 points suivante, vous
veulent neuf à y pointer la place.

157
00:07:13,750 --> 00:07:15,200
Alors voilà.

158
00:07:15,200 --> 00:07:20,370
Et puis, où 13 points de retour
à, tout ce qui vient avant le 13,

159
00:07:20,370 --> 00:07:24,800
nous voulons 10 pour pointer
pour qu'au lieu de 13.

160
00:07:24,800 --> 00:07:29,290
Maintenant, remarquez, si vous suivez
les flèches, on peut déposer 13

161
00:07:29,290 --> 00:07:32,380
sans perdre effectivement toute information.

162
00:07:32,380 --> 00:07:36,002
Nous avons gardé l'intégrité de la liste,
le déplacement vers l'avant et vers l'arrière.

163
00:07:36,002 --> 00:07:38,210
Et puis nous pouvons juste une sorte
de nettoyer un peu

164
00:07:38,210 --> 00:07:40,930
en tirant la liste ensemble.

165
00:07:40,930 --> 00:07:43,270
Donc, nous avons réorganisé le
pointeurs de chaque côté.

166
00:07:43,270 --> 00:07:46,231
Et puis nous avons libéré l'X
qui contenait noeud 13,

167
00:07:46,231 --> 00:07:47,480
et nous ne brisons pas la chaîne.

168
00:07:47,480 --> 00:07:50,980
Donc nous avons fait bonne.

169
00:07:50,980 --> 00:07:53,000
>> Note finale ici, sur les listes chaînées.

170
00:07:53,000 --> 00:07:55,990
Donc, à la fois par des liaisons simples et doublement chaînée
listes, comme nous l'avons vu,

171
00:07:55,990 --> 00:07:58,959
soutien insertion réellement efficace
et la suppression d'éléments.

172
00:07:58,959 --> 00:08:00,750
Vous pouvez très bien le faire
il en temps constant.

173
00:08:00,750 --> 00:08:03,333
Qu'avons-nous avons à faire pour supprimer
un élément juste une seconde il ya?

174
00:08:03,333 --> 00:08:04,440
Nous avons déménagé un pointeur.

175
00:08:04,440 --> 00:08:05,920
Nous avons déménagé une autre pointeur.

176
00:08:05,920 --> 00:08:07,915
Nous avons libéré X- a fallu trois opérations.

177
00:08:07,915 --> 00:08:14,500
Il faut toujours trois opérations à
supprimer cette node-- pour libérer un noeud.

178
00:08:14,500 --> 00:08:15,280
>> Comment pouvons-nous insérons?

179
00:08:15,280 --> 00:08:17,280
Eh bien, nous sommes juste toujours
vireur sur le début

180
00:08:17,280 --> 00:08:19,400
si nous voulons insérer efficacement.

181
00:08:19,400 --> 00:08:21,964
Nous devons donc rearrange--
en fonction de si elle est

182
00:08:21,964 --> 00:08:24,380
une des liaisons simples ou doublement chaînée
liste, nous pourrions avoir besoin de faire trois

183
00:08:24,380 --> 00:08:26,824
ou quatre opérations max.

184
00:08:26,824 --> 00:08:28,365
Mais encore une fois, il est toujours trois ou quatre.

185
00:08:28,365 --> 00:08:30,531
Il n'a pas d'importance combien de
éléments sont dans notre liste,

186
00:08:30,531 --> 00:08:33,549
il est toujours trois ou quatre operations--
tout comme la suppression est toujours

187
00:08:33,549 --> 00:08:35,320
trois ou quatre opérations.

188
00:08:35,320 --> 00:08:36,919
Il est temps constant.

189
00:08:36,919 --> 00:08:38,169
Voilà donc vraiment super.

190
00:08:38,169 --> 00:08:40,620
>> Avec des tableaux, nous faisions
quelque chose comme le tri par insertion.

191
00:08:40,620 --> 00:08:44,739
Vous vous souvenez sans doute que l'insertion
Trier est pas un algorithme de temps constant.

192
00:08:44,739 --> 00:08:46,030
Il est en fait assez cher.

193
00:08:46,030 --> 00:08:48,840
Donc, cela est beaucoup mieux pour l'insertion.

194
00:08:48,840 --> 00:08:51,840
Mais comme je l'ai mentionné dans le
simplement chaînée liste vidéo,

195
00:08:51,840 --> 00:08:54,030
nous avons ici un inconvénient aussi, non?

196
00:08:54,030 --> 00:08:57,580
Nous avons perdu la capacité de
accéder au hasard éléments.

197
00:08:57,580 --> 00:09:02,310
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

198
00:09:02,310 --> 00:09:04,990
de la même manière que nous pouvons
le faire avec un tableau

199
00:09:04,990 --> 00:09:08,630
Ou nous pouvons simplement directement index
dans l'élément de notre gamme.

200
00:09:08,630 --> 00:09:10,930
>> Et donc essayer de trouver un
élément dans une films-- liée

201
00:09:10,930 --> 00:09:15,880
si la recherche est important--
peut maintenant prendre le temps linéaire.

202
00:09:15,880 --> 00:09:18,330
Comme la liste est longue, plus il
pourrait prendre une étape supplémentaire

203
00:09:18,330 --> 00:09:22,644
pour chaque élément dans la liste
Afin de trouver ce que nous cherchons.

204
00:09:22,644 --> 00:09:23,560
Donc, il ya des arbitrages.

205
00:09:23,560 --> 00:09:25,780
Il ya un peu d'un pro
et con élément ici.

206
00:09:25,780 --> 00:09:29,110
>> Et une liste doublement chaînée ne sont pas les
dernier type de combinaison de structure de données

207
00:09:29,110 --> 00:09:32,840
que nous allons parler,
prenant tout l'édifice de base

208
00:09:32,840 --> 00:09:34,865
C un des blocs de mettre ensemble.

209
00:09:34,865 --> 00:09:37,900
Car en fait, nous pouvons
même faire mieux que cela

210
00:09:37,900 --> 00:09:41,970
à créer une structure de données qui
vous pourriez être en mesure de chercher dans

211
00:09:41,970 --> 00:09:43,360
en temps constant aussi.

212
00:09:43,360 --> 00:09:46,080
Mais plus que dans une autre vidéo.

213
00:09:46,080 --> 00:09:47,150
>> Je suis Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Ceci est CS50.

215
00:09:49,050 --> 00:09:50,877