1
00:00:00,000 --> 00:00:03,381
>> [MUSIC JOC]

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

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Bine.

4
00:00:05,520 --> 00:00:07,860
Deci, dacă tocmai ați terminat că
video de pe listele individual legate rău

5
00:00:07,860 --> 00:00:09,568
Ți-am lăsat pe o
pic de cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Dar mă bucur că ești aici pentru a termina
povestea de liste dublu-legate.

7
00:00:12,790 --> 00:00:15,250
>> Deci, dacă vă amintiți de la
că video, am vorbit

8
00:00:15,250 --> 00:00:18,500
despre modul în care-legate individual
Listele merg capacitatea noastră

9
00:00:18,500 --> 00:00:22,090
să se ocupe de informații
în cazul în care numărul de elemente

10
00:00:22,090 --> 00:00:24,442
sau numărul de articole în
o listă poate să crească sau micsora.

11
00:00:24,442 --> 00:00:26,400
Putem face acum cu
ceva de genul asta, în cazul în care

12
00:00:26,400 --> 00:00:28,310
nu am putut face cu o cu tablouri.

13
00:00:28,310 --> 00:00:30,560
>> Dar ei suferă de o
limitare critică care

14
00:00:30,560 --> 00:00:33,790
este că cu un legat individual
Lista, ne putem muta doar vreodată

15
00:00:33,790 --> 00:00:36,200
într-o singură direcție prin lista.

16
00:00:36,200 --> 00:00:39,010
Și singurul situația reală
în cazul în care, care poate deveni o problemă

17
00:00:39,010 --> 00:00:41,250
a fost atunci când am încercat să
șterge un singur element.

18
00:00:41,250 --> 00:00:46,000
Și nu am nici discuta cum se face
într-o listă individual legat în pseudocod.

19
00:00:46,000 --> 00:00:48,797
Este cu siguranță greu de realizat, dar
acesta poate fi un pic de un hassle.

20
00:00:48,797 --> 00:00:50,630
Deci, dacă vă aflați
în situația în care

21
00:00:50,630 --> 00:00:53,175
pe care încercați să ștergeți
elemente singulare din lista

22
00:00:53,175 --> 00:00:55,430
sau va fi necesară
că veți fi ștergerea

23
00:00:55,430 --> 00:00:57,970
elemente unice din
lista, ați putea dori

24
00:00:57,970 --> 00:01:02,090
să ia în considerare utilizarea unui legată de două ori
lista în loc de o listă individual legat.

25
00:01:02,090 --> 00:01:06,320
Deoarece listele de două ori legate permiteți
pentru a muta înainte și înapoi atât

26
00:01:06,320 --> 00:01:09,340
prin lista în loc de
doar înainte prin list--

27
00:01:09,340 --> 00:01:13,950
doar prin adăugarea unui element suplimentar
la definiția noastră structură

28
00:01:13,950 --> 00:01:16,690
pentru nodul lista de două ori legat.

29
00:01:16,690 --> 00:01:19,770
>> Din nou, dacă nu sunteți de gând să
fie ștergerea elemente unice

30
00:01:19,770 --> 00:01:24,810
de la list-- pentru că suntem adăugarea de
un câmp suplimentar pentru a structurii noastre

31
00:01:24,810 --> 00:01:28,340
definiție, nodurile înșiși
pentru liste dublu-legate

32
00:01:28,340 --> 00:01:29,550
vor fi mai mari.

33
00:01:29,550 --> 00:01:31,600
Vor să ia
Mai multe bytes de memorie.

34
00:01:31,600 --> 00:01:34,160
Și așa, dacă acest lucru nu este ceva
ai de gând să nevoie pentru a face,

35
00:01:34,160 --> 00:01:36,300
s-ar putea să decidă că e
nu merita compromisul

36
00:01:36,300 --> 00:01:39,360
să să-și petreacă extra
bytes de memorie necesară

37
00:01:39,360 --> 00:01:43,940
Pentru o listă de două ori legată, dacă nu sunteți
va fi ștergerea elemente unice.

