1
00:00:00,000 --> 00:00:02,832
>> [MUSIC SPILLE]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, så på
dette punktet i kurset,

4
00:00:08,560 --> 00:00:15,300
vi har dekket mye av det grunnleggende C.
Vi vet mye om variabler, matriser,

5
00:00:15,300 --> 00:00:17,610
pekere, alt det gode ting.

6
00:00:17,610 --> 00:00:21,610
De er alle slags inne
i å se som det grunnleggende,

7
00:00:21,610 --> 00:00:23,880
men vi kan gjøre mer, ikke sant?

8
00:00:23,880 --> 00:00:27,930
Vi kan kombinere ting
sammen på interessante måter.

9
00:00:27,930 --> 00:00:31,010
>> Og så la oss gjøre det, la oss starte
å armen ut av hva C gir oss,

10
00:00:31,010 --> 00:00:35,270
og begynne å lage vår egen data
strukturer ved hjelp av disse bygning

11
00:00:35,270 --> 00:00:40,590
blokker sammen for å gjøre noe
virkelig verdifull og nyttig.

12
00:00:40,590 --> 00:00:43,420
En måte vi kan gjøre dette på er
å snakke om samlinger.

13
00:00:43,420 --> 00:00:48,360
Så så langt har vi hatt en type data
struktur for samlinger

14
00:00:48,360 --> 00:00:51,030
av like verdier, tilsvarende verdier.

15
00:00:51,030 --> 00:00:52,350
Det ville være en matrise.

16
00:00:52,350 --> 00:00:57,020
Vi har samlinger av heltall, eller
samlinger av figurer og så videre.

17
00:00:57,020 --> 00:01:00,890
>> Strukturer er også sortere av en data
struktur for innsamling av opplysninger

18
00:01:00,890 --> 00:01:03,220
men det er ikke for å samle like verdier.

19
00:01:03,220 --> 00:01:08,090
Det blander vanligvis forskjellige datatyper
sammen inne i en enkelt boks.

20
00:01:08,090 --> 00:01:10,750
Men det er ikke i seg selv
brukes til å kjede sammen

21
00:01:10,750 --> 00:01:16,920
eller koble sammen lignende
elementer, som en matrise.

22
00:01:16,920 --> 00:01:20,960
Arrays er stor for
element se opp, men tilbakekalling

23
00:01:20,960 --> 00:01:24,262
at det er svært vanskelig
å sette inn i en matrise,

24
00:01:24,262 --> 00:01:26,470
med mindre vi setter på
helt på slutten av denne matrisen.

25
00:01:26,470 --> 00:01:29,730
>> Og det beste eksemplet jeg har
for det er innsetting sort.

26
00:01:29,730 --> 00:01:31,650
Hvis du husker vår video
på innsetting sortere,

27
00:01:31,650 --> 00:01:34,110
Det var en masse
utgifter som er involvert i å ha

28
00:01:34,110 --> 00:01:37,970
å plukke opp elementer, og flytte dem
ut av veien for å passe noe

29
00:01:37,970 --> 00:01:41,290
inn i midten av klyngen.

30
00:01:41,290 --> 00:01:44,690
Arrays også lider av en annen
Problemet, som er manglende fleksibilitet.

31
00:01:44,690 --> 00:01:47,150
Når vi erklære en matrise,
vi får ett skudd på den.

32
00:01:47,150 --> 00:01:49,790
Vi får å si, jeg vil ha
dette mange elementer.

33
00:01:49,790 --> 00:01:51,940
Kan være 100, det kan
være 1000, det kan

34
00:01:51,940 --> 00:01:55,930
være x der x er et tall som brukeren
ga oss en melding eller på kommando

35
00:01:55,930 --> 00:01:56,630
linjen.

36
00:01:56,630 --> 00:01:59,905
>> Men vi får bare ett skudd på det, vi
får ikke til så si oh, faktisk jeg

37
00:01:59,905 --> 00:02:04,360
trengte 101, eller jeg trengte x pluss 20.

38
00:02:04,360 --> 00:02:07,910
For sent, har vi allerede erklært
array, og hvis vi ønsker å få 101 eller x

39
00:02:07,910 --> 00:02:12,050
pluss 20, må vi erklære
en helt annen matrise,

40
00:02:12,050 --> 00:02:15,540
kopiere alle elementene i matrisen
over, og da har vi nok.

41
00:02:15,540 --> 00:02:19,880
Og hva om vi tar feil igjen, hva
hvis vi faktisk trenger 102, eller x pluss 40,

42
00:02:19,880 --> 00:02:21,970
vi må gjøre dette igjen.

43
00:02:21,970 --> 00:02:26,250
Slik at de er svært lite fleksible
for å endre størrelse våre data,

44
00:02:26,250 --> 00:02:29,360
men hvis vi kombinerer sammen noen
av de grunnleggende at vi allerede har

45
00:02:29,360 --> 00:02:33,230
lært om pekere og strukturer,
Spesielt ved bruk av dynamisk minne

46
00:02:33,230 --> 00:02:36,180
tildeling med malloc, vi
kan sette disse bitene sammen

47
00:02:36,180 --> 00:02:40,960
å skape en ny data structure-- en
enkeltvis lenket liste vi kan say--

48
00:02:40,960 --> 00:02:45,400
som tillater oss å vokse og
krympe en samling verdier

49
00:02:45,400 --> 00:02:48,800
og vi vil ikke ha noen bortkastet plass.

50
00:02:48,800 --> 00:02:53,320
>> Så igjen, kaller vi denne ideen,
denne forestillingen, en lenket liste.

51
00:02:53,320 --> 00:02:56,320
Spesielt i denne videoen er vi
snakker om enkeltvis lenket liste,

52
00:02:56,320 --> 00:02:59,185
og deretter en annen video vi skal snakke
om dobbelt lenkede lister, som

53
00:02:59,185 --> 00:03:01,560
er bare en variant av et tema her.

54
00:03:01,560 --> 00:03:05,200
Men en enkeltvis lenket liste
består av noder,

55
00:03:05,200 --> 00:03:08,559
noder bare å være en abstrakt term--
det er bare noe jeg ringer

56
00:03:08,559 --> 00:03:10,350
det er en slags
struktur, i utgangspunktet er jeg?

57
00:03:10,350 --> 00:03:16,190
Bare kommer til å kalle det en node-- og dette
node har to medlemmer, eller to felt.

58
00:03:16,190 --> 00:03:20,300
Det har data, vanligvis en
heltall, et tegn flyte,

59
00:03:20,300 --> 00:03:23,790
eller kan være noen annen datatype
at du har definert med en type def.

