1
00:00:00,000 --> 00:00:03,381
>> [Muusika mängib]

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

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

4
00:00:05,520 --> 00:00:07,860
Nii et kui sa just lõpetasin selle
video üksikult seotud nimekirju kahju

5
00:00:07,860 --> 00:00:09,568
Jätsin sulle välja lülitada
natuke pinge.

6
00:00:09,568 --> 00:00:12,790
Aga ma olen rõõmus, et sa siin oled lõpetada
lugu kahekordselt seotud nimekirju.

7
00:00:12,790 --> 00:00:15,250
>> Nii et kui te mäletate
et video, me rääkisime

8
00:00:15,250 --> 00:00:18,500
kuidas üksikult seotud
nimekirju teha osaleda meie võime

9
00:00:18,500 --> 00:00:22,090
tegelema teavet
kus elementide arv

10
00:00:22,090 --> 00:00:24,442
või üksuste arv
nimekirja võib kasvada või väheneda.

11
00:00:24,442 --> 00:00:26,400
Nüüd on võimalik tegeleda
midagi sellist, kus

12
00:00:26,400 --> 00:00:28,310
me ei suutnud toime tulla massiivid.

13
00:00:28,310 --> 00:00:30,560
>> Aga nad ei kannata üks
kriitiline piirangud, mis

14
00:00:30,560 --> 00:00:33,790
on, et koos ühe--aheldatud
nimekirja, saame ainult kunagi liikuma

15
00:00:33,790 --> 00:00:36,200
ühes suunas läbi nimekirja.

16
00:00:36,200 --> 00:00:39,010
Ja ainus olukord
kus see võib muutuda probleemiks

17
00:00:39,010 --> 00:00:41,250
oli, kui me püüdsime
kustutada ühe elemendi.

18
00:00:41,250 --> 00:00:46,000
Ja me isegi ei arutada, kuidas seda teha
on üksikult seotud nimekiri pseudokoodi.

19
00:00:46,000 --> 00:00:48,797
Kindlasti on sooritatav, kuid
see võib olla veidi vaeva.

20
00:00:48,797 --> 00:00:50,630
Nii et kui sa leiad end
olukorras, kus

21
00:00:50,630 --> 00:00:53,175
üritad kustutada
üksikute elementide loendist

22
00:00:53,175 --> 00:00:55,430
või siis läheb vaja
et saad kustutamine

23
00:00:55,430 --> 00:00:57,970
ühe elemendid
nimekirja, võiksite

24
00:00:57,970 --> 00:01:02,090
kaaluda kahekordselt seotud
nimekirja asemel üksikult seotud nimekirja.

25
00:01:02,090 --> 00:01:06,320
Kuna kahekordselt ahelloendid võimaldab teil
liikuda nii edasi ja tagasi

26
00:01:06,320 --> 00:01:09,340
läbi nimekirja asemel
lihtsalt edasi läbi list--

27
00:01:09,340 --> 00:01:13,950
lihtsalt lisades ühe lisaelemendi
meie struktuuri määratlemine

28
00:01:13,950 --> 00:01:16,690
eest kahekordselt seotud nimekirja sõlme.

29
00:01:16,690 --> 00:01:19,770
>> Jällegi, kui te ei kavatse
kustutate ühe elemendid

30
00:01:19,770 --> 00:01:24,810
alates list-- sest me lisame
Lisatasu valdkonnas meie struktuur

31
00:01:24,810 --> 00:01:28,340
määratlus, sõlmed ise
eest kahekordselt ahelloendid

32
00:01:28,340 --> 00:01:29,550
hakkavad olema suuremad.

33
00:01:29,550 --> 00:01:31,600
Nad läheme
rohkem baiti mälu.

34
00:01:31,600 --> 00:01:34,160
Ja kui see ei ole midagi
sa lähed pead tegema,

35
00:01:34,160 --> 00:01:36,300
võite otsustada see on
ei ole väärt kompromiss

36
00:01:36,300 --> 00:01:39,360
saada kulutama rohkem
baiti vajatava mälu

