1
00:00:00,000 --> 00:00:03,381
>> [Glazbom]

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

3
00:00:04,604 --> 00:00:05,520
Doug LLOYD: U redu.

4
00:00:05,520 --> 00:00:07,860
Dakle, ako ste upravo završili da
Video o jednostruko-povezanim popisima žao

5
00:00:07,860 --> 00:00:09,568
Te ostavio sam off na
malo Cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ali drago mi je da ste ovdje završiti
priča o dvostruko povezane liste.

7
00:00:12,790 --> 00:00:15,250
>> Dakle, ako se sjećate iz
taj video, razgovarali smo

8
00:00:15,250 --> 00:00:18,500
kako pojedinačno povezani
popisi ne pohađaju našu sposobnost

9
00:00:18,500 --> 00:00:22,090
da se bave informacijama
gdje je broj elemenata

10
00:00:22,090 --> 00:00:24,442
ili broj predmeta u
popis može rasti ili smanjivati.

11
00:00:24,442 --> 00:00:26,400
Sada možemo nositi s
nešto slično, gdje

12
00:00:26,400 --> 00:00:28,310
nismo mogli nositi s njom s polja.

13
00:00:28,310 --> 00:00:30,560
>> Ali oni ne pate od jedne
kritično ograničenje koje

14
00:00:30,560 --> 00:00:33,790
je da se uz pojedinačno povezani
Popis, možemo samo uvijek kretati

15
00:00:33,790 --> 00:00:36,200
u jednom smjeru kroz listu.

16
00:00:36,200 --> 00:00:39,010
A jedini pravi stanje
gdje da može postati problem

17
00:00:39,010 --> 00:00:41,250
bio je kada smo pokušali
Brisanje jednog elementa.

18
00:00:41,250 --> 00:00:46,000
A nismo ni razgovarali o tome kako to učiniti
u popisu pojedinačno-povezane u pseudokod.

19
00:00:46,000 --> 00:00:48,797
To je svakako izvodljiv, ali
to može biti malo gnjavaža.

20
00:00:48,797 --> 00:00:50,630
Dakle, ako se nađete
u situaciji u kojoj

21
00:00:50,630 --> 00:00:53,175
pokušavate izbrisati
pojedinačni elementi iz popisa

22
00:00:53,175 --> 00:00:55,430
ili će to biti potrebno
da ćete se brisanje

23
00:00:55,430 --> 00:00:57,970
pojedinačni elementi iz
popis, možda želite

24
00:00:57,970 --> 00:01:02,090
razmotriti pomoću dvostruko povezani
popis, umjesto popisa za jednostruko-povezane.

25
00:01:02,090 --> 00:01:06,320
Zbog dvostruko povezani popisi omogućuju vam
premjestiti oba naprijed i natrag

26
00:01:06,320 --> 00:01:09,340
kroz popis, umjesto
Samo naprijed kroz list--

27
00:01:09,340 --> 00:01:13,950
Samo dodavanjem jednog dodatni element
u našu definiciju strukture

28
00:01:13,950 --> 00:01:16,690
za dvostruko povezane liste čvora.

29
00:01:16,690 --> 00:01:19,770
>> Opet, ako ne ide na
se brisanje pojedinačnih elemenata

30
00:01:19,770 --> 00:01:24,810
iz list-- jer mi dodajemo
dodatni polje našem strukture

31
00:01:24,810 --> 00:01:28,340
definiciji, sami čvorovi
za dvostruko povezane liste

32
00:01:28,340 --> 00:01:29,550
će biti veća.

33
00:01:29,550 --> 00:01:31,600
Oni će uzeti
se više bajtova memorije.

34
00:01:31,600 --> 00:01:34,160
I tako, ako to nije nešto
ti si idući u morati učiniti,

35
00:01:34,160 --> 00:01:36,300
možda odlučiti da je
nije vrijedno trgovina off

36
00:01:36,300 --> 00:01:39,360
morati provesti extra
bajta memorije potrebne

