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

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

3
00:00:04,604 --> 00:00:05,520
DOUG Lloyd: Selvä.

4
00:00:05,520 --> 00:00:07,860
Joten jos olet juuri että
video yksittäin sidottujen luettelot pahoillani

5
00:00:07,860 --> 00:00:09,568
Jätin sinut pois
hieman jännitysnäytelmä.

6
00:00:09,568 --> 00:00:12,790
Mutta olen iloinen että olet täällä loppuun
tarina kaksinkertaisesti sidottu luetteloita.

7
00:00:12,790 --> 00:00:15,250
>> Joten jos muistatte
että video, puhuimme

8
00:00:15,250 --> 00:00:18,500
miten yksittäin sidottu
luettelot tehdä osallistua kykymme

9
00:00:18,500 --> 00:00:22,090
käsittelemään tietoa
jossa alkioiden lukumäärä

10
00:00:22,090 --> 00:00:24,442
tai kohteiden määrä
luettelo voi kasvaa tai kutistua.

11
00:00:24,442 --> 00:00:26,400
Voimme nyt käsitellä
jotain, jos

12
00:00:26,400 --> 00:00:28,310
emme voineet käsitellä sitä paneelit.

13
00:00:28,310 --> 00:00:30,560
>> Mutta he eivät kärsi yhdestä
kriittinen rajoitus joka

14
00:00:30,560 --> 00:00:33,790
on, että yksittäin sidottu
lista, voimme vain koskaan liikkua

15
00:00:33,790 --> 00:00:36,200
yhteen suuntaan listan läpi.

16
00:00:36,200 --> 00:00:39,010
Ja ainoa todellinen tilanne
jossa joka voi tulla ongelma

17
00:00:39,010 --> 00:00:41,250
oli, kun yritimme
poistaa yksittäinen elementti.

18
00:00:41,250 --> 00:00:46,000
Ja emme edes keskustella siitä, miten tehdä se
in yksittäin-linkitetyn listan pseudokoodilla.

19
00:00:46,000 --> 00:00:48,797
Se on varmasti toteutettavissa, mutta
se voi olla hieman vaivaa.

20
00:00:48,797 --> 00:00:50,630
Joten jos löydät itsesi
tilanteessa, jossa

21
00:00:50,630 --> 00:00:53,175
yrität poistaa
single elementtejä listasta

22
00:00:53,175 --> 00:00:55,430
tai se tulee vaatia
että sinun on poistaa

23
00:00:55,430 --> 00:00:57,970
single elementtejä
luettelossa, saatat haluta

24
00:00:57,970 --> 00:01:02,090
harkita kahdesti sidottu
luetella sijasta yksittäin-linkitetyn listan.

25
00:01:02,090 --> 00:01:06,320
Koska kaksinkertaisesti sidottu luetteloiden avulla voit
liikkua sekä eteen- että taaksepäin

26
00:01:06,320 --> 00:01:09,340
luetteloa sijasta
vain eteenpäin list--

27
00:01:09,340 --> 00:01:13,950
vain lisäämällä yksi ylimääräinen elementti
meidän rakenteen määrittely

28
00:01:13,950 --> 00:01:16,690
varten kaksoislaimennettu linkitetyn listan solmu.

29
00:01:16,690 --> 00:01:19,770
>> Jälleen, jos et aio
voidaan poistaa yksi elementit

30
00:01:19,770 --> 00:01:24,810
alkaen list-- koska lisäämme
lisäkenttä meidän rakenne

31
00:01:24,810 --> 00:01:28,340
määritelmä, solmut itse
varten kaksinkertaisesti sidottu luettelot

32
00:01:28,340 --> 00:01:29,550
tulevat olemaan suurempia.

33
00:01:29,550 --> 00:01:31,600
He aikovat ottaa
enemmän tavua muistia.

34
00:01:31,600 --> 00:01:34,160
Joten jos tämä ei ole jotain
olet menossa tarvitse tehdä,

35
00:01:34,160 --> 00:01:36,300
saatat päättää se
ei kannata vaihtokaupasta

36
00:01:36,300 --> 00:01:39,360
täytyy käyttää ylimääräistä
tavua muistia tarvitaan