37
00:01:39,360 --> 00:01:43,940
jaoks kahekordselt seotud nimekirja, kui sa ei ole
hakatakse kustutamine ühe elemendid.

38
00:01:43,940 --> 00:01:46,760
Aga nad on ka lahe
muid asju ka.

39
00:01:46,760 --> 00:01:51,260
>> Nii nagu ma ütlesin, me lihtsalt lisada
ühe valdkonna oma struktuuri

40
00:01:51,260 --> 00:01:55,360
definition-- seda mõistet
eelmise pointer.

41
00:01:55,360 --> 00:01:58,620
Nii ühekaupa seotud nimekirja, meil
on väärtus ja Järgmine pointer,

42
00:01:58,620 --> 00:02:02,850
nii kahekordselt ahelloendid lihtsalt on
viis liikuda tahapoole samuti.

43
00:02:02,850 --> 00:02:04,960
>> Nüüd üksikult seotud
nimekirja video, me rääkisime

44
00:02:04,960 --> 00:02:07,210
umbes need viis
Peamised asjad, mida tuleb

45
00:02:07,210 --> 00:02:09,449
võimeline tegema tööd ahelloendid.

46
00:02:09,449 --> 00:02:12,880
Ja enamik neist on asjaolu,
et see on kahekordselt seotud nimekirja

47
00:02:12,880 --> 00:02:14,130
ei ole tõesti suur hüpe.

48
00:02:14,130 --> 00:02:17,936
Me saame ikka otsida lihtsalt
edasiliikumist algusest lõpuni.

49
00:02:17,936 --> 00:02:20,810
Me saame veel luua sõlme välja
õhuke õhk, päris palju sama moodi.

50
00:02:20,810 --> 00:02:23,591
Me ei kustuta nimekirjad päris
samamoodi ka.

51
00:02:23,591 --> 00:02:25,340
Ainsad asjad, mis
on delikaatselt erinevad,

52
00:02:25,340 --> 00:02:28,970
tõesti, on lisada
uued tipud nimistusse,

53
00:02:28,970 --> 00:02:33,722
ja me lõpuks rääkida kustutamine
üksikelemendi nimekirjast samuti.

54
00:02:33,722 --> 00:02:35,430
Jällegi päris palju
Ülejäänud kolm, me oleme

55
00:02:35,430 --> 00:02:37,888
ei kavatse rääkida neist
just nüüd, sest nad lihtsalt

56
00:02:37,888 --> 00:02:43,920
väga Pisimuudatused arutatud ideesid
ka üksikult seotud nimekirja video.

57
00:02:43,920 --> 00:02:46,292
>> Nii saab paigaldada uue tipu
arvesse kahekordselt seotud nimekirja.

58
00:02:46,292 --> 00:02:48,750
Me rääkisime seda teed
üksikult seotud nimekirjad samuti,

59
00:02:48,750 --> 00:02:52,020
kuid seal on paar extra
saagi koos topelt-ahelloendid.

60
00:02:52,020 --> 00:02:55,280
Oleme [? kulgeb?] in juht
siin loetleda mõned suvalise väärtuse,

61
00:02:55,280 --> 00:02:58,600
ja me tahame saada uue juhi
nimekirja läbi selle funktsiooni.

62
00:02:58,600 --> 00:03:01,414
Sellepärast tagastab dllnode star.

63
00:03:01,414 --> 00:03:02,330
Millised on sammud?

64
00:03:02,330 --> 00:03:04,496
Nad on jällegi väga sarnased
to üksikult seotud nimekirjad

65
00:03:04,496 --> 00:03:05,670
ühe ekstra lisaks.

66
00:03:05,670 --> 00:03:08,900
Me tahame, et eraldab ruumi uuele
sõlme ja veenduge, et see on õige.

67
00:03:08,900 --> 00:03:11,510
Tahame täita, et sõlm üles
mis tahes teavet me

68
00:03:11,510 --> 00:03:12,564
tahan panna seda.