37
00:01:39,360 --> 00:01:43,940
za popis dvostruko povezana ako niste
će se brisanje pojedinačne elemente.

38
00:01:43,940 --> 00:01:46,760
Ali oni su također super
za druge stvari.

39
00:01:46,760 --> 00:01:51,260
>> Dakle, kao što sam rekao, samo moramo dodati
jedan jedini polje našem strukture

40
00:01:51,260 --> 00:01:55,360
definition-- ovaj pojam
prethodne pokazivača.

41
00:01:55,360 --> 00:01:58,620
Tako je s popisa za jednostruko povezanom smo
imaju vrijednost i sljedeći pokazivač,

42
00:01:58,620 --> 00:02:02,850
tako da je popis dvostruko povezana je upravo
način za pomicanje unatrag, kao dobro.

43
00:02:02,850 --> 00:02:04,960
>> Sada se u pojedinačno-linked
Popis videa, razgovarali smo

44
00:02:04,960 --> 00:02:07,210
o su pet od
Glavne stvari koje trebate biti

45
00:02:07,210 --> 00:02:09,449
u mogućnosti to učiniti za rad s povezanim popisima.

46
00:02:09,449 --> 00:02:12,880
A za većinu tih, činjenice
da je popis s dvostruko povezani

47
00:02:12,880 --> 00:02:14,130
zapravo i nije veliki skok.

48
00:02:14,130 --> 00:02:17,936
Još uvijek možete pretraživati ​​po samo
kreće naprijed od početka do kraja.

49
00:02:17,936 --> 00:02:20,810
Još uvijek možete stvoriti čvor iz
zraku, prilično mnogo na isti način.

50
00:02:20,810 --> 00:02:23,591
Možemo brisati popise lijepa
mnogo na isti način previše.

51
00:02:23,591 --> 00:02:25,340
Jedine stvari koje
su suptilno različita,

52
00:02:25,340 --> 00:02:28,970
stvarno su umetanje
novi čvorovi u popisu,

53
00:02:28,970 --> 00:02:33,722
pa ćemo napokon razgovarati o brisanju
jedan element iz ljestvicu.

54
00:02:33,722 --> 00:02:35,430
Opet, prilično mnogo
ostale tri, mi smo

55
00:02:35,430 --> 00:02:37,888
ne ide razgovarati o njima
upravo sada, jer oni su samo

56
00:02:37,888 --> 00:02:43,920
vrlo male tweaks na idejama raspravlja
u pojedinačno-povezanog popisa videozapisa.

57
00:02:43,920 --> 00:02:46,292
>> Tako ćemo umetnuti novi čvor
u popisu dvostruko povezani.

58
00:02:46,292 --> 00:02:48,750
Razgovarali smo o to za
pojedinačno povezani liste i,

59
00:02:48,750 --> 00:02:52,020
ali ima par extra
hvata s dvostruko povezanim popisima.

60
00:02:52,020 --> 00:02:55,280
Mi smo [? prolazi?] u glavi od
popis ovdje, a neke proizvoljne vrijednosti,

61
00:02:55,280 --> 00:02:58,600
i želimo dobiti novu glavu
popisa iz ove funkcije.

62
00:02:58,600 --> 00:03:01,414
Zato vraća dllnode zvijezdu.

63
00:03:01,414 --> 00:03:02,330
Pa što su koraci?

64
00:03:02,330 --> 00:03:04,496
Oni su, opet, vrlo sličan
za pojedinačno povezani liste

65
00:03:04,496 --> 00:03:05,670
s pomoćnim toga.

66
00:03:05,670 --> 00:03:08,900
Želimo dodjeljuje prostor za nova
čvor i provjera kako bi bili sigurni da je valjana.

67
00:03:08,900 --> 00:03:11,510
Želimo ispuniti tu čvor se
sa što informacije koje

68
00:03:11,510 --> 00:03:12,564
želite staviti u njega.

69
00:03:12,564 --> 00:03:15,480
Zadnje što trebamo do--
extra stvar koju trebate učiniti, rather--