37
00:01:39,360 --> 00:01:43,940
varten kaksinkertaisesti sidottu lista, jos et ole
aiotaan poistaa yhden elementtejä.

38
00:01:43,940 --> 00:01:46,760
Mutta he ovat myös viileä
muita asioita liikaa.

39
00:01:46,760 --> 00:01:51,260
>> Joten kuten sanoin, meidän on vain lisätä
yksi kenttä rakenteemme

40
00:01:51,260 --> 00:01:55,360
definition-- tätä käsitettä
edellisen osoittimen.

41
00:01:55,360 --> 00:01:58,620
Joten yksittäin-linkitetty lista, me
on arvo ja Seuraava osoitin,

42
00:01:58,620 --> 00:02:02,850
joten kaksoislaimennettu linkitetty lista vain on
tapa liikkua taaksepäin samoin.

43
00:02:02,850 --> 00:02:04,960
>> Nyt yksinään sidottu
lista video, puhuimme

44
00:02:04,960 --> 00:02:07,210
näistä on viisi
tärkeimmät asiat sinun täytyy olla

45
00:02:07,210 --> 00:02:09,449
voi tehdä työskennellä linkitettyjen listojen.

46
00:02:09,449 --> 00:02:12,880
Ja useimmat näistä se,
että se on kaksinkertaisesti linkitetty lista

47
00:02:12,880 --> 00:02:14,130
ei oikeastaan ​​ison hypyn.

48
00:02:14,130 --> 00:02:17,936
Voimme silti etsiä vain hieman
eteenpäin alusta loppuun.

49
00:02:17,936 --> 00:02:20,810
Voimme silti luoda solmu ulos
ohut ilma, melko samalla tavalla.

50
00:02:20,810 --> 00:02:23,591
Voimme poistaa luetteloita melko
paljon samalla tavalla myös.

51
00:02:23,591 --> 00:02:25,340
Ainoat asiat,
ovat hieman toisenlainen,

52
00:02:25,340 --> 00:02:28,970
todella, asennat
uusi solmut listaan,

53
00:02:28,970 --> 00:02:33,722
ja me lopulta puhua poistaminen
yksittäinen elementti luettelosta samoin.

54
00:02:33,722 --> 00:02:35,430
Jälleen melko paljon
muut kolme, olemme

55
00:02:35,430 --> 00:02:37,888
aio puhua niistä
juuri nyt, koska ne ovat vain

56
00:02:37,888 --> 00:02:43,920
hyvin pieniä parannuksia sen ajatuksista keskustellaan
in yksittäin-linkitetyn listan video.

57
00:02:43,920 --> 00:02:46,292
>> Joten lisätä uusi solmu
osaksi kaksinkertaisesti sidottu lista.

58
00:02:46,292 --> 00:02:48,750
Puhuimme tee tätä
yksittäin sidoksissa luettelot samoin,

59
00:02:48,750 --> 00:02:52,020
mutta siellä on pari ylimääräistä
saaliit kahdesti sidoksissa luetteloita.

60
00:02:52,020 --> 00:02:55,280
Olemme [? ohimennen?] vuonna pään
luetella tässä ja joitakin mielivaltainen arvo,

61
00:02:55,280 --> 00:02:58,600
ja haluamme saada uusi johtaja
luettelon pois tämän toiminnon.

62
00:02:58,600 --> 00:03:01,414
Siksi se palaa dllnode tähti.

63
00:03:01,414 --> 00:03:02,330
Mitä ovat vaiheet?

64
00:03:02,330 --> 00:03:04,496
Ne ovat, jälleen, hyvin samankaltainen
että yksittäin sidottu luettelot

65
00:03:04,496 --> 00:03:05,670
yksi ylimääräinen lisäksi.

66
00:03:05,670 --> 00:03:08,900
Haluamme jakaa tilaa uuden
solmu ja varmista, että se on voimassa.

67
00:03:08,900 --> 00:03:11,510
Haluamme täyttää että solmu ylös
kanssa, mitä tietoa meillä

68
00:03:11,510 --> 00:03:12,564
haluavat laittaa se.