38
00:01:43,940 --> 00:01:46,760
Dar sunt, de asemenea, se răcească
pentru alte lucruri.

39
00:01:46,760 --> 00:01:51,260
>> Deci, după cum am spus, trebuie doar să adăugați
un singur câmp pentru a structurii noastre

40
00:01:51,260 --> 00:01:55,360
definition-- această noțiune
de un pointer precedent.

41
00:01:55,360 --> 00:01:58,620
Deci, cu o listă individual-legate, am
au valoarea și indicatorul continuare,

42
00:01:58,620 --> 00:02:02,850
astfel încât lista dublu-legat doar are
un mod de a muta înapoi, de asemenea.

43
00:02:02,850 --> 00:02:04,960
>> Acum, în individual legat
Lista video, am vorbit

44
00:02:04,960 --> 00:02:07,210
despre acestea sunt cinci dintre
lucruri principale pe care trebuie să fie

45
00:02:07,210 --> 00:02:09,449
în stare să facă pentru a lucra cu liste legate.

46
00:02:09,449 --> 00:02:12,880
Și pentru cele mai multe dintre acestea, faptul
că este o listă de două ori legată

47
00:02:12,880 --> 00:02:14,130
nu este cu adevărat un salt mare.

48
00:02:14,130 --> 00:02:17,936
Putem căuta în continuare prin doar prin
avansează de la început până la sfârșit.

49
00:02:17,936 --> 00:02:20,810
Putem crea încă un nod din
aer subțire, destul de mult în același mod.

50
00:02:20,810 --> 00:02:23,591
Putem șterge liste destul de
același fel de mult prea.

51
00:02:23,591 --> 00:02:25,340
Singurele lucruri care
sunt subtil diferite,

52
00:02:25,340 --> 00:02:28,970
într-adevăr, sunt introducerea
noi noduri în listă,

53
00:02:28,970 --> 00:02:33,722
și vom vorbi în cele din urmă despre ștergerea
un singur element din listă, de asemenea.

54
00:02:33,722 --> 00:02:35,430
Din nou, destul de mult
celelalte trei, suntem

55
00:02:35,430 --> 00:02:37,888
Nu vorbi despre ele
acum pentru că sunt doar

56
00:02:37,888 --> 00:02:43,920
trucuri minore pe ideile discutate
în lista video separat legat.

57
00:02:43,920 --> 00:02:46,292
>> Deci, haideți să introduceți un nou nod
într-o listă de două ori legată.

58
00:02:46,292 --> 00:02:48,750
Am vorbit despre a face acest lucru pentru
liste individual legat de asemenea,

59
00:02:48,750 --> 00:02:52,020
dar există o serie de plus
prinde cu liste dublu-legate.

60
00:02:52,020 --> 00:02:55,280
Suntem [? trece?] în capul
lista de aici și o valoare arbitrară,

61
00:02:55,280 --> 00:02:58,600
și vrem să ajungem noul șef
din lista din această funcție.

62
00:02:58,600 --> 00:03:01,414
De aceea, se întoarce o stea dllnode.

63
00:03:01,414 --> 00:03:02,330
Deci, care sunt pașii?

64
00:03:02,330 --> 00:03:04,496
Ele sunt, din nou, foarte asemănător
listelor legată individual

65
00:03:04,496 --> 00:03:05,670
cu o plus suplimentar.

66
00:03:05,670 --> 00:03:08,900
Vrem să alocă spațiu pentru un nou
nod și verificați pentru a vă asigura că este valabil.

67
00:03:08,900 --> 00:03:11,510
Vrem să umple acel nod până
cu orice informații pe care le

68
00:03:11,510 --> 00:03:12,564
doriți să puneți în ea.

69
00:03:12,564 --> 00:03:15,480
Ultimul lucru de care avem nevoie pentru a do--
lucru suplimentar trebuie să facem, rather--

70
00:03:15,480 --> 00:03:19,435
este de a stabili indicatorul precedent
a capului vechi listei.