70
00:03:15,480 --> 00:03:19,435
je popraviti Prethodna pokazivač
stare glave popisa.

71
00:03:19,435 --> 00:03:21,310
Zapamtite da zbog
od dvostruko povezane liste,

72
00:03:21,310 --> 00:03:23,110
možemo krenuti naprijed
i backwards-- koji

73
00:03:23,110 --> 00:03:27,080
znači da je svaki čvor zapravo ukazuje
druga dva čvora, umjesto samo jednog.

74
00:03:27,080 --> 00:03:29,110
I tako moramo popraviti
stari šef popisa

75
00:03:29,110 --> 00:03:32,151
ukazati natrag na novu glavu
popis povezani, što je nešto

76
00:03:32,151 --> 00:03:33,990
nismo imali za napraviti prije.

77
00:03:33,990 --> 00:03:37,420
A kao i prije, samo smo se vratiti
pokazivač na novu glavu na popisu.

78
00:03:37,420 --> 00:03:38,220
>> Dakle, ovdje je popis.

79
00:03:38,220 --> 00:03:40,144
Želimo umetnuti 12 u ovaj popis.

80
00:03:40,144 --> 00:03:42,060
Obavijest da je dijagram
je malo drugačija.

81
00:03:42,060 --> 00:03:47,710
Svaki čvor ima tri fields--
podataka, a Sljedeća pokazivač crveno,

82
00:03:47,710 --> 00:03:50,170
a Prethodna pokazivač u plavom.

83
00:03:50,170 --> 00:03:54,059
Ništa dolazi prije 15 čvora,
tako da je njegova Prethodna pointer je null.

84
00:03:54,059 --> 00:03:55,350
To je početak popisa.

85
00:03:55,350 --> 00:03:56,560
Nema ništa prije njega.

86
00:03:56,560 --> 00:04:03,350
I ništa ne dolazi nakon 10 čvora, te
tako da je kazaljka Sljedeća je ništavan, kao dobro.

87
00:04:03,350 --> 00:04:05,616
>> Tako ćemo dodati 12 na ovaj popis.

88
00:04:05,616 --> 00:04:08,070
Trebamo [nečujan] prostor za čvor.

89
00:04:08,070 --> 00:04:11,480
Mi smo stavili 12 unutar nje.

90
00:04:11,480 --> 00:04:14,840
A onda opet, moramo biti jako
Pazite da ne razbiti lanac.

91
00:04:14,840 --> 00:04:17,144
Želimo preurediti
upućuje u ispravnom redoslijedu.

92
00:04:17,144 --> 00:04:19,519
A ponekad da bi mogli mean--
kao što ćemo vidjeti posebno

93
00:04:19,519 --> 00:04:24,120
s delete-- da imamo neke
suvišne pokazivače, ali to je u redu.

94
00:04:24,120 --> 00:04:25,750
>> Dakle, ono što želimo učiniti prvi?

95
00:04:25,750 --> 00:04:28,290
Ja bih preporučiti
stvari koje bi trebali vjerojatno

96
00:04:28,290 --> 00:04:35,350
to su popuniti naputke od 12
čvor prije nego što dodirnete bilo tko drugi.

97
00:04:35,350 --> 00:04:38,640
Pa što je 12 će ukazati na sljedeće?

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

99
00:04:39,860 --> 00:04:42,430
Što dolazi prije 12?

100
00:04:42,430 --> 00:04:43,640
Ništa.

101
00:04:43,640 --> 00:04:46,280
Sada smo ispuni
dodatne informacije u 12

102
00:04:46,280 --> 00:04:49,320
tako da ima Prethodna, sljedeći, i vrijednosti.

103
00:04:49,320 --> 00:04:53,505
>> Sada možemo imati 15-- ovaj dodatni
korak smo razgovarali about-- mi

104
00:04:53,505 --> 00:04:56,590
može imati 15 bod natrag na 12.

105
00:04:56,590 --> 00:04:59,634
I sada možemo pomaknuti glavu
popis povezani i da se 12.