69
00:03:12,564 --> 00:03:15,480
Viimeinen asia, meidän do--
ylimääräinen asia, joka meidän täytyy tehdä, rather--

70
00:03:15,480 --> 00:03:19,435
on korjata Edellinen osoitin
vanhan pään luettelon.

71
00:03:19,435 --> 00:03:21,310
Muista, että koska
aan kahdesti sidottu luettelot,

72
00:03:21,310 --> 00:03:23,110
voimme edetä
ja backwards-- joka

73
00:03:23,110 --> 00:03:27,080
tarkoittaa, että jokainen solmu todella huomauttaa
kaksi muuta solmut yhden sijasta.

74
00:03:27,080 --> 00:03:29,110
Ja niin meidän täytyy korjata
vanha johtaja lista

75
00:03:29,110 --> 00:03:32,151
osoittamaan taaksepäin uusi johtaja
linkitetty lista, joka oli jotain

76
00:03:32,151 --> 00:03:33,990
meillä ei tarvitse tehdä ennen.

77
00:03:33,990 --> 00:03:37,420
Ja kuten ennenkin, me vain palata
Osoitin uusi johtaja luettelon.

78
00:03:37,420 --> 00:03:38,220
>> Joten tässä on luettelo.

79
00:03:38,220 --> 00:03:40,144
Haluamme lisätä 12 tähän luetteloon.

80
00:03:40,144 --> 00:03:42,060
Huomaa, että kaavio
on hieman erilainen.

81
00:03:42,060 --> 00:03:47,710
Jokainen solmu sisältää kolme fields--
tiedot, ja Seuraava osoitin punainen,

82
00:03:47,710 --> 00:03:50,170
ja Edellinen osoitin sinisellä.

83
00:03:50,170 --> 00:03:54,059
Mitään tulee ennen 15 solmun,
joten sen Edellinen osoitin on null.

84
00:03:54,059 --> 00:03:55,350
Se on listan alussa.

85
00:03:55,350 --> 00:03:56,560
Ei ole mitään ennen sitä.

86
00:03:56,560 --> 00:04:03,350
Ja mitään ei tule jälkeen 10 solmun, ja
joten se seuraavaksi osoitin on tyhjä samoin.

87
00:04:03,350 --> 00:04:05,616
>> Joten lisätä 12 tähän luetteloon.

88
00:04:05,616 --> 00:04:08,070
Tarvitsemme [äänetön] tilaa solmu.

89
00:04:08,070 --> 00:04:11,480
Laitamme 12 sen sisälle.

90
00:04:11,480 --> 00:04:14,840
Ja sitten taas, meidän on oltava todella
Varo katkaisemiseksi.

91
00:04:14,840 --> 00:04:17,144
Haluamme järjestää
viitteitä oikeassa järjestyksessä.

92
00:04:17,144 --> 00:04:19,519
Ja joskus se voi mean--
kuten näemme erityisesti

93
00:04:19,519 --> 00:04:24,120
kanssa delete-- että meillä on joitakin
tarpeeton osoittimia, mutta se on OK.

94
00:04:24,120 --> 00:04:25,750
>> Mitä me haluamme tehdä ensin?

95
00:04:25,750 --> 00:04:28,290
Suosittelen
asioita sinun pitäisi luultavasti

96
00:04:28,290 --> 00:04:35,350
do ovat täyttää osoittimet 12
solmu ennen kuin kosketat ketään muuta.

97
00:04:35,350 --> 00:04:38,640
Joten mitä 12 menossa osoittamaan seuraavaksi?

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

99
00:04:39,860 --> 00:04:42,430
Mitä tulee ennen 12?

100
00:04:42,430 --> 00:04:43,640
Mitään.

101
00:04:43,640 --> 00:04:46,280
Nyt olemme täynnä
Lisätiedot 12

102
00:04:46,280 --> 00:04:49,320
joten se on Edellinen, Seuraava, ja arvo.

103
00:04:49,320 --> 00:04:53,505
>> Nyt voimme olla 15-- tätä ylimääräistä
askel puhuimme about-- me

104
00:04:53,505 --> 00:04:56,590
voi olla 15 kohta takaisin 12.

105
00:04:56,590 --> 00:04:59,634
Ja nyt voimme siirtyä pään
linkitetty lista on myös 12.