60
00:03:23,790 --> 00:03:29,290
Og den inneholder en peker til
en annen node av samme type.

61
00:03:29,290 --> 00:03:34,710
>> Så vi har to ting inni
denne noden, data og en peker

62
00:03:34,710 --> 00:03:36,380
til en annen node.

63
00:03:36,380 --> 00:03:39,370
Og hvis du begynner å visualisere
dette, kan du tenke på det

64
00:03:39,370 --> 00:03:42,280
som en kjede av noder som
er koblet sammen.

65
00:03:42,280 --> 00:03:45,070
Vi har den første node, det
inneholder data, og en peker

66
00:03:45,070 --> 00:03:49,110
til den andre noden som inneholder
data, og en peker til den tredje noden.

67
00:03:49,110 --> 00:03:52,940
Og så det er derfor vi kaller det en
lenket liste, de er koblet sammen.

68
00:03:52,940 --> 00:03:56,070
>> Hva gjør denne spesiell
nodestruktur ser ut?

69
00:03:56,070 --> 00:04:01,120
Vel, hvis du husker fra vår video på
definere tilpassede typer, med type def,

70
00:04:01,120 --> 00:04:05,400
vi kan definere en structure-- og
skriver definere en struktur som dette.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, og da er jeg
bruke ordet verdi her vilkårlig

72
00:04:11,240 --> 00:04:13,891
for å indikere hvilken som helst datatype egentlig.

73
00:04:13,891 --> 00:04:16,890
Du kan passere på et heltall eller flyte,
du kan få hva du vil.

74
00:04:16,890 --> 00:04:19,389
Det er ikke begrenset til bare
heltall, eller noe sånt.

75
00:04:19,389 --> 00:04:22,790
Så verdien er bare en vilkårlig
datatype, og deretter en peker

76
00:04:22,790 --> 00:04:26,310
til en annen node av samme type.

77
00:04:26,310 --> 00:04:29,690
>> Nå er det en liten fangst
her med å definere en struktur

78
00:04:29,690 --> 00:04:33,030
når det er en selvrefererende struktur.

79
00:04:33,030 --> 00:04:35,340
Jeg må ha en midlertidig
nevne for min struktur.

80
00:04:35,340 --> 00:04:37,640
På slutten av dagen I
klart vil kalle det

81
00:04:37,640 --> 00:04:43,030
SLL node, det er til syvende og sist den nye
nevne en del av min type definisjon,

82
00:04:43,030 --> 00:04:47,450
men jeg kan ikke bruke sll node
i midten av dette.

83
00:04:47,450 --> 00:04:51,430
Årsaken er, jeg har ikke
skapt en type som heter sll node

84
00:04:51,430 --> 00:04:55,200
før jeg traff denne siste punktet her.

85
00:04:55,200 --> 00:04:59,720
Frem til det punktet, må jeg ha
en annen måte å referere til denne datatypen.

86
00:04:59,720 --> 00:05:02,440
>> Og dette er en selv
referensiell datatype.

87
00:05:02,440 --> 00:05:06,314
Den, er en datatype for en
struktur som inneholder en data,

88
00:05:06,314 --> 00:05:08,480
og en peker til en annen
struktur av samme type.

89
00:05:08,480 --> 00:05:11,750
Så jeg må være i stand til å referere til
dette datatype i det minste midlertidig,

90
00:05:11,750 --> 00:05:14,910
så gir det en midlertidig
Navnet på struct sllist

91
00:05:14,910 --> 00:05:18,540
tillater meg å så si at jeg vil ha en
Peker til en annen struct sllist,

92
00:05:18,540 --> 00:05:24,690
en struct sllist stjerne, og deretter
etter at jeg har fullført definisjon,

93
00:05:24,690 --> 00:05:27,220
Jeg kan nå kalle denne typen en sll node.

94
00:05:27,220 --> 00:05:30,520
>> Så det er derfor du ser det er
et midlertidig navn her,

95
00:05:30,520 --> 00:05:31,879
men et permanent navn her.

96
00:05:31,879 --> 00:05:33,920
Noen ganger kan du se
definisjoner av struktur,

97
00:05:33,920 --> 00:05:36,570
for eksempel, som ikke er
selvrefererende, at

98
00:05:36,570 --> 00:05:39,390
har ikke en Specifier navn her.

99
00:05:39,390 --> 00:05:43,040
Det ville bare si typedef struct,
åpne klammeparentes og deretter definere det.

100
00:05:43,040 --> 00:05:45,620
Men hvis du er struct er selv
henvisnings, som denne er,

101
00:05:45,620 --> 00:05:49,010
må du angi en
midlertidig typenavn.

102
00:05:49,010 --> 00:05:51,310
Men til slutt, nå
at vi har gjort dette,

103
00:05:51,310 --> 00:05:53,620
Vi kan bare henvise til
disse nodene, disse enheter,

104
00:05:53,620 --> 00:05:57,900
som SLL noder for formål
av resten av denne videoen.

105
00:05:57,900 --> 00:06:00,900
>> Greit, så vi vet hvordan de skal
skape en lenket liste node.

106
00:06:00,900 --> 00:06:03,240
Vi vet hvordan du definerer
en lenket liste node.

107
00:06:03,240 --> 00:06:06,670
Nå, hvis vi kommer til å starte
bruke dem til å samle inn informasjon,

108
00:06:06,670 --> 00:06:10,360
det er et par av operasjoner vi
trenger å forstå og jobbe med.

109
00:06:10,360 --> 00:06:12,860
Vi trenger å vite hvordan du oppretter
en lenket liste ut av løse luften.

110
00:06:12,860 --> 00:06:14,901
Hvis det er ingen liste allerede,
Vi ønsker å starte en.

111
00:06:14,901 --> 00:06:16,960
Så vi må være i stand
for å lage en lenket liste,

112
00:06:16,960 --> 00:06:19,130
vi må trolig søke
via lenken liste

113
00:06:19,130 --> 00:06:21,830
å finne et element vi leter etter.

114
00:06:21,830 --> 00:06:24,430
Vi må være i stand til å sette inn
nye ting inn i listen,

115
00:06:24,430 --> 00:06:25,930
Vi ønsker vår liste for å kunne vokse.

116
00:06:25,930 --> 00:06:28,638
Og på samme måte, vil vi være i stand
å slette ting fra vår liste,

117
00:06:28,638 --> 00:06:30,250
Vi ønsker vår liste for å være i stand til å krympe.

118
00:06:30,250 --> 00:06:32,160
Og på slutten av vår
programmer, særlig

119
00:06:32,160 --> 00:06:34,550
hvis du husker at vi er
dynamisk tildele minne