71
00:03:19,435 --> 00:03:21,310
Amintiți-vă că, din cauza
liste de dublu-legate,

72
00:03:21,310 --> 00:03:23,110
putem merge mai departe
și backwards-- care

73
00:03:23,110 --> 00:03:27,080
înseamnă că fiecare nod punctele de fapt
la alte două noduri loc de unul singur.

74
00:03:27,080 --> 00:03:29,110
Și așa că trebuie să se stabilească
vechiul cap al listei

75
00:03:29,110 --> 00:03:32,151
la punctul înapoi la noul șef al
listei de legătura, care era ceva

76
00:03:32,151 --> 00:03:33,990
nu am avut de a face înainte de.

77
00:03:33,990 --> 00:03:37,420
Și ca și mai înainte, ne întoarcem doar o
pointer la noul șef al listei.

78
00:03:37,420 --> 00:03:38,220
>> Deci, aici este o listă.

79
00:03:38,220 --> 00:03:40,144
Vrem să introduceți 12 în această listă.

80
00:03:40,144 --> 00:03:42,060
Observați că diagrama
este ușor diferit.

81
00:03:42,060 --> 00:03:47,710
Fiecare nod conține trei câmpuri sub
date, și un pointer Următorul în roșu,

82
00:03:47,710 --> 00:03:50,170
și un pointer anterioară în albastru.

83
00:03:50,170 --> 00:03:54,059
Nimic nu vine înainte de nodul de 15,
astfel încât sa pointer precedent este nul.

84
00:03:54,059 --> 00:03:55,350
Este începutul listei.

85
00:03:55,350 --> 00:03:56,560
Nu e nimic în fața sa.

86
00:03:56,560 --> 00:04:03,350
Și nimic nu vine dupa nodul 10, și
asa ca este pointer Următorul este nul, de asemenea.

87
00:04:03,350 --> 00:04:05,616
>> Deci, haideți să adăugați 12 la această listă.

88
00:04:05,616 --> 00:04:08,070
Avem nevoie de [neauzit] spațiu pentru nodul.

89
00:04:08,070 --> 00:04:11,480
Am pus 12 în interiorul acestuia.

90
00:04:11,480 --> 00:04:14,840
Și apoi din nou, trebuie să fie într-adevăr
Aveți grijă să nu pentru a rupe lantul.

91
00:04:14,840 --> 00:04:17,144
Vrem să rearanja
indicii în ordinea corectă.

92
00:04:17,144 --> 00:04:19,519
Și, uneori, care ar putea mean--
cum vom vedea în special

93
00:04:19,519 --> 00:04:24,120
cu delete-- că avem niște
indicii redundante, dar e OK.

94
00:04:24,120 --> 00:04:25,750
>> Deci, ceea ce vrem să facem mai întâi?

95
00:04:25,750 --> 00:04:28,290
Mi-ar recomanda
lucruri pe care le ar fi trebuit probabil

96
00:04:28,290 --> 00:04:35,350
face să umple indicii ale 12
nod înainte de a atinge altcineva.

97
00:04:35,350 --> 00:04:38,640
Deci, ce este de 12 de gând să arate la următorul?

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

99
00:04:39,860 --> 00:04:42,430
Ceea ce vine înainte de 12?

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

101
00:04:43,640 --> 00:04:46,280
Acum ne-am umplut
informații suplimentare în 12

102
00:04:46,280 --> 00:04:49,320
deci are Anterior, Next, și valoarea.

103
00:04:49,320 --> 00:04:53,505
>> Acum 15-- putem avea această suplimentar
pas am vorbit about-- noi

104
00:04:53,505 --> 00:04:56,590
poate avea 15 laturi Inapoi la 12.

105
00:04:56,590 --> 00:04:59,634
Și acum ne putem muta capul de
listei de legătura să fie, de asemenea, 12.

106
00:04:59,634 --> 00:05:02,550
Deci, este destul de similar cu ceea ce am
făceau cu liste individual-legate,