106
00:04:59,634 --> 00:05:02,550
Dakle, to je prilično slično onome što smo
radili s pojedinačno-povezane liste,

107
00:05:02,550 --> 00:05:06,940
osim za dodatni korak
povezivanje staru glavu na popis

108
00:05:06,940 --> 00:05:09,810
Natrag na novog šefa popisa.

109
00:05:09,810 --> 00:05:12,170
>> Sada ćemo konačno brisanje
čvor s popisa povezane.

110
00:05:12,170 --> 00:05:14,350
Tako recimo imamo
neke druge funkcije koje

111
00:05:14,350 --> 00:05:18,080
je pronalaženje čvor želimo obrisati
i da nam je dao pokazivač na točno

112
00:05:18,080 --> 00:05:19,710
čvor koji želimo izbrisati.

113
00:05:19,710 --> 00:05:22,360
Mi ni ne need-- reći
Glava je još uvijek globalno proglašen.

114
00:05:22,360 --> 00:05:23,590
Ne trebamo glavu ovdje.

115
00:05:23,590 --> 00:05:26,830
Sve to omogućuje radi je imamo
pronašao pokazivač na točno čvor mi

116
00:05:26,830 --> 00:05:28,090
Želite se riješiti.

117
00:05:28,090 --> 00:05:28,940
Idemo dobiti osloboditi od njega.

118
00:05:28,940 --> 00:05:31,859
To je puno lakše s
dvostruko povezane liste.

119
00:05:31,859 --> 00:05:33,650
First-- to je zapravo
samo par stvari.

120
00:05:33,650 --> 00:05:38,760
Mi samo trebate popraviti okolno
čvorovi 'pokazivače tako da oni preskaču

121
00:05:38,760 --> 00:05:40,240
čvor želimo izbrisati.

122
00:05:40,240 --> 00:05:43,484
A onda možemo izbrisati taj čvor.

123
00:05:43,484 --> 00:05:45,150
Pa opet, mi samo idemo ovuda.

124
00:05:45,150 --> 00:05:49,625
Mi očito su odlučili da
želimo izbrisati čvor X.

125
00:05:49,625 --> 00:05:51,500
I opet, što sam
radi here-- od way--

126
00:05:51,500 --> 00:05:54,580
je opći slučaj za
čvor koji je u sredini.

127
00:05:54,580 --> 00:05:56,547
Postoji nekoliko
dodatni upozorenja da

128
00:05:56,547 --> 00:05:59,380
morate uzeti u obzir kada ste brisanja
samog početka popisa

129
00:05:59,380 --> 00:06:01,040
ili samom kraju liste.

130
00:06:01,040 --> 00:06:03,730
Postoji nekoliko posebna
Kutak za slučajeve da se bave tamo.

131
00:06:03,730 --> 00:06:07,960
>> Tako to radi za brisanje bilo čvor
u sredini onoga koji list--

132
00:06:07,960 --> 00:06:11,550
ima legitiman pokazivač naprijed
i legitimna pokazivač unatrag,

133
00:06:11,550 --> 00:06:14,460
legitimna Prethodna Sljedeća i pokazivač.

134
00:06:14,460 --> 00:06:16,530
Opet, ako radite
s krajevima, što

135
00:06:16,530 --> 00:06:18,500
morati nositi one
malo drugačije,

136
00:06:18,500 --> 00:06:19,570
i nećemo se
razgovarati o tome sada.

137
00:06:19,570 --> 00:06:21,319
Ali vjerojatno možete
shvatiti što treba

138
00:06:21,319 --> 00:06:24,610
treba učiniti samo gledajući ovaj video.

139
00:06:24,610 --> 00:06:28,910
>> Tako smo izolirani X. X čvor
želimo izbrisati s popisa.

140
00:06:28,910 --> 00:06:30,140
Što nam je činiti?

141
00:06:30,140 --> 00:06:32,800
Prvo, moramo preurediti
vanjski naputke.