69
00:03:12,564 --> 00:03:15,480
Viimane asi, mida me peame do--
Täiendava asi, mida me peame tegema, rather--

70
00:03:15,480 --> 00:03:19,435
on määrata Eelmine pointer
vana juht nimekirja.

71
00:03:19,435 --> 00:03:21,310
Pea meeles, et kuna
on kahekordselt ahelloendid,

72
00:03:21,310 --> 00:03:23,110
saame edasi liikuda
ja backwards-- mis

73
00:03:23,110 --> 00:03:27,080
tähendab, et iga sõlm tegelikult juhib
kahele muude sõlmede ühe asemel.

74
00:03:27,080 --> 00:03:29,110
Ja nii on meil vaja määrata
vana juht nimekirja

75
00:03:29,110 --> 00:03:32,151
punkti tahapoole uue juhi
lingitud nimekirja, mis oli midagi

76
00:03:32,151 --> 00:03:33,990
me ei pea tegema enne.

77
00:03:33,990 --> 00:03:37,420
Ja nagu enne, me lihtsalt tagastada
kursor uus juht nimekirja.

78
00:03:37,420 --> 00:03:38,220
>> Nii et siin on nimekiri.

79
00:03:38,220 --> 00:03:40,144
Me tahame, et lisada 12 sellesse nimekirja.

80
00:03:40,144 --> 00:03:42,060
Pange tähele, et skeem
on veidi erinev.

81
00:03:42,060 --> 00:03:47,710
Iga sõlm sisaldab kolme fields--
andmed ja Järgmine kursor punaseks,

82
00:03:47,710 --> 00:03:50,170
ja Eelmine kursorit sinine.

83
00:03:50,170 --> 00:03:54,059
Miski ei tule enne 15 sõlme,
nii oma Eelmine osuti on null.

84
00:03:54,059 --> 00:03:55,350
See on loendi alguses.

85
00:03:55,350 --> 00:03:56,560
Ei ole midagi enne seda.

86
00:03:56,560 --> 00:04:03,350
Ja midagi tuleb pärast 10 sõlme ja
nii et see on Järgmine osuti on null samuti.

87
00:04:03,350 --> 00:04:05,616
>> Lisame 12. sellesse nimekirja.

88
00:04:05,616 --> 00:04:08,070
Me vajame [kuuldamatu] ruumi sõlme.

89
00:04:08,070 --> 00:04:11,480
Panime 12 sees on.

90
00:04:11,480 --> 00:04:14,840
Ja siis jälle, me peame olema väga
ettevaatlik, et mitte murda kett.

91
00:04:14,840 --> 00:04:17,144
Tahame korrastada
viiteid õiges järjekorras.

92
00:04:17,144 --> 00:04:19,519
Ja mõnikord, et võiks mean--
nagu me näeme eriti

93
00:04:19,519 --> 00:04:24,120
koos delete-- et meil on mõned
koondatud suunanäitajaks, kuid see on OK.

94
00:04:24,120 --> 00:04:25,750
>> Mida me tahame teha esimesena?

95
00:04:25,750 --> 00:04:28,290
Ma soovitaks
Asjad, mida peaks ilmselt

96
00:04:28,290 --> 00:04:35,350
teha on täita suunanäitajaks 12
sõlme, enne kui puudutada kedagi teist.

97
00:04:35,350 --> 00:04:38,640
Mis on 12 kavatse osutavad edasi?

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

99
00:04:39,860 --> 00:04:42,430
Mis tuleb enne 12?

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

101
00:04:43,640 --> 00:04:46,280
Nüüd oleme täitnud
Täiendava info 12

102
00:04:46,280 --> 00:04:49,320
nii et see on Eelmine, Järgmine väärtus.

103
00:04:49,320 --> 00:04:53,505
>> Nüüd saame olla 15-- see extra
samm rääkisime about-- me

104
00:04:53,505 --> 00:04:56,590
võib olla 15 punkti tagasi 12.

105
00:04:56,590 --> 00:04:59,634
Ja nüüd me saame liikuda juht
lingitud nimekirja ka 12.