120
00:06:34,550 --> 00:06:38,337
å bygge disse listene typisk,
vi ønsker å frigjøre alle som minne

121
00:06:38,337 --> 00:06:39,670
når vi er ferdig å jobbe med det.

122
00:06:39,670 --> 00:06:44,627
Og så må vi være i stand til å slette en
Hele lenket liste i ett mislykkes nedslag.

123
00:06:44,627 --> 00:06:46,460
Så la oss gå gjennom
noen av disse operasjonene

124
00:06:46,460 --> 00:06:51,192
og hvordan vi kan visualisere dem,
snakker i pseudokode spesifikt.

125
00:06:51,192 --> 00:06:53,150
Så vi ønsker å skape en
lenket liste, så kanskje vi

126
00:06:53,150 --> 00:06:56,480
ønsker å definere en funksjon
med denne prototypen.

127
00:06:56,480 --> 00:07:01,690
SLL node stjerne, skape, og jeg passert
i ett argument, en oppkonstruert data

128
00:07:01,690 --> 00:07:05,530
skriver igjen, av noen vilkårlig datatype.

129
00:07:05,530 --> 00:07:10,482
Men jeg returning-- denne funksjonen
tilbake til meg en peker til en enkeltvis

130
00:07:10,482 --> 00:07:11,190
lenket liste node.

131
00:07:11,190 --> 00:07:14,050
Igjen, vi prøver å skape
en lenket liste ut av løse luften,

132
00:07:14,050 --> 00:07:17,900
så jeg trenger en peker til
den listen når jeg er ferdig.

133
00:07:17,900 --> 00:07:19,420
>> Så hva er fremgangsmåten involvert her?

134
00:07:19,420 --> 00:07:20,960
Vel, jeg er første
kommer til å gjøre er dynamisk

135
00:07:20,960 --> 00:07:22,550
tildele plass for en ny node.

136
00:07:22,550 --> 00:07:26,689
Igjen, vi skaper den ut av tynn
luft, så vi trenger å malloc plass for det.

137
00:07:26,689 --> 00:07:28,480
Og selvfølgelig, umiddelbart
etter at vi malloc,

138
00:07:28,480 --> 00:07:31,692
vi alltid sjekke for å være sikker på at vår
pointer-- vi ikke få tilbake null.

139
00:07:31,692 --> 00:07:33,650
Fordi hvis vi prøver og
ærbødighet en nullpeker,

140
00:07:33,650 --> 00:07:36,190
vi kommer til å lide en
segfault og vi ønsker ikke det.

141
00:07:36,190 --> 00:07:39,510
>> Da vil vi gjerne fylle på feltet,
vi ønsker å initialverdifeltet

142
00:07:39,510 --> 00:07:41,690
og initial neste felt.

143
00:07:41,690 --> 00:07:45,450
Og så ønsker vi to-- slutt som
funksjon prototype indicates-- vi ønsker

144
00:07:45,450 --> 00:07:49,940
å returnere en peker til en sll node.

145
00:07:49,940 --> 00:07:51,710
Så hva gjør dette ser ut visuelt?

146
00:07:51,710 --> 00:07:55,230
Vel, først skal vi dynamisk
tildele plass for en ny SLL node,

147
00:07:55,230 --> 00:07:58,320
så vi malloc-- det er
en visuell representasjon

148
00:07:58,320 --> 00:08:00,020
av noden vi nettopp opprettet.

149
00:08:00,020 --> 00:08:02,757
Og vi må du kontrollere
det er ikke null-- i dette tilfellet,

150
00:08:02,757 --> 00:08:04,840
bildet ville ikke ha
vist seg hvis det var null,

151
00:08:04,840 --> 00:08:07,298
vi ville ha gått tom for minne,
så vi er godt å gå dit.

152
00:08:07,298 --> 00:08:10,200
Så nå er vi videre til trinn C,
initialisere noder verdifeltet.

153
00:08:10,200 --> 00:08:12,280
Vel, basert på denne funksjonen
kaller jeg bruker her,

154
00:08:12,280 --> 00:08:16,700
ser ut som jeg ønsker å passere på 6,
Så jeg skal seks i verdifeltet.

155
00:08:16,700 --> 00:08:18,865
Nå initial neste felt.

156
00:08:18,865 --> 00:08:21,640
Vel, hva skal jeg gjøre der,
det er ingenting ved siden, høyre,

157
00:08:21,640 --> 00:08:23,600
dette er den eneste på listen.

158
00:08:23,600 --> 00:08:27,206
Så hva er det neste på listen?

159
00:08:27,206 --> 00:08:29,660
>> Det bør ikke peke på noe, ikke sant.

160
00:08:29,660 --> 00:08:33,600
Det er ingenting annet der, så hva er
konseptet vi vet om som er nothing--

161
00:08:33,600 --> 00:08:35,638
pekere til ingenting?

162
00:08:35,638 --> 00:08:37,929
Det bør være kanskje vi ønsker
å sette en nullpeker der,

163
00:08:37,929 --> 00:08:40,178
og jeg skal representere null
pekeren som bare en rød boks,

164
00:08:40,178 --> 00:08:41,559
vi kan ikke gå videre.

165
00:08:41,559 --> 00:08:44,430
Som vi skal se litt senere,
vi vil ha slutt kjeder

166
00:08:44,430 --> 00:08:46,330
piler koble
disse nodene sammen,

167
00:08:46,330 --> 00:08:48,480
men når du treffer
røde boksen, det er null,

168
00:08:48,480 --> 00:08:51,150
vi kan ikke gå videre,
det er slutten av listen.

169
00:08:51,150 --> 00:08:53,960
>> Og til slutt, vi ønsker bare å
returnere en peker til denne noden.

170
00:08:53,960 --> 00:08:56,160
Så vi vil kalle det nye,
og vil returnere nytt

171
00:08:56,160 --> 00:08:59,370
slik at den kan brukes i
uansett funksjon opprettet den.

172
00:08:59,370 --> 00:09:03,100
Så det vi går, Vi har laget en enkeltvis
lenket liste node ut av løse luften,

173
00:09:03,100 --> 00:09:05,920
og nå har vi en liste vi kan jobbe med.

174
00:09:05,920 --> 00:09:08,260
>> Nå, la oss si at vi allerede
har en stor kjede,

175
00:09:08,260 --> 00:09:09,800
og vi ønsker å finne noe i det.

176
00:09:09,800 --> 00:09:12,716
Og vi vil ha en funksjon som kommer
å returnere sant eller usant, avhengig

177
00:09:12,716 --> 00:09:15,840
om hvorvidt en verdi eksisterer i den listen.