142
00:06:32,800 --> 00:06:35,815
Moramo preurediti
9 je uz preskočiti 13

143
00:06:35,815 --> 00:06:38,030
a točka na kojoj 10--
je ono što smo upravo učinili.

144
00:06:38,030 --> 00:06:41,180
I mi također trebaju
preurediti 10 prethodnih

145
00:06:41,180 --> 00:06:44,610
ukazati na 9 umjesto ukazujući na 13.

146
00:06:44,610 --> 00:06:46,490
>> Pa opet, to je bio
dijagram za početak.

147
00:06:46,490 --> 00:06:47,730
To je bio naš lanac.

148
00:06:47,730 --> 00:06:51,027
Moramo preskočiti 13,
ali moramo i sačuvati

149
00:06:51,027 --> 00:06:52,110
cjelovitost popisa.

150
00:06:52,110 --> 00:06:54,680
Mi ne želimo izgubiti bilo
Informacije u oba smjera.

151
00:06:54,680 --> 00:06:59,620
Dakle, moramo preurediti
se upućuje pozorno

152
00:06:59,620 --> 00:07:02,240
tako da ne razbiti lanac na sve.

153
00:07:02,240 --> 00:07:05,710
>> Tako možemo reći je sljedeće pokazivač 9
ukazuje na isto mjesto

154
00:07:05,710 --> 00:07:08,040
da trinaest je sljedeće
pokazivač ističe upravo sada.

155
00:07:08,040 --> 00:07:10,331
Budući da smo na kraju
će htjeti preskočiti 13.

156
00:07:10,331 --> 00:07:13,750
Dakle, gdje god je 13 bodova Sljedeći, te
Želite devet ukazati tamo umjesto.

157
00:07:13,750 --> 00:07:15,200
Dakle, to je to.

158
00:07:15,200 --> 00:07:20,370
A onda gdje god 13 bodova natrag
da, sve što dolazi prije 13 godina,

159
00:07:20,370 --> 00:07:24,800
želimo ukazati 10
da da, umjesto 13.

160
00:07:24,800 --> 00:07:29,290
Sada primijetite, ako slijedite
strelice, možemo ispustiti 13

161
00:07:29,290 --> 00:07:32,380
zapravo bez gubitka podataka.

162
00:07:32,380 --> 00:07:36,002
Mi smo zadržao cjelovitost popisa,
kreće i naprijed i nazad.

163
00:07:36,002 --> 00:07:38,210
A onda možemo samo vrsta
ga počistiti malo

164
00:07:38,210 --> 00:07:40,930
povlačenjem popis zajedno.

165
00:07:40,930 --> 00:07:43,270
Tako smo preuredio
upućuje na obje strane.

166
00:07:43,270 --> 00:07:46,231
A onda smo oslobodili x
čvor koji je sadržavao 13,

167
00:07:46,231 --> 00:07:47,480
a nismo razbiti lanac.

168
00:07:47,480 --> 00:07:50,980
Dobar Tako smo i učinili.

169
00:07:50,980 --> 00:07:53,000
>> Završna napomena ovdje na povezanim popisima.

170
00:07:53,000 --> 00:07:55,990
Tako i singly- i dvostruko povezani
popisi, kao što smo vidjeli,

171
00:07:55,990 --> 00:07:58,959
Podrška jako učinkovit umetanje
i brisanje elemenata.

172
00:07:58,959 --> 00:08:00,750
Možete prilično mnogo učiniti
je u stalnom vremenu.

173
00:08:00,750 --> 00:08:03,333
Što moramo učiniti za brisanje
element samo sekundu prije?

174
00:08:03,333 --> 00:08:04,440
Preselili smo jedan pokazivač.

175
00:08:04,440 --> 00:08:05,920
Krenuli smo još jedan pokazivač.

176
00:08:05,920 --> 00:08:07,915
Oslobođeni smo X-- uzeo tri operacije.

177
00:08:07,915 --> 00:08:14,500
Uvijek traje tri operacije na
izbrišite node-- da oslobodi čvor.