106
00:04:59,634 --> 00:05:02,550
Nii et see on üsna sarnane sellega, mida me
tegid koos üksikult seotud nimekirju,

107
00:05:02,550 --> 00:05:06,940
välja arvatud ekstra sammu
ühendavad vana juht nimekirja

108
00:05:06,940 --> 00:05:09,810
tagasi uue juhi nimekirja.

109
00:05:09,810 --> 00:05:12,170
>> Nüüd lõpuks kustutada
sõlm on ahelloend.

110
00:05:12,170 --> 00:05:14,350
Ütleme, et meil on
mõne muu funktsiooni, mis

111
00:05:14,350 --> 00:05:18,080
on leida sõlme tahame kustutada
ja andnud meile viit täpselt

112
00:05:18,080 --> 00:05:19,710
sõlme, et me tahame kustutada.

113
00:05:19,710 --> 00:05:22,360
Me isegi ei need-- öelda
Pea on ikka maailmas kuulutatud.

114
00:05:22,360 --> 00:05:23,590
Me ei pea pea siin.

115
00:05:23,590 --> 00:05:26,830
Kõik see funktsioon teeb on me oleme
leitud kursor täpselt sõlme me

116
00:05:26,830 --> 00:05:28,090
tahad lahti saada.

117
00:05:28,090 --> 00:05:28,940
Olgem lahti saada.

118
00:05:28,940 --> 00:05:31,859
See on palju lihtsam
kahekordselt seotud nimekirju.

119
00:05:31,859 --> 00:05:33,650
First-- see on tegelikult
vaid paar asja.

120
00:05:33,650 --> 00:05:38,760
Me lihtsalt vaja parandada ümbritsevat
sõlmed "viiteid, et nad vahele üle

121
00:05:38,760 --> 00:05:40,240
sõlme tahame kustutada.

122
00:05:40,240 --> 00:05:43,484
Ja siis saame kustutada selle sõlme.

123
00:05:43,484 --> 00:05:45,150
Nii jälle, me lihtsalt läbimas siin.

124
00:05:45,150 --> 00:05:49,625
Meil on ilmselt otsustanud, et
tahame kustutada sõlme X.

125
00:05:49,625 --> 00:05:51,500
Ja jälle, mida ma olen
teeme siin-- poolt way--

126
00:05:51,500 --> 00:05:54,580
Üldiselt on see siis, kui
sõlm, mis on keset.

127
00:05:54,580 --> 00:05:56,547
Seal on paar
Täiendava vastuväiteid, mida sa

128
00:05:56,547 --> 00:05:59,380
on vaja kaaluda, kui sa kustutamine
Algusest nimekirja

129
00:05:59,380 --> 00:06:01,040
või väga loendi lõppu.

130
00:06:01,040 --> 00:06:03,730
Seal on paar erilist
nurgas juhtudel tegeleda seal.

131
00:06:03,730 --> 00:06:07,960
>> Nii käib see kustutamist sõlme
keskel on list-- mis

132
00:06:07,960 --> 00:06:11,550
on õigustatud kursorit edasi
ja õigustatud pointer tahapoole,

133
00:06:11,550 --> 00:06:14,460
õigustatud Eelmine ja Järgmine pointer.

134
00:06:14,460 --> 00:06:16,530
Jällegi, kui te töötate
otstega, siis

135
00:06:16,530 --> 00:06:18,500
pead hakkama neid
veidi erinevalt,

136
00:06:18,500 --> 00:06:19,570
ja me ei kavatse
rääkida, et nüüd.

137
00:06:19,570 --> 00:06:21,319
Aga sa võid ilmselt
aru saada, mis vajab

138
00:06:21,319 --> 00:06:24,610
tuleb teha lihtsalt vaadates seda videot.

139
00:06:24,610 --> 00:06:28,910
>> Nii oleme isoleeritud X. X on sõlm
tahame kustutada loendist.

140
00:06:28,910 --> 00:06:30,140
Mida me siis teeme?