107
00:05:02,550 --> 00:05:06,940
excepție pentru etapa suplimentara de
conectarea vechiul cap al listei

108
00:05:06,940 --> 00:05:09,810
înapoi la noul șef al listei.

109
00:05:09,810 --> 00:05:12,170
>> Acum, haideți să ștergeți în cele din urmă
un nod dintr-o listă legată.

110
00:05:12,170 --> 00:05:14,350
Așa că haideți să spunem că avem
o altă funcție care

111
00:05:14,350 --> 00:05:18,080
este de a găsi un nod vrem să ștergeți
și ne-a dat un pointer la exact

112
00:05:18,080 --> 00:05:19,710
nodul pe care dorim să-l ștergeți.

113
00:05:19,710 --> 00:05:22,360
Noi nici măcar nu need-- spun
cap este încă declarată la nivel global.

114
00:05:22,360 --> 00:05:23,590
Nu avem nevoie de capul aici.

115
00:05:23,590 --> 00:05:26,830
Toate această funcție este de a face este ne-am
găsit un pointer la exact WE nod

116
00:05:26,830 --> 00:05:28,090
vrei sa scapi de.

117
00:05:28,090 --> 00:05:28,940
Să scăpăm de ea.

118
00:05:28,940 --> 00:05:31,859
Este mult mai ușor cu
liste de două ori legat.

119
00:05:31,859 --> 00:05:33,650
First-- este de fapt
doar câteva lucruri.

120
00:05:33,650 --> 00:05:38,760
Avem nevoie doar de a stabili jurul
indicii noduri, astfel încât acestea trece peste

121
00:05:38,760 --> 00:05:40,240
nodul vrem să ștergeți.

122
00:05:40,240 --> 00:05:43,484
Și atunci putem sterge acel nod.

123
00:05:43,484 --> 00:05:45,150
Deci, din nou, vom merge doar pe aici.

124
00:05:45,150 --> 00:05:49,625
Am decis că, aparent
vrem să ștergeți X. nod

125
00:05:49,625 --> 00:05:51,500
Și din nou, ceea ce eu sunt
face here-- de way--

126
00:05:51,500 --> 00:05:54,580
este un caz general de
nod, care este în mijloc.

127
00:05:54,580 --> 00:05:56,547
Există o serie de
limitări suplimentare pe care le

128
00:05:56,547 --> 00:05:59,380
trebuie să ia în considerare atunci când sunteți ștergerea
Chiar de la începutul listei

129
00:05:59,380 --> 00:06:01,040
sau chiar la sfârșitul listei.

130
00:06:01,040 --> 00:06:03,730
Există o serie de special
cazuri colț pentru a face față acolo.

131
00:06:03,730 --> 00:06:07,960
>> Deci, acest lucru funcționează pentru ștergerea orice nod
în mijlocul celui list-- care

132
00:06:07,960 --> 00:06:11,550
are un indicator legitim înainte
și un pointer legitim înapoi,

133
00:06:11,550 --> 00:06:14,460
legitim Anterioară și următoare de pointer.

134
00:06:14,460 --> 00:06:16,530
Din nou, dacă sunteți de lucru
cu capetele, vă

135
00:06:16,530 --> 00:06:18,500
trebuie să se ocupe de cei
ușor diferit,

136
00:06:18,500 --> 00:06:19,570
și noi nu vom
vorbim despre asta acum.

137
00:06:19,570 --> 00:06:21,319
Dar puteți, probabil,
dau seama ce are nevoie

138
00:06:21,319 --> 00:06:24,610
să fie făcut doar prin vizionarea acestui film.

139
00:06:24,610 --> 00:06:28,910
>> Deci ne-am izolat X. X este nodul
vrem să ștergeți din listă.

140
00:06:28,910 --> 00:06:30,140
Ce facem?

141
00:06:30,140 --> 00:06:32,800
În primul rând, avem nevoie pentru a rearanja
indicii exterioare.

142
00:06:32,800 --> 00:06:35,815
Avem nevoie pentru a rearanja
9 de pe lângă săriți peste 13