178
00:08:14,500 --> 00:08:15,280
>> Kako umetnuti?

179
00:08:15,280 --> 00:08:17,280
Pa, mi smo samo uvijek
letanja na početku

180
00:08:17,280 --> 00:08:19,400
Ako smo umetanje učinkovito.

181
00:08:19,400 --> 00:08:21,964
Dakle, moramo rearrange--
ovisno o tome je li to

182
00:08:21,964 --> 00:08:24,380
singly- ili dvostruko povezani
Popis, možda moramo učiniti tri

183
00:08:24,380 --> 00:08:26,824
ili četiri operacije max.

184
00:08:26,824 --> 00:08:28,365
Ali opet, to je uvijek tri ili četiri.

185
00:08:28,365 --> 00:08:30,531
Nije bitno koliko je
elementi u našem listu,

186
00:08:30,531 --> 00:08:33,549
to je uvijek tri ili četiri operations--
baš kao i brisanje je uvijek

187
00:08:33,549 --> 00:08:35,320
tri ili četiri operacije.

188
00:08:35,320 --> 00:08:36,919
To je konstanta vrijeme.

189
00:08:36,919 --> 00:08:38,169
Dakle, to je stvarno super.

190
00:08:38,169 --> 00:08:40,620
>> S polja, bili smo radili
nešto poput umetanja vrste.

191
00:08:40,620 --> 00:08:44,739
Vjerojatno se sjetiti da je umetanje
vrsta nije konstantna vremena algoritam.

192
00:08:44,739 --> 00:08:46,030
To je zapravo prilično skupo.

193
00:08:46,030 --> 00:08:48,840
Dakle, ovo je puno bolje za umetanje.

194
00:08:48,840 --> 00:08:51,840
Ali kao što sam spomenuo u
pojedinačno povezani popis videozapisa,

195
00:08:51,840 --> 00:08:54,030
imamo downside ovdje, zar ne?

196
00:08:54,030 --> 00:08:57,580
Mi smo izgubili sposobnost
slučajno pristupiti elemente.

197
00:08:57,580 --> 00:09:02,310
Ne možemo reći, želim elementa broj četiri
ili je element broj 10 od popisa povezan

198
00:09:02,310 --> 00:09:04,990
isti način na koji možemo
učiniti da se s nizom

199
00:09:04,990 --> 00:09:08,630
ili možemo jednostavno izravno indeksa
u našu Array u elementu.

200
00:09:08,630 --> 00:09:10,930
>> I tako pokušava pronaći
element u povezanom list--

201
00:09:10,930 --> 00:09:15,880
Ako potrazi je important--
Sada mogu uzeti linearno vrijeme.

202
00:09:15,880 --> 00:09:18,330
Kao popis dobiva više, to
možda uzeti jedan dodatni korak

203
00:09:18,330 --> 00:09:22,644
za svaki pojedini element u popisu u
kako bi se pronašli ono što tražite.

204
00:09:22,644 --> 00:09:23,560
Dakle, postoji trgovina off.

205
00:09:23,560 --> 00:09:25,780
Tu je malo pro
i protiv elementa ovdje.

206
00:09:25,780 --> 00:09:29,110
>> A dvostruko povezani popisi nisu
Posljednji vrsta kombinacije strukture podataka

207
00:09:29,110 --> 00:09:32,840
da ćemo razgovarati,
da sve osnovne zgrade

208
00:09:32,840 --> 00:09:34,865
blokovi C stavljajući zajedno.

209
00:09:34,865 --> 00:09:37,900
Jer, u stvari, možemo
čak i bolje od toga

210
00:09:37,900 --> 00:09:41,970
stvoriti strukturu podataka koji
možda ćete biti u mogućnosti da pretraživanje

211
00:09:41,970 --> 00:09:43,360
u stalnom vrijeme previše.

212
00:09:43,360 --> 00:09:46,080
No, više o tome u drugom videu.

213
00:09:46,080 --> 00:09:47,150
>> Ja sam Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Ovo je CS50.

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