178
00:09:15,840 --> 00:09:18,160
En funksjon prototype, eller
erklæringen for denne funksjonen,

179
00:09:18,160 --> 00:09:23,320
kan se ut som dette-- bool finne, og
så vi ønsker å passere på to argumenter.

180
00:09:23,320 --> 00:09:26,996
>> Den første er en peker til
første elementet i lenket liste.

181
00:09:26,996 --> 00:09:29,620
Dette er faktisk noe du vil
alltid ønsker å holde styr på,

182
00:09:29,620 --> 00:09:33,110
og faktisk kan være noe som
du selv satt i en global variabel.

183
00:09:33,110 --> 00:09:35,360
Når du oppretter en liste,
du alltid, alltid

184
00:09:35,360 --> 00:09:38,990
ønsker å holde styr på de aller
første elementet på listen.

185
00:09:38,990 --> 00:09:43,690
På den måten kan du referere til alle de andre
elementer ved bare å følge kjeden,

186
00:09:43,690 --> 00:09:47,300
uten å måtte holde pekere
intakt til hvert enkelt element.

187
00:09:47,300 --> 00:09:50,920
Du trenger bare å holde styr på den første
en hvis de er alle lenket sammen.

188
00:09:50,920 --> 00:09:52,460
>> Og deretter den andre tingen
vi kjører i gang

189
00:09:52,460 --> 00:09:54,376
er vilkårlig some--
uansett datatype vi er

190
00:09:54,376 --> 00:09:59,640
leter etter det er innsiden av
forhåpentligvis en av nodene i listen.

191
00:09:59,640 --> 00:10:00,980
Så hva er fremgangsmåten?

192
00:10:00,980 --> 00:10:04,250
Vel, er det første vi gjør
vi skape en tverrgående peker

193
00:10:04,250 --> 00:10:06,015
og peker på listene hodet.

194
00:10:06,015 --> 00:10:08,890
Vel, hvorfor skal vi gjøre det vi allerede
har en peker på listene hodet,

195
00:10:08,890 --> 00:10:10,974
hvorfor ikke vi bare flytte den rundt?

196
00:10:10,974 --> 00:10:13,140
Vel, som jeg sa,
det er veldig viktig for oss

197
00:10:13,140 --> 00:10:17,580
å alltid holde styr på
aller første element i listen.

198
00:10:17,580 --> 00:10:21,270
Og så det er faktisk bedre
for å lage en kopi av det,

199
00:10:21,270 --> 00:10:25,350
og bruke den til å bevege seg rundt så vi aldri
uhell bevege seg bort, eller vi alltid

200
00:10:25,350 --> 00:10:30,430
har en peker på et punkt som ligger
rett på det første elementet på listen.

201
00:10:30,430 --> 00:10:33,290
Så det er bedre å lage en
andre en som vi bruker til å bevege seg.

202
00:10:33,290 --> 00:10:35,877
>> Så vi bare sammenligne hvorvidt
verdifeltet på den noden

203
00:10:35,877 --> 00:10:38,960
er det vi leter etter, og hvis det er
ikke, vi bare flytte til neste node.

204
00:10:38,960 --> 00:10:41,040
Og vi fortsette med det
over, og over og over,

205
00:10:41,040 --> 00:10:44,811
før vi enten finne
elementet, eller vi treffer

206
00:10:44,811 --> 00:10:47,310
null-- vi har nådd slutten
av listen, og det er ikke der.

207
00:10:47,310 --> 00:10:50,540
Dette bør forhåpentligvis ringe en bjelle
til deg som bare lineær søk,

208
00:10:50,540 --> 00:10:54,430
vi bare replikere den i
en enkeltvis lenket liste struktur

209
00:10:54,430 --> 00:10:56,280
stedet for å bruke en matrise for å gjøre det.

210
00:10:56,280 --> 00:10:58,210
>> Så her er et eksempel på
en enkeltvis lenket liste.

211
00:10:58,210 --> 00:11:00,043
Denne består av
fem noder, og vi har

212
00:11:00,043 --> 00:11:04,330
en peker til leder av
liste, som kalles listen.

213
00:11:04,330 --> 00:11:07,385
Det første vi vil gjøre er å
igjen, lage, at traversering pekeren.

214
00:11:07,385 --> 00:11:09,760
Så vi har nå to pekere
som peker til det samme.

215
00:11:09,760 --> 00:11:15,025
>> Legg nå merke til her også, jeg gjorde ikke
må malloc noen plass for trav.

216
00:11:15,025 --> 00:11:18,970
Jeg sa ikke trav lik malloc
noe, allerede eksisterer som node,

217
00:11:18,970 --> 00:11:21,160
at plass i minnet finnes allerede.

218
00:11:21,160 --> 00:11:24,290
Så alt jeg egentlig gjør er
å skape et annet peker til den.

219
00:11:24,290 --> 00:11:28,210
Jeg er ikke mallocing en ekstra
plass, må bare nå to pekere

220
00:11:28,210 --> 00:11:31,370
peker på det samme.

221
00:11:31,370 --> 00:11:33,710
>> Så er to hva jeg leter etter?

222
00:11:33,710 --> 00:11:37,220
Vel, nei, så i stedet jeg er
kommer til å flytte til den neste.

223
00:11:37,220 --> 00:11:41,740
Så i utgangspunktet vil jeg si,
trav tilsvarer trav neste.

224
00:11:41,740 --> 00:11:43,630
Er tre det jeg leter etter, nei.

225
00:11:43,630 --> 00:11:45,780
Så jeg fortsetter å gå
gjennom, inntil eventuelt

226
00:11:45,780 --> 00:11:48,690
komme til 6 som er hva jeg ser
basert på beregnet funksjon samtale

227
00:11:48,690 --> 00:11:51,600
Jeg har på toppen
der, og så er jeg ferdig.

228
00:11:51,600 --> 00:11:54,150
>> Nå, hva om elementet jeg er
leter etter er ikke i listen,

229
00:11:54,150 --> 00:11:55,510
er det fortsatt kommer til å fungere?

230
00:11:55,510 --> 00:11:57,120
Vel, legge merke til at listen
her er litt forskjellig,

231
00:11:57,120 --> 00:11:59,410
og dette er en annen ting som er
viktig med koblede lister,

232
00:11:59,410 --> 00:12:01,780
du trenger ikke å bevare
dem i en bestemt rekkefølge.

233
00:12:01,780 --> 00:12:05,390
Du kan hvis du vil, men
du har kanskje allerede lagt merke til

234
00:12:05,390 --> 00:12:09,310
at vi ikke holde styr på
hva antall element vi er på.