106
00:04:59,634 --> 00:05:02,550
Joten se on melko samanlainen kuin mitä me
tekivät kanssa yksittäin sidottu luettelot,

107
00:05:02,550 --> 00:05:06,940
lukuun ottamatta ylimääräinen vaihe
yhdistää vanha pää luettelon

108
00:05:06,940 --> 00:05:09,810
Takaisin uusi johtaja luettelon.

109
00:05:09,810 --> 00:05:12,170
>> Nyt vihdoin poistaa
solmu linkitetyn listan.

110
00:05:12,170 --> 00:05:14,350
Joten sanokaamme meillä
joitakin muita toiminto

111
00:05:14,350 --> 00:05:18,080
on löytää solmu haluamme poistaa
ja on antanut meille osoitin tarkalleen

112
00:05:18,080 --> 00:05:19,710
solmu, että haluamme poistaa.

113
00:05:19,710 --> 00:05:22,360
Emme edes need-- sanoa
pää on edelleen maailmanlaajuisesti julistettu.

114
00:05:22,360 --> 00:05:23,590
Emme tarvitse pää täällä.

115
00:05:23,590 --> 00:05:26,830
Kaikki tämä toiminto tekee on olemme
löytyi osoitin juuri solmu me

116
00:05:26,830 --> 00:05:28,090
haluavat päästä eroon.

117
00:05:28,090 --> 00:05:28,940
Mennään eroon siitä.

118
00:05:28,940 --> 00:05:31,859
Se on paljon helpompaa
kaksinkertaisesti sidottu luetteloita.

119
00:05:31,859 --> 00:05:33,650
First-- se on todella
vain pari asiaa.

120
00:05:33,650 --> 00:05:38,760
Meidän vain täytyy korjata ympäröivän
solmut "viitteitä jotta he ohittaa

121
00:05:38,760 --> 00:05:40,240
solmu haluamme poistaa.

122
00:05:40,240 --> 00:05:43,484
Ja sitten voimme poistaa että solmu.

123
00:05:43,484 --> 00:05:45,150
Joten jälleen, me vain läpi täällä.

124
00:05:45,150 --> 00:05:49,625
Olemme ilmeisesti päättänyt, että
haluamme poistaa solmuun X.

125
00:05:49,625 --> 00:05:51,500
Ja vielä, mitä olen
tekee here-- mukaan way--

126
00:05:51,500 --> 00:05:54,580
on yleinen asia
solmu, joka on keskellä.

127
00:05:54,580 --> 00:05:56,547
On olemassa pari
ylimääräisiä varoituksista, että olet

128
00:05:56,547 --> 00:05:59,380
täytyy harkita, kun olet poistat
aivan listan alkuun

129
00:05:59,380 --> 00:06:01,040
tai erittäin luettelon loppuun.

130
00:06:01,040 --> 00:06:03,730
On pari erityinen
kulma tapauksissa käsitellä siellä.

131
00:06:03,730 --> 00:06:07,960
>> Joten tämä toimii poistamatta solmu
keskellä list-- joka

132
00:06:07,960 --> 00:06:11,550
on oikeutettu osoitin eteenpäin
ja laillinen osoitin taaksepäin,

133
00:06:11,550 --> 00:06:14,460
oikeutettu Edellinen ja Seuraava osoitin.

134
00:06:14,460 --> 00:06:16,530
Jälleen, jos olet työskennellyt
kanssa päättyy, sinun

135
00:06:16,530 --> 00:06:18,500
täytyy käsitellä niitä
hieman eri tavalla,

136
00:06:18,500 --> 00:06:19,570
ja emme aio
puhua siitä nyt.

137
00:06:19,570 --> 00:06:21,319
Mutta voit luultavasti
selvittää, mitä on

138
00:06:21,319 --> 00:06:24,610
tehtävä vain katsomalla tämän videon.

139
00:06:24,610 --> 00:06:28,910
>> Joten olemme eristetty X. X on solmu
haluamme poistaa listalta.

140
00:06:28,910 --> 00:06:30,140
Mitä me teemme?