143
00:06:35,815 --> 00:06:38,030
și punctul de 10-- care
este ceea ce tocmai am făcut.

144
00:06:38,030 --> 00:06:41,180
Și avem nevoie, de asemenea, să
rearanja 10 Înapoi

145
00:06:41,180 --> 00:06:44,610
pentru a indica 9 în loc de arătând spre 13.

146
00:06:44,610 --> 00:06:46,490
>> Deci, din nou, acest lucru a fost
diagrama pentru a începe cu.

147
00:06:46,490 --> 00:06:47,730
Acest lucru a fost lanțul nostru.

148
00:06:47,730 --> 00:06:51,027
Avem nevoie pentru a trece peste 13,
dar avem nevoie pentru a păstra, de asemenea,

149
00:06:51,027 --> 00:06:52,110
integritatea listei.

150
00:06:52,110 --> 00:06:54,680
Nu vrem să-și piardă orice
informații în orice direcție.

151
00:06:54,680 --> 00:06:59,620
Deci, avem nevoie pentru a rearanja
indicii cu atenție

152
00:06:59,620 --> 00:07:02,240
așa că nu rupe lantul, la toate.

153
00:07:02,240 --> 00:07:05,710
>> Deci, putem spune 9 lui pointer Urmatorul
subliniază în același loc

154
00:07:05,710 --> 00:07:08,040
că treisprezece Next
pointer puncte acum.

155
00:07:08,040 --> 00:07:10,331
Pentru că suntem în cele din urmă
gând să doriți să săriți peste 13.

156
00:07:10,331 --> 00:07:13,750
Deci, ori de câte ori 13 puncte viitoare,
doresc nouă la punctul acolo în loc.

157
00:07:13,750 --> 00:07:15,200
Deci asta e.

158
00:07:15,200 --> 00:07:20,370
Și apoi ori de câte ori 13 puncte înapoi
la, orice vine înainte de 13,

159
00:07:20,370 --> 00:07:24,800
vrem 10 de la punctul
în acest loc de 13.

160
00:07:24,800 --> 00:07:29,290
Acum observați, dacă urmați
săgeți, putem scădea 13

161
00:07:29,290 --> 00:07:32,380
fără a pierde de fapt nici o informație.

162
00:07:32,380 --> 00:07:36,002
Am păstrat integritatea a listei,
în mișcare atât înainte și înapoi.

163
00:07:36,002 --> 00:07:38,210
Și apoi putem doar un fel
de curăța un pic

164
00:07:38,210 --> 00:07:40,930
trăgând lista împreună.

165
00:07:40,930 --> 00:07:43,270
Asa ca am reamenajat
indicii pe fiecare parte.

166
00:07:43,270 --> 00:07:46,231
Și apoi ne-am eliberat X
nod care conținea 13,

167
00:07:46,231 --> 00:07:47,480
și nu am rupe lantul.

168
00:07:47,480 --> 00:07:50,980
Așa că am făcut bine.

169
00:07:50,980 --> 00:07:53,000
>> Notă finală aici, pe liste legate.

170
00:07:53,000 --> 00:07:55,990
Deci, atât singly- și dublu-legate
liste, așa cum am văzut,

171
00:07:55,990 --> 00:07:58,959
suport de inserție într-adevăr eficient
și ștergerea elementelor.

172
00:07:58,959 --> 00:08:00,750
Puteți face destul de mult
o în timp constant.

173
00:08:00,750 --> 00:08:03,333
Ce a trebuie să facem pentru a șterge
un element doar o secundă în urmă?

174
00:08:03,333 --> 00:08:04,440
Ne-am mutat un pointer.

175
00:08:04,440 --> 00:08:05,920
Ne-am mutat un alt pointer.

176
00:08:05,920 --> 00:08:07,915
Am eliberat X- luat trei operațiuni.

177
00:08:07,915 --> 00:08:14,500
Este nevoie de trei operații la Întotdeauna
șterge care node-- pentru a elibera un nod.