235
00:12:09,310 --> 00:12:13,150
>> Og det er liksom en handel som vi
har med lenket liste vers arrays,

236
00:12:13,150 --> 00:12:15,300
det har vi ikke
random access lenger.

237
00:12:15,300 --> 00:12:18,150
Vi kan ikke bare si, jeg vil ha
å gå til 0. element,

238
00:12:18,150 --> 00:12:21,410
eller den sjette element av min array,
som jeg kan gjøre i en matrise.

239
00:12:21,410 --> 00:12:25,080
Jeg kan ikke si at jeg ønsker å gå til
0. element, eller det sjette element,

240
00:12:25,080 --> 00:12:30,360
eller den 25. element av min lenket liste,
det er ingen indeks knyttet til dem.

241
00:12:30,360 --> 00:12:33,660
Og slik er det ikke virkelig betyr noe
hvis vi bevare vår liste i orden.

242
00:12:33,660 --> 00:12:36,080
Hvis du vil kan du
sikkert kan, men det er

243
00:12:36,080 --> 00:12:38,567
ingen grunn til at de trenger å
bli bevart i den rekkefølgen.

244
00:12:38,567 --> 00:12:40,400
Så igjen, la oss prøve og
finne 6 i denne listen.

245
00:12:40,400 --> 00:12:43,200
Vel, vi begynner på
begynner, finner vi ikke seks,

246
00:12:43,200 --> 00:12:47,690
og da har vi ikke fortsette å finne
6, før vi til slutt får til her.

247
00:12:47,690 --> 00:12:52,790
Så akkurat nå trav peker til noden
inneholder åtte, og seks er ikke der.

248
00:12:52,790 --> 00:12:55,250
>> Så neste skritt vil være
for å gå til neste pekeren,

249
00:12:55,250 --> 00:12:57,440
så si trav tilsvarer trav neste.

250
00:12:57,440 --> 00:13:00,750
Vel, trav neste, angitt med
den røde boksen der, er null.

251
00:13:00,750 --> 00:13:03,020
Så det er ikke noe annet å
gå, og så på dette punktet

252
00:13:03,020 --> 00:13:06,120
Vi kan konkludere med at vi har nådd
enden av lenket liste,

253
00:13:06,120 --> 00:13:07,190
og 6 er ikke i der.

254
00:13:07,190 --> 00:13:10,980
Og det ville bli returnert
falsk i dette tilfellet.

255
00:13:10,980 --> 00:13:14,540
>> OK, hvordan setter vi en ny
node inn i lenket liste?

256
00:13:14,540 --> 00:13:17,310
Så vi har vært i stand til å skape
en lenket liste ut av ingenting,

257
00:13:17,310 --> 00:13:19,370
men vi sannsynligvis vil
bygge opp en kjede og ikke

258
00:13:19,370 --> 00:13:22,620
skape en haug med forskjellige lister.

259
00:13:22,620 --> 00:13:25,700
Vi ønsker å ha en liste som
har en haug med noder i det,

260
00:13:25,700 --> 00:13:28,040
ikke en haug med lister med én node.

261
00:13:28,040 --> 00:13:31,260
Så vi kan ikke bare fortsette å bruke Lag
funksjon vi definert tidligere, nå er vi

262
00:13:31,260 --> 00:13:33,860
ønsker å sette inn en
liste som allerede eksisterer.

263
00:13:33,860 --> 00:13:36,499
>> Så dette tilfellet, skal vi
å passere i to argumenter,

264
00:13:36,499 --> 00:13:39,290
pekeren til leder av det
lenket liste som vi ønsker å legge til.

265
00:13:39,290 --> 00:13:40,910
Igjen, det er derfor det er så
viktig at vi alltid

266
00:13:40,910 --> 00:13:43,400
holde orden på det, fordi
det er den eneste måten vi virkelig

267
00:13:43,400 --> 00:13:46,690
nødt til å referere til hele listen er
bare ved en peker til det første elementet.

268
00:13:46,690 --> 00:13:49,360
Så vi ønsker å passere i en
Peker til det første elementet,

269
00:13:49,360 --> 00:13:52,226
og hva verdien vi
ønsker å legge til i listen.

270
00:13:52,226 --> 00:13:54,600
Og til slutt denne funksjonen
kommer til å returnere en peker

271
00:13:54,600 --> 00:13:57,980
til den nye sjefen for en lenket liste.

272
00:13:57,980 --> 00:13:59,700
>> Hva er fremgangsmåten involvert her?

273
00:13:59,700 --> 00:14:02,249
Vel, akkurat som med opprette,
vi trenger å dynamisk allokere

274
00:14:02,249 --> 00:14:05,540
plass til en ny node, og kontroller
sikker på at vi ikke går tom for minne, på nytt,

275
00:14:05,540 --> 00:14:07,150
fordi vi bruker malloc.

276
00:14:07,150 --> 00:14:09,080
Så vi ønsker å fylle
og sette inn node,

277
00:14:09,080 --> 00:14:12,730
så sette tall, uansett
val er, inn i noden.

278
00:14:12,730 --> 00:14:17,310
Vi ønsker å sette noden på
begynnelsen av lenket liste.

279
00:14:17,310 --> 00:14:19,619
>> Det er en grunn til at jeg
ønsker å gjøre dette, og det

280
00:14:19,619 --> 00:14:21,910
kan være verdt å ta en andre
til pause videoen her,

281
00:14:21,910 --> 00:14:25,860
og tenke på hvorfor jeg ønsker å
Sett i begynnelsen av en koblet

282
00:14:25,860 --> 00:14:26,589
listen.

283
00:14:26,589 --> 00:14:28,630
Igjen, jeg nevnte tidligere
at det gjør egentlig ikke

284
00:14:28,630 --> 00:14:33,020
rolle om vi bevare det på noen
rekkefølge, så kanskje det er en anelse.

285
00:14:33,020 --> 00:14:36,040
Og du så hva som ville skje hvis vi
ønsket to-- eller fra bare et sekund

286
00:14:36,040 --> 00:14:37,360
siden da vi skulle
gjennom søk deg

287
00:14:37,360 --> 00:14:39,235
kunne se hva som kan
skje hvis vi prøvde

288
00:14:39,235 --> 00:14:41,330
for å sette inn i enden av listen.

289
00:14:41,330 --> 00:14:44,750
Fordi vi ikke har et
pekeren til enden av listen.

290
00:14:44,750 --> 00:14:47,490
>> Så grunnen til at jeg ønsker
å sette i begynnelsen,

291
00:14:47,490 --> 00:14:49,380
er fordi jeg kan gjøre det umiddelbart.