141
00:06:30,140 --> 00:06:32,800
Ensinnäkin, meidän täytyy järjestää
ulkopuolella viitteitä.

142
00:06:32,800 --> 00:06:35,815
Meidän on järjestää
9: n vieressä ohittaa 13

143
00:06:35,815 --> 00:06:38,030
ja valitse 10-- joka
on mitä olemme juuri tehneet.

144
00:06:38,030 --> 00:06:41,180
Ja meidän on myös
järjestää 10: n Edellinen

145
00:06:41,180 --> 00:06:44,610
osoittamaan 9 sijasta osoittaa 13.

146
00:06:44,610 --> 00:06:46,490
>> Niin edelleen, tämä oli
kaavio aloittaa.

147
00:06:46,490 --> 00:06:47,730
Tämä oli meidän ketju.

148
00:06:47,730 --> 00:06:51,027
Meidän on ohittaa 13,
mutta meidän on myös säilyttää

149
00:06:51,027 --> 00:06:52,110
eheyden luettelon.

150
00:06:52,110 --> 00:06:54,680
Emme halua menettää
tiedot kumpaankin suuntaan.

151
00:06:54,680 --> 00:06:59,620
Joten meidän täytyy järjestää
viitteitä huolellisesti

152
00:06:59,620 --> 00:07:02,240
joten emme katkaisemiseksi ollenkaan.

153
00:07:02,240 --> 00:07:05,710
>> Voimme siis sanoa 9 Next osoitin
viittaa samaan paikkaan

154
00:07:05,710 --> 00:07:08,040
että kolmetoista Next
osoitin juuri nyt.

155
00:07:08,040 --> 00:07:10,331
Koska olemme lopulta
menossa haluavat ohittaa 13.

156
00:07:10,331 --> 00:07:13,750
Joten missä 13 pistettä Seuraavaksi
haluavat yhdeksän kohtaan siellä sijaan.

157
00:07:13,750 --> 00:07:15,200
Niin se siitä.

158
00:07:15,200 --> 00:07:20,370
Ja sitten missä 13 pistettä takaisin
on, mitä tulee ennen 13,

159
00:07:20,370 --> 00:07:24,800
Haluamme 10 pisteeseen
sen, että sen sijaan 13.

160
00:07:24,800 --> 00:07:29,290
Nyt huomaa, jos noudatat
nuolet, voimme pudottaa 13

161
00:07:29,290 --> 00:07:32,380
ilman todella menettämättä mitään tietoa.

162
00:07:32,380 --> 00:07:36,002
Olemme säilyttäneet eheyden luettelon,
liikkuvat sekä eteen- ja taaksepäin.

163
00:07:36,002 --> 00:07:38,210
Ja sitten voimme vain eräänlainen
ja puhdistaa sen hieman

164
00:07:38,210 --> 00:07:40,930
vetämällä luettelon yhdessä.

165
00:07:40,930 --> 00:07:43,270
Joten me jäsensi
viitteitä kummallakin puolella.

166
00:07:43,270 --> 00:07:46,231
Ja sitten me vapautti X
solmu, joka sisälsi 13,

167
00:07:46,231 --> 00:07:47,480
ja emme katkaisemiseksi.

168
00:07:47,480 --> 00:07:50,980
Joten teimme hyvää.

169
00:07:50,980 --> 00:07:53,000
>> Lopullinen huomautus täällä linkitettyjen listojen.

170
00:07:53,000 --> 00:07:55,990
Joten molemmat singly- ja kaksinkertaisesti sidottu
luettelot, kuten olemme nähneet,

171
00:07:55,990 --> 00:07:58,959
tuki todella tehokas lisäys
ja poistetaan elementtejä.

172
00:07:58,959 --> 00:08:00,750
Voit melko paljon tehdä
se jatkuvasti ajan.

173
00:08:00,750 --> 00:08:03,333
Mitä meidän on tehtävä poistaa
elementti vain toinen sitten?

174
00:08:03,333 --> 00:08:04,440
Muutimme yksi osoitin.

175
00:08:04,440 --> 00:08:05,920
Muutimme toinen osoitin.

176
00:08:05,920 --> 00:08:07,915
Me vapautti X-- kesti kolme toimintaa.