141
00:06:30,140 --> 00:06:32,800
Esiteks, me peame ümber
väljastpoolt suunanäitajaks.

142
00:06:32,800 --> 00:06:35,815
Me peame ümber
9 järgmiseks vahele üle 13

143
00:06:35,815 --> 00:06:38,030
ja punkt 10-- mis
on see, mida me oleme lihtsalt teha.

144
00:06:38,030 --> 00:06:41,180
Ja me peame ka
ümber 10 aasta Eelmine

145
00:06:41,180 --> 00:06:44,610
punkti 9 asemel osutades 13.

146
00:06:44,610 --> 00:06:46,490
>> Nii jälle, see oli
diagrammil alustada.

147
00:06:46,490 --> 00:06:47,730
See oli meie kett.

148
00:06:47,730 --> 00:06:51,027
Me peame vahele üle 13,
kuid me peame ka säilitada

149
00:06:51,027 --> 00:06:52,110
terviklikkuse nimekirja.

150
00:06:52,110 --> 00:06:54,680
Me ei taha kaotada mis tahes
andmed ühes või teises suunas.

151
00:06:54,680 --> 00:06:59,620
Seega peame ümber
vihjeid hoolikalt

152
00:06:59,620 --> 00:07:02,240
nii et me ei riku kett üldse.

153
00:07:02,240 --> 00:07:05,710
>> Nii võime öelda, 9 järgmiseks pointer
juhib samas kohas

154
00:07:05,710 --> 00:07:08,040
et kolmteist järgmiseks
pointer juhib praegu.

155
00:07:08,040 --> 00:07:10,331
Sest me oleme lõpuks
lähed tahan vahele üle 13.

156
00:07:10,331 --> 00:07:13,750
Nii kõikjal 13 punkti kõrval, siis
tahan üheksa punkti seal asemel.

157
00:07:13,750 --> 00:07:15,200
Nii et see, et.

158
00:07:15,200 --> 00:07:20,370
Ja siis seal, kus 13 punkti tagasi
et olenemata tuleb enne 13,

159
00:07:20,370 --> 00:07:24,800
tahame 10 punkti
selle asemel 13.

160
00:07:24,800 --> 00:07:29,290
Nüüd märgata, kui te järgite
nooled, me võib langeda 13

161
00:07:29,290 --> 00:07:32,380
ilma tegelikult kaotada mis tahes teavet.

162
00:07:32,380 --> 00:07:36,002
Me oleme hoidnud terviklikkuse nimekirja,
liikudes nii edasi ja tagasi.

163
00:07:36,002 --> 00:07:38,210
Ja siis me saame lihtsalt omamoodi
ja puhastan natuke

164
00:07:38,210 --> 00:07:40,930
tõmmates nimekirja koos.

165
00:07:40,930 --> 00:07:43,270
Nii me paigutas ümber
osuti mõlemale küljele.

166
00:07:43,270 --> 00:07:46,231
Ja siis me vabanenud X
sõlm, mis sisaldas 13

167
00:07:46,231 --> 00:07:47,480
ja me ei kaotanud kett.

168
00:07:47,480 --> 00:07:50,980
Nii me tegime hea.

169
00:07:50,980 --> 00:07:53,000
>> Lõpetuseks siin ahelloendid.

170
00:07:53,000 --> 00:07:55,990
Nii nii singly- ja kahekordselt seotud
nimekirjad, nagu me oleme näinud,

171
00:07:55,990 --> 00:07:58,959
toetust tõesti tõhus sisestamise
ja väljajätmist.

172
00:07:58,959 --> 00:08:00,750
Võite päris palju teha
see konstantse ajaga.

173
00:08:00,750 --> 00:08:03,333
Mida me peame tegema, et kustutada
element vaid sekund tagasi?

174
00:08:03,333 --> 00:08:04,440
Kolisime üks pointer.

175
00:08:04,440 --> 00:08:05,920
Kolisime teise kursorit.

176
00:08:05,920 --> 00:08:07,915
Meil vabanes x-ist võttis kolm operatsiooni.