178
00:08:14,500 --> 00:08:15,280
>> Cum putem introduce?

179
00:08:15,280 --> 00:08:17,280
Ei bine, suntem doar mereu
tacking pe la începutul

180
00:08:17,280 --> 00:08:19,400
dacă ne introduce în mod eficient.

181
00:08:19,400 --> 00:08:21,964
Deci, avem nevoie să rearrange--
în funcție de dacă este

182
00:08:21,964 --> 00:08:24,380
un singly- sau dublu-legat
Lista, am putea să facem trei trebuie

183
00:08:24,380 --> 00:08:26,824
sau patru operațiuni max.

184
00:08:26,824 --> 00:08:28,365
Dar, din nou, este întotdeauna trei sau patru.

185
00:08:28,365 --> 00:08:30,531
Nu contează cât de multe
elemente sunt în lista noastră,

186
00:08:30,531 --> 00:08:33,549
este întotdeauna trei sau patru operations--
la fel ca ștergerea este întotdeauna

187
00:08:33,549 --> 00:08:35,320
trei sau patru operațiuni.

188
00:08:35,320 --> 00:08:36,919
E timpul constant.

189
00:08:36,919 --> 00:08:38,169
Așa că e foarte mare.

190
00:08:38,169 --> 00:08:40,620
>> Cu tablouri, făceam
ceva de genul sortare prin inserție.

191
00:08:40,620 --> 00:08:44,739
Probabil vă amintiți că inserție
fel nu este un algoritm de timp constant.

192
00:08:44,739 --> 00:08:46,030
Este de fapt destul de scump.

193
00:08:46,030 --> 00:08:48,840
Deci, acest lucru este mult mai bine pentru a introduce.

194
00:08:48,840 --> 00:08:51,840
Dar, așa cum am menționat în
individual-legate de listă video,

195
00:08:51,840 --> 00:08:54,030
avem un dezavantaj aici, nu?

196
00:08:54,030 --> 00:08:57,580
Am pierdut capacitatea de a
acces aleatoriu elemente.

197
00:08:57,580 --> 00:09:02,310
Nu putem spune, vreau numărul element de patru
sau numărul element de 10 de o listă legată

198
00:09:02,310 --> 00:09:04,990
în același mod în care putem
face acest lucru cu o serie

199
00:09:04,990 --> 00:09:08,630
sau putem doar direct index
în elementul gama noastre.

200
00:09:08,630 --> 00:09:10,930
>> Și astfel încercarea de a găsi un
element dintr-o list-- legat

201
00:09:10,930 --> 00:09:15,880
dacă căutarea este important--
poate lua acum timp liniar.

202
00:09:15,880 --> 00:09:18,330
Ca lista devine mai lungă, aceasta
s-ar putea lua un pas suplimentar

203
00:09:18,330 --> 00:09:22,644
pentru fiecare element unic în lista de la
scopul de a găsi ceea ce căutați.

204
00:09:22,644 --> 00:09:23,560
Deci nu e off comerciale.

205
00:09:23,560 --> 00:09:25,780
Există un pic de o pro
și elementul con aici.

206
00:09:25,780 --> 00:09:29,110
>> Și liste de doua ori-legate nu de sunt
Ultima fel de combinație structură de date

207
00:09:29,110 --> 00:09:32,840
că vom vorbi despre,
luând toată clădirea de bază

208
00:09:32,840 --> 00:09:34,865
blocuri de C o pune împreună.

209
00:09:34,865 --> 00:09:37,900
Pentru că, de fapt, putem
chiar face mai bine decât acest lucru

210
00:09:37,900 --> 00:09:41,970
pentru a crea o structură de date care
s-ar putea fi capabil de a căuta prin

211
00:09:41,970 --> 00:09:43,360
în timp constant prea.

212
00:09:43,360 --> 00:09:46,080
Dar mai mult pe faptul că într-un alt film.

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

214
00:09:47,150 --> 00:09:49,050
Acest lucru este CS50.

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