292
00:14:49,380 --> 00:14:52,730
Jeg har en peker i begynnelsen, og
vi vil se dette i et visuelt i et sekund.

293
00:14:52,730 --> 00:14:55,605
Men hvis jeg ønsker å sette inn på slutten,
Jeg må begynne på begynnelsen,

294
00:14:55,605 --> 00:14:58,760
traversere hele veien til den
enden, og deretter slår den på.

295
00:14:58,760 --> 00:15:01,420
Slik det ville bety at
innsetting i enden av listen

296
00:15:01,420 --> 00:15:04,140
ville bli en o n
drift, kommer tilbake

297
00:15:04,140 --> 00:15:06,720
til vår diskusjon av
beregningsorientert kompleksitet.

298
00:15:06,720 --> 00:15:10,140
Det ville blitt en o n operasjon, der
som listen ble større og større,

299
00:15:10,140 --> 00:15:13,310
og større, vil det bli mer og
vanskeligere å tråkle noe

300
00:15:13,310 --> 00:15:14,661
på i enden.

301
00:15:14,661 --> 00:15:17,410
Men det er alltid veldig lett å
tack noe på i begynnelsen,

302
00:15:17,410 --> 00:15:19,060
du er alltid i begynnelsen.

303
00:15:19,060 --> 00:15:21,620
>> Og vi vil se en visuell av dette igjen.

304
00:15:21,620 --> 00:15:24,100
Og så når vi er ferdig, en gang
Vi har satt inn ny node,

305
00:15:24,100 --> 00:15:26,880
vi ønsker å gå tilbake til vår pekeren til
den nye sjefen for en lenket liste, som

306
00:15:26,880 --> 00:15:29,213
siden vi setter på
begynner, faktisk vil være

307
00:15:29,213 --> 00:15:31,060
en peker til noden vi nettopp opprettet.

308
00:15:31,060 --> 00:15:33,280
La oss visualisere dette,
fordi jeg tror det vil hjelpe.

309
00:15:33,280 --> 00:15:36,661
>> Så her er vår liste, den består av
fire elementer, en node som inneholder 15,

310
00:15:36,661 --> 00:15:38,410
som peker til en node
inneholdende 9, hvilken

311
00:15:38,410 --> 00:15:41,370
peker til en node som inneholder 13,
som peker til en node som inneholder

312
00:15:41,370 --> 00:15:44,840
10, som har null
pekeren som sin neste pekeren

313
00:15:44,840 --> 00:15:47,010
så det er slutten av listen.

314
00:15:47,010 --> 00:15:50,200
Så vi ønsker å sette inn et
ny node med verdien 12

315
00:15:50,200 --> 00:15:52,720
i begynnelsen av denne
liste, hva gjør vi?

316
00:15:52,720 --> 00:15:58,770
Vel, først vi malloc plass for
node, og da vi satt 12 i det.

317
00:15:58,770 --> 00:16:02,211
>> Så nå har vi nådd en
beslutningspunkt, ikke sant?

318
00:16:02,211 --> 00:16:03,960
Vi har et par
tips som vi kunne

319
00:16:03,960 --> 00:16:06,770
bevege seg, som man bør vi flytte først?

320
00:16:06,770 --> 00:16:09,250
Skal vi lage 12 poeng å
den nye sjefen for list--

321
00:16:09,250 --> 00:16:13,020
eller unnskylde meg, bør vi gjøre 12
peke på den gamle hodet av listen?

322
00:16:13,020 --> 00:16:15,319
Eller skal vi si at
Listen begynner nå på 12.

323
00:16:15,319 --> 00:16:17,110
Det er en forskjell
der, og vi vil se

324
00:16:17,110 --> 00:16:19,870
på hva som skjer med begge i en andre.

325
00:16:19,870 --> 00:16:23,350
>> Men dette fører til en
stort tema for sidebar,

326
00:16:23,350 --> 00:16:26,280
som er at en av de
vanskeligste ting med lenkede lister

327
00:16:26,280 --> 00:16:30,980
er å ordne pekere
i riktig rekkefølge.

328
00:16:30,980 --> 00:16:34,520
Hvis du flytter ting i rekkefølge,
du kan ende opp ved et uhell

329
00:16:34,520 --> 00:16:36,050
orphaning resten av listen.

330
00:16:36,050 --> 00:16:37,300
Og her er et eksempel på det.

331
00:16:37,300 --> 00:16:40,540
Så la oss gå med ideen of--
vel, vi har nettopp opprettet 12.

332
00:16:40,540 --> 00:16:43,180
Vi vet 12 kommer til å bli
ny leder av listen,

333
00:16:43,180 --> 00:16:47,660
og så hvorfor ikke vi bare flytte
listen pekeren til å peke der.

334
00:16:47,660 --> 00:16:49,070
>> OK, så det er bra.

335
00:16:49,070 --> 00:16:51,560
Så nå hvor kommer 12 neste punkt?

336
00:16:51,560 --> 00:16:54,580
Jeg mener, visuelt vi kan se
at den vil peke til 15,

337
00:16:54,580 --> 00:16:57,250
som mennesker det er veldig tydelig for oss.

338
00:16:57,250 --> 00:17:00,300
Hvordan datamaskinen vet?

339
00:17:00,300 --> 00:17:02,720
Vi har ikke noe
pekte på 15 lenger, ikke sant?

340
00:17:02,720 --> 00:17:05,869
>> Vi har mistet noen mulighet til å referere til 15.

341
00:17:05,869 --> 00:17:11,460
Vi kan ikke si ny pilen ved equals
noe, det er ingenting der.

342
00:17:11,460 --> 00:17:13,510
Faktisk har vi foreldreløs
resten av listen

343
00:17:13,510 --> 00:17:16,465
ved å gjøre det, vi har
brutt ved et uhell kjeden.

344
00:17:16,465 --> 00:17:18,089
Og vi absolutt ikke ønsker å gjøre det.

345
00:17:18,089 --> 00:17:20,000
>> Så la oss gå tilbake og prøve dette igjen.

346
00:17:20,000 --> 00:17:24,060
Kanskje den riktige tingen å gjøre
er å sette 12 neste pekeren

347
00:17:24,060 --> 00:17:28,290
til den gamle hodet av listen først,
da kan vi flytte listen over.

348
00:17:28,290 --> 00:17:30,420
Og i virkeligheten er at
riktig rekkefølge som vi

349
00:17:30,420 --> 00:17:32,836
må følge når vi er
jobbe med enkeltvis lenket liste.

350
00:17:32,836 --> 00:17:36,460
Vi ønsker alltid å koble
nytt element i listen