177
00:08:07,915 --> 00:08:14,500
See võtab alati kolm toimingud
kustutada node-- vaba sõlme.

178
00:08:14,500 --> 00:08:15,280
>> Kuidas lisada?

179
00:08:15,280 --> 00:08:17,280
Noh, me oleme lihtsalt alati
laveerimine alguses

180
00:08:17,280 --> 00:08:19,400
kui me sisestamist tõhusalt.

181
00:08:19,400 --> 00:08:21,964
Seega peame rearrange--
sõltuvalt sellest, kas see on

182
00:08:21,964 --> 00:08:24,380
singly- või kahekordselt seotud
nimekirja, meil võib olla vaja teha kolm

183
00:08:24,380 --> 00:08:26,824
või neli tegevust max.

184
00:08:26,824 --> 00:08:28,365
Aga jälle, see on alati kolm või neli.

185
00:08:28,365 --> 00:08:30,531
See ei ole tähtis, kui palju
elemendid on meie nimekirjas,

186
00:08:30,531 --> 00:08:33,549
see on alati kolm või neli operations--
nagu kustutamine on alati

187
00:08:33,549 --> 00:08:35,320
kolm või neli operatsioone.

188
00:08:35,320 --> 00:08:36,919
See on pidev aega.

189
00:08:36,919 --> 00:08:38,169
Nii see on tõesti suur.

190
00:08:38,169 --> 00:08:40,620
>> Mis massiivid, me teeme
midagi sisestamise omamoodi.

191
00:08:40,620 --> 00:08:44,739
Sa ilmselt meelde tuletada, et sisestamise
Sorteeri ei ole pidev algoritm.

192
00:08:44,739 --> 00:08:46,030
See on tegelikult päris kallis.

193
00:08:46,030 --> 00:08:48,840
Nii et see on palju parem sisestamist.

194
00:08:48,840 --> 00:08:51,840
Aga nagu ma mainisin
üksikult seotud nimekirja video,

195
00:08:51,840 --> 00:08:54,030
meil ka varjukülg ka siin, eks?

196
00:08:54,030 --> 00:08:57,580
Me oleme kaotanud võime
juhuslikult juurde elemente.

197
00:08:57,580 --> 00:09:02,310
Me ei saa öelda, ma tahan element number neli
või element number 10 ahelloend

198
00:09:02,310 --> 00:09:04,990
Samamoodi, et suudame
teha, et massiivi

199
00:09:04,990 --> 00:09:08,630
või saame lihtsalt otse indeks
meie massiiv on element.

200
00:09:08,630 --> 00:09:10,930
>> Ja nii püüab leida
element seotud list--

201
00:09:10,930 --> 00:09:15,880
Kui otsing ei important--
võib nüüd võtta lineaarne aeg.

202
00:09:15,880 --> 00:09:18,330
Nagu nimekirjast muutub pikemaks, siis
võib võtta veel üks samm

203
00:09:18,330 --> 00:09:22,644
iga üksiku elemendi nimekiri
Selleks, et leida, mida me otsime.

204
00:09:22,644 --> 00:09:23,560
Nii et kompromisse.

205
00:09:23,560 --> 00:09:25,780
Seal on natuke pro
ja con element siin.

206
00:09:25,780 --> 00:09:29,110
>> Ja kahekordselt ahelloendid ei ole
Viimast liiki andmete struktuuri kombinatsioon

207
00:09:29,110 --> 00:09:32,840
et me räägime,
võttes kõik põhilised ehitusplokid

208
00:09:32,840 --> 00:09:34,865
plokid C puhul koondades.

209
00:09:34,865 --> 00:09:37,900
Sest tegelikult suudame
isegi parem kui see

210
00:09:37,900 --> 00:09:41,970
luua andmestruktuur, et
sa võiksid otsida

211
00:09:41,970 --> 00:09:43,360
pidevas aega ka.

212
00:09:43,360 --> 00:09:46,080
Aga rohkem, et teise video.

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

214
00:09:47,150 --> 00:09:49,050
See on CS50.

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