177
00:08:07,915 --> 00:08:14,500
Se vie aina kolme toimintaansa
poistaa että node-- vapaa solmuun.

178
00:08:14,500 --> 00:08:15,280
>> Miten lisätä?

179
00:08:15,280 --> 00:08:17,280
No, olemme vain aina
tacking alussa

180
00:08:17,280 --> 00:08:19,400
jos me lisäämällä tehokkaasti.

181
00:08:19,400 --> 00:08:21,964
Joten meidän on rearrange--
riippuen jos se on

182
00:08:21,964 --> 00:08:24,380
singly- tai kaksinkertaisesti sidottu
luettelo, saatamme tarvita tehdä kolme

183
00:08:24,380 --> 00:08:26,824
tai neljä toimintaa max.

184
00:08:26,824 --> 00:08:28,365
Mutta jälleen kerran, se on aina kolme tai neljä.

185
00:08:28,365 --> 00:08:30,531
Sillä ei ole väliä kuinka monta
elementit ovat listallamme,

186
00:08:30,531 --> 00:08:33,549
se on aina kolme tai neljä operations--
kuten poisto on aina

187
00:08:33,549 --> 00:08:35,320
kolme tai neljä toimintaa.

188
00:08:35,320 --> 00:08:36,919
Se on jatkuva aika.

189
00:08:36,919 --> 00:08:38,169
Niin se on todella suuri.

190
00:08:38,169 --> 00:08:40,620
>> Kanssa paneelit, teemme
jotain lisäyslajittelun.

191
00:08:40,620 --> 00:08:44,739
Olet luultavasti muistaa, että lisäys
lajitella ei ole vakio algoritmi.

192
00:08:44,739 --> 00:08:46,030
Se on oikeastaan ​​aika kallista.

193
00:08:46,030 --> 00:08:48,840
Joten tämä on paljon parempi lisäämällä.

194
00:08:48,840 --> 00:08:51,840
Mutta kuten mainitsin
yksittäin-linkitetty lista video,

195
00:08:51,840 --> 00:08:54,030
meillä haittapuoli täälläkin, eikö?

196
00:08:54,030 --> 00:08:57,580
Olemme menettäneet kyvyn
satunnaisesti käyttää elementtejä.

197
00:08:57,580 --> 00:09:02,310
Emme voi sanoa, haluan elementti numero neljä
tai osa numero 10 linkitetty lista

198
00:09:02,310 --> 00:09:04,990
samalla tavalla kuin voimme
tehdä sen array

199
00:09:04,990 --> 00:09:08,630
tai voimme vain suoraan indeksi
meidän array elementti.

200
00:09:08,630 --> 00:09:10,930
>> Ja niin yritetään löytää
elementti liittyy list--

201
00:09:10,930 --> 00:09:15,880
jos haku on important--
voi vastedes ottaa lineaarinen aikaa.

202
00:09:15,880 --> 00:09:18,330
Koska lista pitenee, se
saattaa kestää yksi lisävaihe

203
00:09:18,330 --> 00:09:22,644
jokaisesta elementti luettelossa
jotta löytää mitä etsimme.

204
00:09:22,644 --> 00:09:23,560
Joten siellä on kompromisseista.

205
00:09:23,560 --> 00:09:25,780
On hieman pro
ja con elementti tässä.

206
00:09:25,780 --> 00:09:29,110
>> Ja kaksinkertaisesti sidottu luettelot eivät ole
viime millaisia ​​tietoja rakenteen yhdistelmä

207
00:09:29,110 --> 00:09:32,840
että me puhumme,
kun kaikki perusrakenneosia

208
00:09:32,840 --> 00:09:34,865
lohkojen C koota.

209
00:09:34,865 --> 00:09:37,900
Koska itse asiassa, voimme
jopa tehdä paremmin kuin tämä

210
00:09:37,900 --> 00:09:41,970
luoda tietojen rakenne, joka
voit ehkä etsiä

211
00:09:41,970 --> 00:09:43,360
jatkuvassa aikaa.

212
00:09:43,360 --> 00:09:46,080
Mutta lisää, että toinen video.

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

214
00:09:47,150 --> 00:09:49,050
Tämä on CS50.

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