351
00:17:36,460 --> 00:17:41,010
før vi tar den slags
viktig skritt for å endre

352
00:17:41,010 --> 00:17:43,360
der leder av lenket liste er.

353
00:17:43,360 --> 00:17:46,740
Igjen, det er en så grunnleggende ting,
vi ønsker ikke å miste oversikten over det.

354
00:17:46,740 --> 00:17:49,310
>> Så vi ønsker å være sikker på at
alt er lenket sammen,

355
00:17:49,310 --> 00:17:52,040
før vi flytter at pekeren.

356
00:17:52,040 --> 00:17:55,300
Og så dette ville være riktig rekkefølge,
som er til å koble 12 til listen,

357
00:17:55,300 --> 00:17:57,630
så si at listen starter en 12.

358
00:17:57,630 --> 00:18:00,860
Hvis vi sa listen starter på 12 og
så forsøkt å koble 12 til listen,

359
00:18:00,860 --> 00:18:02,193
vi har allerede sett hva som skjer.

360
00:18:02,193 --> 00:18:04,920
Vi mister listen ved en feiltakelse.

361
00:18:04,920 --> 00:18:06,740
>> OK, så en ting å snakke om.

362
00:18:06,740 --> 00:18:09,750
Hva hvis vi ønsker å bli kvitt
en hel lenket liste på en gang?

363
00:18:09,750 --> 00:18:11,750
Igjen, vi mallocing
all denne plassen, og så vi

364
00:18:11,750 --> 00:18:13,351
trenger å frigjøre det når vi er ferdige.

365
00:18:13,351 --> 00:18:15,350
Så nå ønsker vi å slette
hele lenket liste.

366
00:18:15,350 --> 00:18:16,850
Vel, hva vi ønsker å gjøre?

367
00:18:16,850 --> 00:18:20,460
>> Hvis vi har nådd nullpeker, vi
ønsker å stoppe, ellers bare slette

368
00:18:20,460 --> 00:18:23,420
resten av listen og deretter frigjøre meg.

369
00:18:23,420 --> 00:18:28,890
Sletter resten av listen,
og deretter frigjøre gjeldende node.

370
00:18:28,890 --> 00:18:32,850
Hva høres dette ut som,
hva teknikken har vi snakket

371
00:18:32,850 --> 00:18:35,440
om tidligere høres det ut?

372
00:18:35,440 --> 00:18:39,560
Slett alle andre, så
komme tilbake og slette meg.

373
00:18:39,560 --> 00:18:42,380
>> Det er rekursjon, har vi gjort
problemet litt mindre,

374
00:18:42,380 --> 00:18:46,910
vi sier slette alle
annet, så kan du slette meg.

375
00:18:46,910 --> 00:18:50,940
Og lenger ned i veien, som node
vil si, slette alle andre.

376
00:18:50,940 --> 00:18:53,940
Men til slutt vil vi komme til
punkt hvor listen er null,

377
00:18:53,940 --> 00:18:55,310
og det er vår base case.

378
00:18:55,310 --> 00:18:57,010
>> Så la oss ta en titt på denne,
og hvordan dette kan fungere.

379
00:18:57,010 --> 00:18:59,759
Så her er vår liste, er det det samme
lister vi var bare snakker om,

380
00:18:59,759 --> 00:19:00,980
og det er trinnene.

381
00:19:00,980 --> 00:19:04,200
Det er mye tekst her, men
forhåpentligvis visualisering vil hjelpe.

382
00:19:04,200 --> 00:19:08,557
>> Så vi have-- og jeg har også trukket
opp vår stack rammer illustrasjon

383
00:19:08,557 --> 00:19:10,890
fra vår video på anrops stabler,
og forhåpentligvis all denne

384
00:19:10,890 --> 00:19:13,260
sammen vil vise deg hva som skjer.

385
00:19:13,260 --> 00:19:14,510
Så her er vår pseudokode.

386
00:19:14,510 --> 00:19:17,830
Hvis vi nå en null
pekeren, stoppe, ellers

387
00:19:17,830 --> 00:19:21,320
sletter resten av listen,
deretter frigjøre gjeldende node.

388
00:19:21,320 --> 00:19:25,700
Så akkurat nå, list--
pekeren at vi er

389
00:19:25,700 --> 00:19:28,410
bestått i å ødelegge poeng til 12.

390
00:19:28,410 --> 00:19:33,340
12 er ikke en nullpeker, så vi er
kommer til å slette resten av listen.

391
00:19:33,340 --> 00:19:35,450
>> Hva er å slette
Resten av oss som er involvert?

392
00:19:35,450 --> 00:19:37,950
Vel, det betyr å gjøre en
ringe for å ødelegge, sier

393
00:19:37,950 --> 00:19:42,060
15 som er begynnelsen av
Resten av listen vi ønsker å ødelegge.

394
00:19:42,060 --> 00:19:47,480
Og så kallet til å ødelegge
12 er litt på vent.

395
00:19:47,480 --> 00:19:52,690
Det er frosset der, venter på
ringe for å ødelegge 15, for å fullføre jobben sin.

396
00:19:52,690 --> 00:19:56,280
>> Vel, er 15 ikke en nullpeker, og
så det kommer til å si, all right,

397
00:19:56,280 --> 00:19:58,450
vel, slette resten av listen.

398
00:19:58,450 --> 00:20:00,760
Resten av listen starter
på 9, og så får vi bare

399
00:20:00,760 --> 00:20:04,514
vent til du sletter alt som
ting, så komme tilbake og slette meg.

400
00:20:04,514 --> 00:20:06,680
Vel ni kommer til å si, vel,
Jeg er ikke en nullpeker,

401
00:20:06,680 --> 00:20:09,020
så sletter resten listen herfra.

402
00:20:09,020 --> 00:20:11,805
Og så prøve og ødelegge 13.

403
00:20:11,805 --> 00:20:15,550
13 sier: Jeg er ikke nullpeker,
samme, går det the buck.

404
00:20:15,550 --> 00:20:17,930
10 er ikke nullpeker, 10
inneholder en nullpeker,

405
00:20:17,930 --> 00:20:20,200
men 10 er ikke i seg selv en
nullpeker akkurat nå,

406
00:20:20,200 --> 00:20:22,470
og så den passerer the buck også.

407
00:20:22,470 --> 00:20:25,560
>> Og nå liste poeng der, det
virkelig vil peke på some--

408
00:20:25,560 --> 00:20:28,710
hvis jeg hadde mer plass i bildet,
det ville peke på noen tilfeldig plass

409
00:20:28,710 --> 00:20:29,960
at vi ikke vet hva det er.

410
00:20:29,960 --> 00:20:34,680
Det er nullpeker skjønt, listen
er bokstavelig talt nå satt det verdier null.

411
00:20:34,680 --> 00:20:36,820
Det peker rett på innsiden som rød boks.

412
00:20:36,820 --> 00:20:39,960
Vi nådde en nullpeker, så
vi kan stoppe, og vi er ferdige.

413
00:20:39,960 --> 00:20:46,230
>> Og slik at lilla ramme er now-- på
toppen av stack-- som er den aktive rammen,

414
00:20:46,230 --> 00:20:47,017
men det er gjort.

415
00:20:47,017 --> 00:20:48,600
Hvis vi har nådd en nullpeker, stopp.

416
00:20:48,600 --> 00:20:51,290
Vi gjør ikke noe, vi
kan ikke frigjøre en nullpeker,

417
00:20:51,290 --> 00:20:55,070
vi ikke malloc noen
plass, og så er vi ferdige.

418
00:20:55,070 --> 00:20:57,590
Slik at funksjonsramme
er ødelagt, og vi

419
00:20:57,590 --> 00:21:00,930
resume-- vi fortsette der vi forlot
med det nest høyeste ene, som

420
00:21:00,930 --> 00:21:02,807
er denne mørke blå ramme her.

421
00:21:02,807 --> 00:21:04,390
Så vi plukke opp akkurat der vi slapp.

422
00:21:04,390 --> 00:21:06,598
Vi fjernet resten av
liste allerede, så nå er vi

423
00:21:06,598 --> 00:21:08,000
kommer til å frigjøre de nåværende noder.

424
00:21:08,000 --> 00:21:12,920
Så nå kan vi frigjøre denne noden, og nå
Vi har nådd slutten av funksjonen.

425
00:21:12,920 --> 00:21:16,810
Og slik at funksjonsramme er ødelagt,
og vi plukke opp på den lyseblå en.

426
00:21:16,810 --> 00:21:20,650
>> Så det says-- jeg allerede har done--
sletting resten av listen, så

427
00:21:20,650 --> 00:21:23,140
frigjøre nåværende node.

428
00:21:23,140 --> 00:21:26,520
Og nå den gule rammen er
tilbake på toppen av bunken.

429
00:21:26,520 --> 00:21:29,655
Og slik som du ser, er vi nå
ødelegge listen fra høyre til venstre.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Hva ville ha skjedd, skjønt,
hvis vi hadde gjort ting på feil måte?

432
00:21:37,280 --> 00:21:39,410
Akkurat som da vi prøvde
å legge til et element.

433
00:21:39,410 --> 00:21:41,909
Hvis vi messed opp kjeden, hvis
vi ikke koble pekere

434
00:21:41,909 --> 00:21:44,690
i riktig rekkefølge, hvis vi
bare frigjort det første elementet,

435
00:21:44,690 --> 00:21:47,420
hvis vi bare frigjort
leder av listen, nå er vi

436
00:21:47,420 --> 00:21:49,642
har ingen mulighet til å referere til
resten av listen.

437
00:21:49,642 --> 00:21:51,350
Og så ville vi ha
foreldreløs alt,

438
00:21:51,350 --> 00:21:53,880
vi ville ha hatt det som er
kalt en minnelekkasje.

439
00:21:53,880 --> 00:21:56,800
Hvis du husker fra vår video
på dynamisk minne allokering,

440
00:21:56,800 --> 00:21:58,650
det er ikke veldig bra.

441
00:21:58,650 --> 00:22:00,810
>> Så som jeg sa, det
er flere operasjoner

442
00:22:00,810 --> 00:22:04,010
at vi trenger å bruke for å jobbe
med lenket liste effektivt.

443
00:22:04,010 --> 00:22:08,430
Og du har kanskje merket jeg utelatt en,
slette en enkelt element fra en tilkoblet

444
00:22:08,430 --> 00:22:09,064
listen.

445
00:22:09,064 --> 00:22:10,980
Grunnen til at jeg gjorde det
er det er faktisk slags

446
00:22:10,980 --> 00:22:14,360
vanskelig å tenke på hvordan du sletter
et enkelt element fra en enkeltvis

447
00:22:14,360 --> 00:22:15,600
lenket liste.

448
00:22:15,600 --> 00:22:19,950
Vi må være i stand til å hoppe over
noe på listen, som

449
00:22:19,950 --> 00:22:22,975
betyr at vi får til en point-- vi
vil slette denne node--

450
00:22:22,975 --> 00:22:25,350
men for å gjøre det slik vi
ikke mister noe informasjon,

451
00:22:25,350 --> 00:22:30,530
vi trenger å koble dette
node over her, her.

452
00:22:30,530 --> 00:22:33,390
>> Så jeg sannsynligvis gjorde det galt
fra et visuelt perspektiv.

453
00:22:33,390 --> 00:22:36,830
Så vi er i begynnelsen av vår
liste, vi går gjennom,

454
00:22:36,830 --> 00:22:40,510
vi vil slette denne noden.

455
00:22:40,510 --> 00:22:43,440
Hvis vi bare slette den,
vi har brutt kjeden.

456
00:22:43,440 --> 00:22:45,950
Denne noden her
refererer til alt annet,

457
00:22:45,950 --> 00:22:48,260
den inneholder kjeden fra her på ut.

458
00:22:48,260 --> 00:22:51,190
>> Så det vi trenger å gjøre faktisk
etter at vi kommer til dette punktet,

459
00:22:51,190 --> 00:22:56,670
er vi trenger å gå tilbake ett, og
koble denne noden over til denne node,

460
00:22:56,670 --> 00:22:58,590
slik at vi kan deretter slette
den i midten.

461
00:22:58,590 --> 00:23:02,120
Men enkeltvis lenkede lister ikke
gi oss en vei å gå bakover.

462
00:23:02,120 --> 00:23:05,160
Så vi må enten holde
to pekere, og flytte dem

463
00:23:05,160 --> 00:23:09,527
slags off trinn, en bak
andre mens vi går, eller kommer til et punkt

464
00:23:09,527 --> 00:23:11,110
og deretter sende en annen pekeren gjennom.

465
00:23:11,110 --> 00:23:13,150
Og som du kan se, det
kan bli litt rotete.

466
00:23:13,150 --> 00:23:15,360
Heldigvis har vi
en annen måte å løse det,

467
00:23:15,360 --> 00:23:17,810
når vi snakker om dobbelt lenkede lister.

468
00:23:17,810 --> 00:23:20,720
>> Jeg er Doug Lloyd, dette er CS50.

469
00:23:20,720 --> 00:23:22,298