1 00:00:00,000 --> 00:00:02,832 >> [Musik spiller] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG Lloyd: OK, så på dette punkt i løbet, 4 00:00:08,560 --> 00:00:15,300 Vi har dækket en masse af det grundlæggende i C. Vi ved en masse om variabler, arrays, 5 00:00:15,300 --> 00:00:17,610 pegepinde, alt, gode ting. 6 00:00:17,610 --> 00:00:21,610 De er alle slags bygget i at se som de grundlæggende, 7 00:00:21,610 --> 00:00:23,880 men vi kan gøre mere, ikke? 8 00:00:23,880 --> 00:00:27,930 Vi kan kombinere tingene sammen på interessante måder. 9 00:00:27,930 --> 00:00:31,010 >> Og så lad os gøre det, lad os starte at forgrene ud af det C giver os, 10 00:00:31,010 --> 00:00:35,270 og begynde at skabe vores egne data strukturer ved hjælp disse bygning 11 00:00:35,270 --> 00:00:40,590 blokke sammen for at gøre noget virkelig værdifulde, nyttige. 12 00:00:40,590 --> 00:00:43,420 En måde vi kan gøre dette er at tale om samlinger. 13 00:00:43,420 --> 00:00:48,360 Så indtil videre har vi haft en slags data struktur til at repræsentere samlinger 14 00:00:48,360 --> 00:00:51,030 af lide værdier, lignende værdier. 15 00:00:51,030 --> 00:00:52,350 Det ville være et array. 16 00:00:52,350 --> 00:00:57,020 Vi har samlinger af heltal eller samlinger af tegn og så videre. 17 00:00:57,020 --> 00:01:00,890 >> Strukturer er også sortere i en data struktur til indsamling af oplysninger, 18 00:01:00,890 --> 00:01:03,220 men det er ikke til opsamling som værdier. 19 00:01:03,220 --> 00:01:08,090 Det er normalt blander forskellige datatyper sammen inde i en enkelt kasse. 20 00:01:08,090 --> 00:01:10,750 Men det er ikke i sig selv anvendes til at kæde sammen 21 00:01:10,750 --> 00:01:16,920 eller tilslut sammen lignende elementer, ligesom et array. 22 00:01:16,920 --> 00:01:20,960 Arrays er stor for element se op, men tilbagekaldelse 23 00:01:20,960 --> 00:01:24,262 at det er meget vanskeligt at indsætte i et array, 24 00:01:24,262 --> 00:01:26,470 medmindre vi indsætter på allersidst i denne array. 25 00:01:26,470 --> 00:01:29,730 >> Og det bedste eksempel jeg har for det er insertion slags. 26 00:01:29,730 --> 00:01:31,650 Hvis du husker vores video ved indsættelse sortere, 27 00:01:31,650 --> 00:01:34,110 der var en masse udgift involveret i at have 28 00:01:34,110 --> 00:01:37,970 at afhente elementer, og skift dem af vejen til at passe noget 29 00:01:37,970 --> 00:01:41,290 ind i midten af ​​dit array. 30 00:01:41,290 --> 00:01:44,690 Arrays også lider af en anden problem, hvilket er manglende fleksibilitet. 31 00:01:44,690 --> 00:01:47,150 Når vi erklære et array, vi får et skud på det. 32 00:01:47,150 --> 00:01:49,790 Vi får at sige, jeg vil dette mange elementer. 33 00:01:49,790 --> 00:01:51,940 Kan være 100, det måske være 1,000, kan det 34 00:01:51,940 --> 00:01:55,930 være x hvor x er et tal, som brugeren gav os på en prompt eller på kommando 35 00:01:55,930 --> 00:01:56,630 linje. 36 00:01:56,630 --> 00:01:59,905 >> Men vi får kun ét skud på det, vi ikke komme til at så sige åh, faktisk jeg 37 00:01:59,905 --> 00:02:04,360 havde brug for 101, eller jeg havde brug for x plus 20. 38 00:02:04,360 --> 00:02:07,910 For sent, har vi allerede erklæret array, og hvis vi ønsker at få 101 eller x 39 00:02:07,910 --> 00:02:12,050 plus 20, er vi nødt til at erklære en helt anden matrix, 40 00:02:12,050 --> 00:02:15,540 kopiere alle elementer i array overstået, og så vi har nok. 41 00:02:15,540 --> 00:02:19,880 Og hvad hvis vi tager fejl igen, hvad hvis vi rent faktisk har brug 102 eller x plus 40, 42 00:02:19,880 --> 00:02:21,970 vi er nødt til at gøre det igen. 43 00:02:21,970 --> 00:02:26,250 Så de er meget ufleksibel til resizing vores data, 44 00:02:26,250 --> 00:02:29,360 men hvis vi kombinerer sammen nogle af det grundlæggende, at vi har allerede 45 00:02:29,360 --> 00:02:33,230 lært om pegepinde og strukturer, især ved hjælp af dynamisk hukommelse 46 00:02:33,230 --> 00:02:36,180 fordeling med malloc, vi kan sætte disse stykker sammen 47 00:02:36,180 --> 00:02:40,960 at oprette en ny data structure-- en enkeltvis sammenkædet liste vi måske say-- 48 00:02:40,960 --> 00:02:45,400 der giver os mulighed for at vokse og skrumpe en samling værdier 49 00:02:45,400 --> 00:02:48,800 og vi vil ikke have nogen spildplads. 50 00:02:48,800 --> 00:02:53,320 >> Så igen, kalder vi denne idé, dette begreb, en sammenkædet liste. 51 00:02:53,320 --> 00:02:56,320 Især vi i denne video er taler om enkeltvis linket liste, 52 00:02:56,320 --> 00:02:59,185 og derefter en anden video, vi vil tale omkring dobbelt hægtede lister, som 53 00:02:59,185 --> 00:03:01,560 er blot en variation på et tema her. 54 00:03:01,560 --> 00:03:05,200 Men en enkelt bundet liste består af knudepunkter, 55 00:03:05,200 --> 00:03:08,559 noder blot at være en abstrakt term-- det er bare noget, jeg ringer 56 00:03:08,559 --> 00:03:10,350 det er en slags struktur, dybest set, jeg er? 57 00:03:10,350 --> 00:03:16,190 Bare at kalde det en node-- og dette knude har to medlemmer, eller to felter. 58 00:03:16,190 --> 00:03:20,300 Det har data, som regel en heltal, et tegn float, 59 00:03:20,300 --> 00:03:23,790 eller kan være en anden datatype at du har defineret med en type def. 60 00:03:23,790 --> 00:03:29,290 Og den indeholder en pointer til en anden node af samme type. 61 00:03:29,290 --> 00:03:34,710 >> Så vi har to ting indersiden af dette knudepunkt, data og en pointer 62 00:03:34,710 --> 00:03:36,380 til et andet knudepunkt. 63 00:03:36,380 --> 00:03:39,370 Og hvis du begynder at visualisere dette, kan du tænke over det 64 00:03:39,370 --> 00:03:42,280 som en kæde af knudepunkter, er forbundet med hinanden. 65 00:03:42,280 --> 00:03:45,070 Vi har det første knudepunkt, det indeholder data, og en pegepind 66 00:03:45,070 --> 00:03:49,110 til det andet knudepunkt, som indeholder data, og en pegepind til den tredje knudepunkt. 67 00:03:49,110 --> 00:03:52,940 Og så det er derfor, vi kalder det en linkede liste, de er bundet sammen. 68 00:03:52,940 --> 00:03:56,070 >> Hvad betyder dette særlige node struktur se ud? 69 00:03:56,070 --> 00:04:01,120 Tja, hvis du husker fra vores video på definere brugerdefinerede typer, med type def, 70 00:04:01,120 --> 00:04:05,400 Vi kan definere en structure-- og skriv definere en struktur som denne. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, og så er jeg bruge ordet værdi her vilkårligt 72 00:04:11,240 --> 00:04:13,891 at angive, hvilke datatype rigtig. 73 00:04:13,891 --> 00:04:16,890 Du kunne videregive et heltal eller flyde, du kunne have hvad du vil. 74 00:04:16,890 --> 00:04:19,389 Det er ikke begrænset til blot heltal, eller noget lignende. 75 00:04:19,389 --> 00:04:22,790 Så værdi er blot en vilkårlig datatype, og derefter en pointer 76 00:04:22,790 --> 00:04:26,310 til en anden node af samme type. 77 00:04:26,310 --> 00:04:29,690 >> Nu, der er en lille fangst her med at definere en struktur 78 00:04:29,690 --> 00:04:33,030 når det er en selv referentiel struktur. 79 00:04:33,030 --> 00:04:35,340 Jeg er nødt til at have en midlertidig navn til min struktur. 80 00:04:35,340 --> 00:04:37,640 I slutningen af ​​den dag, jeg klart vil kalde det 81 00:04:37,640 --> 00:04:43,030 SLL node, det er i sidste ende den nye nævne en del af min type definition 82 00:04:43,030 --> 00:04:47,450 men jeg kan ikke bruge SLL node i midten af ​​dette. 83 00:04:47,450 --> 00:04:51,430 Årsagen er, har jeg ikke skabte en type kaldet SLL node 84 00:04:51,430 --> 00:04:55,200 indtil jeg ramt dette sidste punkt her. 85 00:04:55,200 --> 00:04:59,720 Indtil dette punkt, jeg er nødt til at have en anden måde at henvise til denne datatype. 86 00:04:59,720 --> 00:05:02,440 >> Og det er en selvstændig referentiel datatype. 87 00:05:02,440 --> 00:05:06,314 Det; s en datatype af et struktur, der indeholder en database, 88 00:05:06,314 --> 00:05:08,480 og en pointer til en anden struktur af samme type. 89 00:05:08,480 --> 00:05:11,750 Så jeg har brug for at være i stand til at henvise til denne datatype i det mindste midlertidigt, 90 00:05:11,750 --> 00:05:14,910 så giver det en midlertidig navn struct sllist 91 00:05:14,910 --> 00:05:18,540 tillader mig at så siger jeg vil have en pointer til en anden struct sllist, 92 00:05:18,540 --> 00:05:24,690 en struct sllist stjerne, og derefter efter at jeg har gennemført definitionen, 93 00:05:24,690 --> 00:05:27,220 Jeg kan nu kalde denne type en SLL node. 94 00:05:27,220 --> 00:05:30,520 >> Så det er derfor du se, at der er en midlertidig navn her, 95 00:05:30,520 --> 00:05:31,879 men en permanent navn her. 96 00:05:31,879 --> 00:05:33,920 Nogle gange vil du måske se definitioner af strukturen, 97 00:05:33,920 --> 00:05:36,570 for eksempel, som ikke er selv referentiel, at 98 00:05:36,570 --> 00:05:39,390 ikke har en specifier navn her. 99 00:05:39,390 --> 00:05:43,040 Det ville bare sige typedef struct, åbne krøllede klammeparentes og derefter definere det. 100 00:05:43,040 --> 00:05:45,620 Men hvis du er struct er self referentiel, som dette er, 101 00:05:45,620 --> 00:05:49,010 skal du angive en midlertidig typen navn. 102 00:05:49,010 --> 00:05:51,310 Men i sidste ende, nu at vi har gjort dette, 103 00:05:51,310 --> 00:05:53,620 Vi kan bare henvise til disse knudepunkter, disse enheder, 104 00:05:53,620 --> 00:05:57,900 som SLL noder til formål, af resten af ​​denne video. 105 00:05:57,900 --> 00:06:00,900 >> Okay, så vi ved, hvordan man oprette en sammenkædet liste node. 106 00:06:00,900 --> 00:06:03,240 Vi ved, hvordan man definerer en sammenkædet liste node. 107 00:06:03,240 --> 00:06:06,670 Nu, hvis vi kommer til at starte bruge dem til at indsamle oplysninger, 108 00:06:06,670 --> 00:06:10,360 der er et par af operationer, vi nødt til at forstå og arbejde med. 109 00:06:10,360 --> 00:06:12,860 Vi har brug for at vide, hvordan man skaber en sammenkædet liste ud af den blå luft. 110 00:06:12,860 --> 00:06:14,901 Hvis der ikke er nogen liste allerede, Vi ønsker at starte en. 111 00:06:14,901 --> 00:06:16,960 Så vi skal være i stand at oprette en sammenkædet liste, 112 00:06:16,960 --> 00:06:19,130 vi nødt til sandsynligvis søge via linket listen 113 00:06:19,130 --> 00:06:21,830 for at finde et element, vi leder efter. 114 00:06:21,830 --> 00:06:24,430 Vi skal være i stand til at indsætte nye ting ind i listen, 115 00:06:24,430 --> 00:06:25,930 vi ønsker vores liste til at kunne vokse. 116 00:06:25,930 --> 00:06:28,638 Og på samme måde, vi ønsker at kunne at slette ting fra vores liste, 117 00:06:28,638 --> 00:06:30,250 Vi ønsker, at vores liste at være i stand til at skrumpe. 118 00:06:30,250 --> 00:06:32,160 Og ved slutningen af ​​vores programmer, især 119 00:06:32,160 --> 00:06:34,550 hvis du husker, at vi er dynamisk allokering hukommelse 120 00:06:34,550 --> 00:06:38,337 at opbygge disse lister typisk vi ønsker at befri alle, at hukommelsen 121 00:06:38,337 --> 00:06:39,670 når vi er færdige arbejder med det. 122 00:06:39,670 --> 00:06:44,627 Og så skal vi være i stand til at slette et Hele linket liste på én mislykkes razzia. 123 00:06:44,627 --> 00:06:46,460 Så lad os gå igennem nogle af disse operationer 124 00:06:46,460 --> 00:06:51,192 og hvordan vi kan visualisere dem, taler i pseudokode kode specifikt. 125 00:06:51,192 --> 00:06:53,150 Så vi ønsker at skabe en linkede liste, så måske vi 126 00:06:53,150 --> 00:06:56,480 ønsker at definere en funktion med denne prototype. 127 00:06:56,480 --> 00:07:01,690 SLL node stjerne, oprette, og jeg passerer i et argument, nogle vilkårlige data 128 00:07:01,690 --> 00:07:05,530 skriv igen, af en eller anden vilkårlig datatype. 129 00:07:05,530 --> 00:07:10,482 Men jeg returning-- denne funktion skal tilbage til mig en pointer til en enkeltvis 130 00:07:10,482 --> 00:07:11,190 sammenkædet liste node. 131 00:07:11,190 --> 00:07:14,050 Igen, vi forsøger at skabe en sammenkædet liste ud af den blå luft, 132 00:07:14,050 --> 00:07:17,900 så jeg har brug for en pointer til denne liste, når jeg er færdig. 133 00:07:17,900 --> 00:07:19,420 >> Så hvad er de skridt, der er involveret her? 134 00:07:19,420 --> 00:07:20,960 Nå, første ting jeg kommer til at gøre, er dynamisk 135 00:07:20,960 --> 00:07:22,550 allokere plads til en ny node. 136 00:07:22,550 --> 00:07:26,689 Igen, vi skaber det ud af den blå luft, så vi er nødt til at malloc plads til det. 137 00:07:26,689 --> 00:07:28,480 Og naturligvis straks efter vi malloc, 138 00:07:28,480 --> 00:07:31,692 vi altid tjekke for at sikre, at vores pointer-- vi ikke fik tilbage null. 139 00:07:31,692 --> 00:07:33,650 For hvis vi forsøger og ærbødighed en null-pointer, 140 00:07:33,650 --> 00:07:36,190 vi kommer til at lide en segmenteringsfejl og vi vil ikke have det. 141 00:07:36,190 --> 00:07:39,510 >> Så vi ønsker at udfylde feltet, vi ønsker at initialisere værdien feltet 142 00:07:39,510 --> 00:07:41,690 og initialisere næste felt. 143 00:07:41,690 --> 00:07:45,450 Og så ønsker vi at-- sidst som funktion prototype indicates-- vi ønsker 144 00:07:45,450 --> 00:07:49,940 at returnere en pegepind til en SLL node. 145 00:07:49,940 --> 00:07:51,710 Så hvad gør denne ligne visuelt? 146 00:07:51,710 --> 00:07:55,230 Nå, først vi vil dynamisk allokere plads til en ny SLL node, 147 00:07:55,230 --> 00:07:58,320 så vi malloc-- der er en visuel repræsentation 148 00:07:58,320 --> 00:08:00,020 knudens vi lige har oprettet. 149 00:08:00,020 --> 00:08:02,757 Og vi skal du kontrollere det er ikke null-- i denne sag, 150 00:08:02,757 --> 00:08:04,840 billedet vil ikke vist op, hvis det var null, 151 00:08:04,840 --> 00:08:07,298 vi ville have løbe tør for hukommelse, så vi er godt at gå der. 152 00:08:07,298 --> 00:08:10,200 Så nu er vi til trin C, initialisere knudepunkter værdien felt. 153 00:08:10,200 --> 00:08:12,280 Nå, der er baseret på denne funktion kalder Jeg bruger her, 154 00:08:12,280 --> 00:08:16,700 ser ud som jeg ønsker at passere i 6, Så jeg vil 6 i værdifeltet. 155 00:08:16,700 --> 00:08:18,865 Nu initialisere det næste felt. 156 00:08:18,865 --> 00:08:21,640 Nå, hvad skal jeg gøre der, der er intet næste, højre, 157 00:08:21,640 --> 00:08:23,600 dette er det eneste i listen. 158 00:08:23,600 --> 00:08:27,206 Så hvad er den næste ting på listen? 159 00:08:27,206 --> 00:08:29,660 >> Det bør ikke pege på noget, højre. 160 00:08:29,660 --> 00:08:33,600 Der er ikke noget andet der, så hvad er begrebet vi kender, der er nothing-- 161 00:08:33,600 --> 00:08:35,638 pegepinde til ingenting? 162 00:08:35,638 --> 00:08:37,929 Det bør være måske vi ønsker at sætte en null-pointer der, 163 00:08:37,929 --> 00:08:40,178 og jeg vil repræsentere null pointer som bare en rød boks, 164 00:08:40,178 --> 00:08:41,559 Vi kan ikke gå længere. 165 00:08:41,559 --> 00:08:44,430 Som vi vil se lidt senere, vi vil have i sidste ende kæder 166 00:08:44,430 --> 00:08:46,330 af pile forbinder disse knudepunkter sammen, 167 00:08:46,330 --> 00:08:48,480 men når du rammer røde felt, det er null, 168 00:08:48,480 --> 00:08:51,150 Vi kan ikke gå videre, det er slutningen af ​​listen. 169 00:08:51,150 --> 00:08:53,960 >> Og endelig, vi ønsker blot at returnere en pegepind til denne knude. 170 00:08:53,960 --> 00:08:56,160 Så vi vil kalde det nye, og vil vende tilbage ny 171 00:08:56,160 --> 00:08:59,370 så den kan anvendes i uanset hvilken funktion skabte det. 172 00:08:59,370 --> 00:09:03,100 Så der går vi, vi har oprettet en enkeltvis sammenkædet liste node ud af den blå luft, 173 00:09:03,100 --> 00:09:05,920 og nu har vi en liste, vi kan arbejde med. 174 00:09:05,920 --> 00:09:08,260 >> Lad os nu sige, at vi allerede har en stor kæde, 175 00:09:08,260 --> 00:09:09,800 og vi ønsker at finde noget i det. 176 00:09:09,800 --> 00:09:12,716 Og vi vil have en funktion, der kommer at returnere sand eller falsk, afhængigt 177 00:09:12,716 --> 00:09:15,840 om, hvorvidt en værdi findes i denne liste. 178 00:09:15,840 --> 00:09:18,160 En funktion prototype eller erklæring for denne funktion, 179 00:09:18,160 --> 00:09:23,320 kan se ud som denne-- bool finde, og så vi ønsker at passere i to argumenter. 180 00:09:23,320 --> 00:09:26,996 >> Det første, er en pointer til første element i den linkede liste. 181 00:09:26,996 --> 00:09:29,620 Det er faktisk noget, du vil altid ønsker at holde styr på, 182 00:09:29,620 --> 00:09:33,110 og faktisk kunne være noget, du endda sat i en global variabel. 183 00:09:33,110 --> 00:09:35,360 Når du opretter en liste, du altid, altid 184 00:09:35,360 --> 00:09:38,990 ønsker at holde styr på de meget første element på listen. 185 00:09:38,990 --> 00:09:43,690 På den måde kan du henvise til alle de andre elementer af lige efter kæden, 186 00:09:43,690 --> 00:09:47,300 uden at skulle holde pointers intakt til hver enkelt element. 187 00:09:47,300 --> 00:09:50,920 Du behøver kun at holde styr på den første en, hvis de er alle lænket sammen. 188 00:09:50,920 --> 00:09:52,460 >> Og så den anden ting vi passerer igen 189 00:09:52,460 --> 00:09:54,376 er vilkårligt some-- uanset hvilken datatype er vi 190 00:09:54,376 --> 00:09:59,640 søger der er inde i forhåbentlig et af knudepunkterne på listen. 191 00:09:59,640 --> 00:10:00,980 Så hvad er de skridt? 192 00:10:00,980 --> 00:10:04,250 Nå, den første ting, vi gør, er skaber vi en tværgående pointer 193 00:10:04,250 --> 00:10:06,015 peger på listerne hoved. 194 00:10:06,015 --> 00:10:08,890 Tja, hvorfor gør vi det, vi allerede har en pointer på lister hovedet, 195 00:10:08,890 --> 00:10:10,974 hvorfor vi ikke bare flytte, at man rundt? 196 00:10:10,974 --> 00:10:13,140 Tja, som jeg lige har sagt, det er virkelig vigtigt for os 197 00:10:13,140 --> 00:10:17,580 for altid at holde styr på allerførste element i listen. 198 00:10:17,580 --> 00:10:21,270 Og så er det faktisk bedre at oprette en kopi af denne, 199 00:10:21,270 --> 00:10:25,350 og bruge den til at bevæge sig rundt, så vi aldrig uheld bevæge sig væk, eller vi altid 200 00:10:25,350 --> 00:10:30,430 har en pointer på et tidspunkt, der er lige på det første element på listen. 201 00:10:30,430 --> 00:10:33,290 Så det er bedre at skabe en anden en, som vi bruger til at flytte. 202 00:10:33,290 --> 00:10:35,877 >> Så vi bare sammenligne, om feltet på denne node værdi 203 00:10:35,877 --> 00:10:38,960 er det, vi leder efter, og hvis det er ikke, vi bare gå videre til næste node. 204 00:10:38,960 --> 00:10:41,040 Og vi holde gør, at i og over og over, 205 00:10:41,040 --> 00:10:44,811 indtil vi enten finder elementet, eller vi ramt 206 00:10:44,811 --> 00:10:47,310 null-- vi har nået slutningen af listen, og det er ikke der. 207 00:10:47,310 --> 00:10:50,540 Dette skulle forhåbentlig ringer en klokke til dig som bare lineær søgning, 208 00:10:50,540 --> 00:10:54,430 vi bare replikere det i en enkelt bundet listestruktur 209 00:10:54,430 --> 00:10:56,280 stedet for at bruge et array til at gøre det. 210 00:10:56,280 --> 00:10:58,210 >> Så her er et eksempel på en enkelt bundet listen. 211 00:10:58,210 --> 00:11:00,043 Denne ene består af fem knuder, og vi har 212 00:11:00,043 --> 00:11:04,330 en pointer til lederen af liste, som kaldes listen. 213 00:11:04,330 --> 00:11:07,385 Den første ting, vi ønsker at gøre, er igen, skabe den traversal pointer. 214 00:11:07,385 --> 00:11:09,760 Så vi har nu to pejlemærker der peger på det samme. 215 00:11:09,760 --> 00:11:15,025 >> Nu bemærke her også, jeg ikke nødt til at allokere nogen plads til trav. 216 00:11:15,025 --> 00:11:18,970 Jeg sagde ikke trav lig malloc noget, der allerede findes, at node, 217 00:11:18,970 --> 00:11:21,160 at rummet i hukommelsen findes allerede. 218 00:11:21,160 --> 00:11:24,290 Så alt jeg faktisk gør, er skabe en anden pointer til det. 219 00:11:24,290 --> 00:11:28,210 Jeg er ikke mallocing en ekstra plads, bare har nu to pejlemærker 220 00:11:28,210 --> 00:11:31,370 peger på det samme. 221 00:11:31,370 --> 00:11:33,710 >> Så er 2, hvad jeg leder efter? 222 00:11:33,710 --> 00:11:37,220 Nå, nej, så i stedet er jeg kommer til at flytte til den næste. 223 00:11:37,220 --> 00:11:41,740 Så dybest set vil jeg sige, trav lig trav næste. 224 00:11:41,740 --> 00:11:43,630 Er 3 hvad jeg leder efter, nej. 225 00:11:43,630 --> 00:11:45,780 Så jeg fortsætter med at gå igennem, indtil til sidst 226 00:11:45,780 --> 00:11:48,690 komme til 6, som er hvad jeg søger for baseret på funktionen opkald 227 00:11:48,690 --> 00:11:51,600 Jeg har i toppen der, og så jeg er færdig. 228 00:11:51,600 --> 00:11:54,150 >> Nu, hvad hvis elementet er jeg leder efter, er ikke på listen, 229 00:11:54,150 --> 00:11:55,510 er det stadig kommer til at arbejde? 230 00:11:55,510 --> 00:11:57,120 Nå, bemærke, at listen her er subtilt anderledes, 231 00:11:57,120 --> 00:11:59,410 og det er en anden ting, der er vigtigt med hægtede lister, 232 00:11:59,410 --> 00:12:01,780 du behøver ikke at bevare dem i nogen bestemt rækkefølge. 233 00:12:01,780 --> 00:12:05,390 Du kan hvis du vil, men du måske allerede har bemærket 234 00:12:05,390 --> 00:12:09,310 at vi ikke holde styr på hvad nummer element, vi er på. 235 00:12:09,310 --> 00:12:13,150 >> Og det er slags en handel, som vi har med linket liste vers arrays, 236 00:12:13,150 --> 00:12:15,300 er det vi ikke har random access længere. 237 00:12:15,300 --> 00:12:18,150 Vi kan ikke bare sige, jeg ønsker at gå til 0. element, 238 00:12:18,150 --> 00:12:21,410 eller 6. element i mit array, som jeg kan gøre i et array. 239 00:12:21,410 --> 00:12:25,080 Jeg kan ikke sige jeg ønsker at gå til 0. element, eller 6. element, 240 00:12:25,080 --> 00:12:30,360 eller 25 element min sammenkædet liste, der er ingen indeks forbundet med dem. 241 00:12:30,360 --> 00:12:33,660 Og så det er ligegyldigt virkelig hvis vi bevarer vores liste i orden. 242 00:12:33,660 --> 00:12:36,080 Hvis du ønsker at du sikkert kan, men der er 243 00:12:36,080 --> 00:12:38,567 ingen grund til de skal bevares i vilkårlig rækkefølge. 244 00:12:38,567 --> 00:12:40,400 Så igen, lad os prøve og finde 6 på denne liste. 245 00:12:40,400 --> 00:12:43,200 Nå, vi starter på begynder, vi ikke finde 6, 246 00:12:43,200 --> 00:12:47,690 og derefter fortsætte vi ikke at finde 6, indtil vi til sidst kommer til her. 247 00:12:47,690 --> 00:12:52,790 Så lige nu Trav peger på noden indeholdende 8, og seks er ikke derinde. 248 00:12:52,790 --> 00:12:55,250 >> Så næste skridt ville være at gå til det næste pointer, 249 00:12:55,250 --> 00:12:57,440 så siger trav lig trav næste. 250 00:12:57,440 --> 00:13:00,750 Nå, trav næste, angives med det røde felt der, er null. 251 00:13:00,750 --> 00:13:03,020 Så der er ingen andre steder at gå, og så på dette punkt 252 00:13:03,020 --> 00:13:06,120 Vi kan konkludere, at vi har nået slutningen af ​​linkede liste, 253 00:13:06,120 --> 00:13:07,190 og 6 er ikke derinde. 254 00:13:07,190 --> 00:13:10,980 Og det ville blive returneret falsk i dette tilfælde. 255 00:13:10,980 --> 00:13:14,540 >> OK, hvordan kan vi indsætte en ny knude i den linkede liste? 256 00:13:14,540 --> 00:13:17,310 Så vi har været i stand til at skabe en sammenkædet liste ud af ingenting, 257 00:13:17,310 --> 00:13:19,370 men vi sikkert gerne opbygge en kæde og ikke 258 00:13:19,370 --> 00:13:22,620 skabe en masse forskellige lister. 259 00:13:22,620 --> 00:13:25,700 Vi ønsker at have en liste, har en masse knuder i det, 260 00:13:25,700 --> 00:13:28,040 ikke en flok lister med en enkelt node. 261 00:13:28,040 --> 00:13:31,260 Så vi kan ikke bare fortsætte med at bruge Opret funktion vi defineret tidligere, nu er vi 262 00:13:31,260 --> 00:13:33,860 ønsker at indsætte i en liste, der allerede eksisterer. 263 00:13:33,860 --> 00:13:36,499 >> Så dette tilfælde vil vi at passere i to argumenter, 264 00:13:36,499 --> 00:13:39,290 markøren til lederen af ​​det linkede liste, som vi ønsker at føje til. 265 00:13:39,290 --> 00:13:40,910 Igen, det er derfor det er så vigtigt, at vi altid 266 00:13:40,910 --> 00:13:43,400 holde styr på det, fordi det er den eneste måde, vi virkelig 267 00:13:43,400 --> 00:13:46,690 nødt til at henvise til hele listen er blot ved en pointer til det første element. 268 00:13:46,690 --> 00:13:49,360 Så vi ønsker at passere i en Markøren til denne første element, 269 00:13:49,360 --> 00:13:52,226 og uanset værdi, vi ønsker at tilføje til listen. 270 00:13:52,226 --> 00:13:54,600 Og til sidst denne funktion kommer til at vende tilbage en pegepind 271 00:13:54,600 --> 00:13:57,980 til den nye leder af en linket liste. 272 00:13:57,980 --> 00:13:59,700 >> Hvad er de skridt, der er involveret her? 273 00:13:59,700 --> 00:14:02,249 Nå, ligesom med skabe, vi er nødt til dynamisk allokere 274 00:14:02,249 --> 00:14:05,540 plads til en ny node, og tjek at gøre sikker på at vi ikke løber tør for hukommelse, igen, 275 00:14:05,540 --> 00:14:07,150 fordi vi bruger malloc. 276 00:14:07,150 --> 00:14:09,080 Så vi ønsker at befolke og indsæt node, 277 00:14:09,080 --> 00:14:12,730 så sætter antallet, uanset val er, ind i knuden. 278 00:14:12,730 --> 00:14:17,310 Vi ønsker at indsætte noden på begyndelsen af ​​linkede liste. 279 00:14:17,310 --> 00:14:19,619 >> Der er en grund til, at jeg ønsker at gøre dette, og det 280 00:14:19,619 --> 00:14:21,910 kunne være værd at tage et andet at holde pause i videoen her, 281 00:14:21,910 --> 00:14:25,860 og tænke over, hvorfor jeg ønsker at indsætte ved begyndelsen af ​​en sammenkædet 282 00:14:25,860 --> 00:14:26,589 listen. 283 00:14:26,589 --> 00:14:28,630 Igen, jeg nævnte tidligere at det egentlig ikke 284 00:14:28,630 --> 00:14:33,020 noget, hvis vi bevarer det på nogen orden, så måske det er et fingerpeg. 285 00:14:33,020 --> 00:14:36,040 Og du så, hvad der ville ske, hvis vi ønskede at-- eller fra blot et sekund 286 00:14:36,040 --> 00:14:37,360 siden, da vi skulle gennem søgning, du 287 00:14:37,360 --> 00:14:39,235 kunne se, hvad der kunne ske, hvis vi forsøgte 288 00:14:39,235 --> 00:14:41,330 at indsætte i slutningen af ​​listen. 289 00:14:41,330 --> 00:14:44,750 Fordi vi ikke har en pointer til slutningen af ​​listen. 290 00:14:44,750 --> 00:14:47,490 >> Så grunden til, at jeg ønsker at indsætte i begyndelsen, 291 00:14:47,490 --> 00:14:49,380 er fordi jeg kan gøre det samme. 292 00:14:49,380 --> 00:14:52,730 Jeg har en pointer i starten, og vi vil se det i en visuel i en anden. 293 00:14:52,730 --> 00:14:55,605 Men hvis jeg ønsker at indsætte i slutningen, Jeg er nødt til at starte ved begyndelsen, 294 00:14:55,605 --> 00:14:58,760 krydse hele vejen til ende, og derefter tack det på. 295 00:14:58,760 --> 00:15:01,420 Så det ville betyde, at indsættelse i slutningen af ​​listen 296 00:15:01,420 --> 00:15:04,140 ville blive en o n operation, som går tilbage 297 00:15:04,140 --> 00:15:06,720 til vores diskussion af beregningsmæssige kompleksitet. 298 00:15:06,720 --> 00:15:10,140 Det ville blive en o n operation, hvor som listen blev større, og større, 299 00:15:10,140 --> 00:15:13,310 og større, vil det blive mere og vanskeligere at hæfte noget 300 00:15:13,310 --> 00:15:14,661 ankomsttidspunktet ved afslutningen. 301 00:15:14,661 --> 00:15:17,410 Men det er altid virkelig nemt at tack noget på i starten, 302 00:15:17,410 --> 00:15:19,060 du er altid i begyndelsen. 303 00:15:19,060 --> 00:15:21,620 >> Og vi vil se en visuel af denne igen. 304 00:15:21,620 --> 00:15:24,100 Og så når vi er færdig, når Vi har indsat den nye node, 305 00:15:24,100 --> 00:15:26,880 vi ønsker at returnere vores pointer til den nye leder af en linket liste, som 306 00:15:26,880 --> 00:15:29,213 da vi indsætter på begynder, vil faktisk være 307 00:15:29,213 --> 00:15:31,060 en pointer til det knudepunkt, vi lige har oprettet. 308 00:15:31,060 --> 00:15:33,280 Lad os forestille sig dette, fordi jeg tror, ​​det vil hjælpe. 309 00:15:33,280 --> 00:15:36,661 >> Så her er vores liste, den består af fire elementer, et knudepunkt indeholdende 15, 310 00:15:36,661 --> 00:15:38,410 hvilket tyder på en node indeholdende 9, som 311 00:15:38,410 --> 00:15:41,370 peger på en node, der indeholder 13, hvilket tyder på en node, der indeholder 312 00:15:41,370 --> 00:15:44,840 10, som har nul pointer som sin næste pointer 313 00:15:44,840 --> 00:15:47,010 så det er i slutningen af ​​listen. 314 00:15:47,010 --> 00:15:50,200 Så vi ønsker at indsætte en ny knude med værdien 12 315 00:15:50,200 --> 00:15:52,720 i begyndelsen af ​​denne liste, hvad gør vi? 316 00:15:52,720 --> 00:15:58,770 Nå, først vi malloc plads til knude, og så sætter vi 12 derinde. 317 00:15:58,770 --> 00:16:02,211 >> Så nu har vi nået en beslutning punkt, højre? 318 00:16:02,211 --> 00:16:03,960 Vi har et par pejlemærker, som vi kunne 319 00:16:03,960 --> 00:16:06,770 flytte, som man bør vi flytter først? 320 00:16:06,770 --> 00:16:09,250 Skal vi lave 12 point til den nye leder af list-- 321 00:16:09,250 --> 00:16:13,020 eller undskyld, bør vi gøre 12 pege på den gamle leder af listen? 322 00:16:13,020 --> 00:16:15,319 Eller skal vi sige, at den Listen begynder nu på 12. 323 00:16:15,319 --> 00:16:17,110 Der er en forskel der, og vi vil se 324 00:16:17,110 --> 00:16:19,870 hvad der sker med både i en anden. 325 00:16:19,870 --> 00:16:23,350 >> Men dette fører til en store emne for sidebar, 326 00:16:23,350 --> 00:16:26,280 som er, at en af ​​de vanskeligste ting med hægtede lister 327 00:16:26,280 --> 00:16:30,980 er at arrangere pointers i den rigtige rækkefølge. 328 00:16:30,980 --> 00:16:34,520 Hvis du flytter tingene i orden, du kan ende op ved et uheld 329 00:16:34,520 --> 00:16:36,050 forældreløse resten af ​​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å lad os gå med tanken of-- godt, vi har lige har oprettet 12. 332 00:16:40,540 --> 00:16:43,180 Vi ved 12 vil være den nye leder af listen, 333 00:16:43,180 --> 00:16:47,660 og så hvorfor ikke vi bare flytte listen pointer til at pege der. 334 00:16:47,660 --> 00:16:49,070 >> OK, så det er godt. 335 00:16:49,070 --> 00:16:51,560 Så nu hvor gør 12 næste punkt? 336 00:16:51,560 --> 00:16:54,580 Jeg mener, visuelt kan vi se at det vil pege på 15, 337 00:16:54,580 --> 00:16:57,250 som mennesker er det virkelig klart for os. 338 00:16:57,250 --> 00:17:00,300 Hvordan computeren kender? 339 00:17:00,300 --> 00:17:02,720 Vi har ikke noget peger på 15 længere, vel? 340 00:17:02,720 --> 00:17:05,869 >> Vi har mistet enhver evne til at henvise til 15. 341 00:17:05,869 --> 00:17:11,460 Vi kan ikke sige ny pil ved siden ligemænd noget, der er ikke noget der. 342 00:17:11,460 --> 00:17:13,510 Faktisk har vi forældreløse resten af ​​listen 343 00:17:13,510 --> 00:17:16,465 ved at gøre det, vi har uheld brudt kæden. 344 00:17:16,465 --> 00:17:18,089 Og vi bestemt ikke ønsker at gøre det. 345 00:17:18,089 --> 00:17:20,000 >> Så lad os gå tilbage og prøve dette igen. 346 00:17:20,000 --> 00:17:24,060 Måske det rigtige at gøre er at sætte 12 næste pointer 347 00:17:24,060 --> 00:17:28,290 til den gamle leder af listen først, så kan vi flytte listen igen. 348 00:17:28,290 --> 00:17:30,420 Og i virkeligheden, dvs. rigtige rækkefølge at vi 349 00:17:30,420 --> 00:17:32,836 nødt til at følge, når vi er arbejder med enkelt bundet listen. 350 00:17:32,836 --> 00:17:36,460 Vi ønsker altid at tilslutte nyt element i listen, 351 00:17:36,460 --> 00:17:41,010 før vi tager den slags vigtigt skridt for at ændre 352 00:17:41,010 --> 00:17:43,360 hvor lederen af ​​den linkede liste er. 353 00:17:43,360 --> 00:17:46,740 Igen, det er sådan en grundlæggende ting, Vi ønsker ikke at miste overblikket over det. 354 00:17:46,740 --> 00:17:49,310 >> Så vi ønsker at sikre, at alt er lænket sammen, 355 00:17:49,310 --> 00:17:52,040 før vi går, at markøren. 356 00:17:52,040 --> 00:17:55,300 Og så det ville være den rigtige rækkefølge, som er at forbinde 12 til listen, 357 00:17:55,300 --> 00:17:57,630 så sige, at listen starter en 12. 358 00:17:57,630 --> 00:18:00,860 Hvis vi sagde listen starter ved 12 og derefter forsøgte at forbinde 12 til listen, 359 00:18:00,860 --> 00:18:02,193 Vi har allerede set, hvad der sker. 360 00:18:02,193 --> 00:18:04,920 Vi mister listen ved en fejltagelse. 361 00:18:04,920 --> 00:18:06,740 >> OK, så en ting mere at tale om. 362 00:18:06,740 --> 00:18:09,750 Hvad nu, hvis vi ønsker at slippe af med en hel linkede liste på én gang? 363 00:18:09,750 --> 00:18:11,750 Igen, vi mallocing alt dette rum, og så vi 364 00:18:11,750 --> 00:18:13,351 brug for at frigøre det, når vi er færdig. 365 00:18:13,351 --> 00:18:15,350 Så nu er vi ønsker at slette hele linkede liste. 366 00:18:15,350 --> 00:18:16,850 Nå, hvad ønsker vi at gøre? 367 00:18:16,850 --> 00:18:20,460 >> Hvis vi har nået null-pointer, vi ønsker at stoppe, ellers bare slette 368 00:18:20,460 --> 00:18:23,420 resten af ​​listen og derefter slippe mig. 369 00:18:23,420 --> 00:18:28,890 Slet resten af ​​listen, og derefter slippe den aktuelle node. 370 00:18:28,890 --> 00:18:32,850 Hvad lyder det som, hvad teknik har vi talte 371 00:18:32,850 --> 00:18:35,440 om tidligere lyder det ud? 372 00:18:35,440 --> 00:18:39,560 Slet alle andre, så komme tilbage og slette mig. 373 00:18:39,560 --> 00:18:42,380 >> Det er rekursion, har vi gjort Problem lidt mindre, 374 00:18:42,380 --> 00:18:46,910 vi siger slet alle andet, så kan du slette mig. 375 00:18:46,910 --> 00:18:50,940 Og længere nede ad vejen, at node vil sige, slette alle andre. 376 00:18:50,940 --> 00:18:53,940 Men til sidst vil vi komme til punkt, hvor listen er nul, 377 00:18:53,940 --> 00:18:55,310 og det er vores base sagen. 378 00:18:55,310 --> 00:18:57,010 >> Så lad os tage et kig på denne, og hvordan dette kunne arbejde. 379 00:18:57,010 --> 00:18:59,759 Så her er vores liste, det er det samme liste blev vi bare taler om, 380 00:18:59,759 --> 00:19:00,980 og der er de skridt. 381 00:19:00,980 --> 00:19:04,200 Der er en masse tekst her, men forhåbentlig visualisering vil hjælpe. 382 00:19:04,200 --> 00:19:08,557 >> Så vi have-- og jeg også trukket vores stakrammer illustration 383 00:19:08,557 --> 00:19:10,890 fra vores video på opkald stakke, og forhåbentlig alt dette 384 00:19:10,890 --> 00:19:13,260 sammen vil vise dig, hvad der foregår. 385 00:19:13,260 --> 00:19:14,510 Så her er vores pseudokode kode. 386 00:19:14,510 --> 00:19:17,830 Hvis vi når en null pointer, stop, ellers 387 00:19:17,830 --> 00:19:21,320 slet resten af ​​listen, derefter slippe den aktuelle node. 388 00:19:21,320 --> 00:19:25,700 Så lige nu, list-- markøren, at vi er 389 00:19:25,700 --> 00:19:28,410 passerer at ødelægge point til 12. 390 00:19:28,410 --> 00:19:33,340 12 er ikke en null-pointer, så vi er ved at slette resten af ​​listen. 391 00:19:33,340 --> 00:19:35,450 >> Hvad er at slette resten af ​​os involveret? 392 00:19:35,450 --> 00:19:37,950 Tja, det betyder at gøre en ringe til at ødelægge, siger 393 00:19:37,950 --> 00:19:42,060 at 15 er begyndelsen af resten af ​​listen, vi ønsker at ødelægge. 394 00:19:42,060 --> 00:19:47,480 Og så opfordringen til at ødelægge 12 er lidt i venteposition. 395 00:19:47,480 --> 00:19:52,690 Det er indefrosset der, venter på ringe til at ødelægge 15, for at afslutte sit arbejde. 396 00:19:52,690 --> 00:19:56,280 >> Tja, 15 er ikke en null-pointer, og så det kommer til at sige, okay, 397 00:19:56,280 --> 00:19:58,450 godt, slet resten af ​​listen. 398 00:19:58,450 --> 00:20:00,760 Resten af ​​listen starter på 9, og så vi vil bare 399 00:20:00,760 --> 00:20:04,514 vente, indtil du sletter alt, ting, så kom tilbage og slette mig. 400 00:20:04,514 --> 00:20:06,680 Nå 9 kommer til at sige, ja, Jeg er ikke en null-pointer, 401 00:20:06,680 --> 00:20:09,020 så slette resten listen herfra. 402 00:20:09,020 --> 00:20:11,805 Og så prøv og ødelægge 13. 403 00:20:11,805 --> 00:20:15,550 13 siger, jeg er ikke null-pointer, samme ting, den passerer sorteper. 404 00:20:15,550 --> 00:20:17,930 10 er ikke null-pointer, 10 indeholder en null-pointer, 405 00:20:17,930 --> 00:20:20,200 men 10 er ikke i sig selv en null pointer lige nu, 406 00:20:20,200 --> 00:20:22,470 og så den passerer sorteper også. 407 00:20:22,470 --> 00:20:25,560 >> Og nu liste punkter der, det ville virkelig pege på some-- 408 00:20:25,560 --> 00:20:28,710 hvis jeg havde mere plads i billedet, det ville pege på nogle tilfældige plads 409 00:20:28,710 --> 00:20:29,960 at vi ikke ved, hvad det er. 410 00:20:29,960 --> 00:20:34,680 Det er null pointer selv, listen bogstaveligt talt nu sat det værdier null. 411 00:20:34,680 --> 00:20:36,820 Det peger lige inde at røde felt. 412 00:20:36,820 --> 00:20:39,960 Vi nåede en null-pointer, så Vi kan stoppe, og vi er færdig. 413 00:20:39,960 --> 00:20:46,230 >> Og så lilla ramme er nu-- på toppen af ​​stack-- der er den aktive ramme, 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ået en null-pointer, stop. 416 00:20:48,600 --> 00:20:51,290 Vi gør ikke noget, vi kan ikke slippe en null-pointer, 417 00:20:51,290 --> 00:20:55,070 vi ikke malloc nogen plads, og så vi er færdig. 418 00:20:55,070 --> 00:20:57,590 Således at funktionen ramme er ødelagt, og vi 419 00:20:57,590 --> 00:21:00,930 resume-- vi fortsætte, hvor vi forlod ud med den næsthøjeste en, hvilket 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 samle op lige der, hvor vi slap. 422 00:21:04,390 --> 00:21:06,598 Vi udgår resten af listen allerede, så nu er vi 423 00:21:06,598 --> 00:21:08,000 kommer til at frigøre de nuværende knudepunkter. 424 00:21:08,000 --> 00:21:12,920 Så nu kan vi befri denne node, og nu vi har nået slutningen af ​​funktionen. 425 00:21:12,920 --> 00:21:16,810 Og så funktionen ramme er ødelagt, og vi samle op på den lyseblå én. 426 00:21:16,810 --> 00:21:20,650 >> Så det says-- Jeg har allerede done-- slette resten af ​​listen, så 427 00:21:20,650 --> 00:21:23,140 frigøre den aktuelle node. 428 00:21:23,140 --> 00:21:26,520 Og nu den gule ramme er tilbage på toppen af ​​stakken. 429 00:21:26,520 --> 00:21:29,655 Og så som du ser, er vi nu ødelægge listen fra højre til venstre. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Hvad ville der være sket, selv om, hvis vi havde gjort tingene på den forkerte vej? 432 00:21:37,280 --> 00:21:39,410 Ligesom da vi forsøgte at tilføje et element. 433 00:21:39,410 --> 00:21:41,909 Hvis vi rodet op kæden, hvis vi ikke tilslutte pointers 434 00:21:41,909 --> 00:21:44,690 i den rigtige rækkefølge, hvis vi netop befriet det første element, 435 00:21:44,690 --> 00:21:47,420 hvis vi bare befriet leder af listen, nu er vi 436 00:21:47,420 --> 00:21:49,642 har ingen måde at henvise til resten af ​​listen. 437 00:21:49,642 --> 00:21:51,350 Og så ville vi have forældreløse alt, 438 00:21:51,350 --> 00:21:53,880 ville vi have haft, hvad der er kaldes en hukommelsesfejl. 439 00:21:53,880 --> 00:21:56,800 Hvis du husker fra vores video på dynamisk hukommelse tildeling, 440 00:21:56,800 --> 00:21:58,650 det er ikke meget god ting. 441 00:21:58,650 --> 00:22:00,810 >> Så som jeg sagde, er der er flere operationer 442 00:22:00,810 --> 00:22:04,010 at vi skal bruge for at arbejde med sammenkædet liste effektivt. 443 00:22:04,010 --> 00:22:08,430 Og du måske har bemærket jeg udeladt en, sletning af et enkelt element fra en forbundet 444 00:22:08,430 --> 00:22:09,064 listen. 445 00:22:09,064 --> 00:22:10,980 Grunden til at jeg gjorde det er det er faktisk slags 446 00:22:10,980 --> 00:22:14,360 vanskelig at tænke over, hvordan du sletter et enkelt element fra en enkeltvis 447 00:22:14,360 --> 00:22:15,600 sammenkædet liste. 448 00:22:15,600 --> 00:22:19,950 Vi skal være i stand til at springe over noget på listen, som 449 00:22:19,950 --> 00:22:22,975 betyder, at vi kommer til en point-- vi vil slette denne node-- 450 00:22:22,975 --> 00:22:25,350 men for at gøre det så vi ikke mister nogen oplysninger, 451 00:22:25,350 --> 00:22:30,530 vi nødt til at tilslutte denne node herovre, her. 452 00:22:30,530 --> 00:22:33,390 >> Så sandsynligvis gjorde jeg, at forkert fra et visuelt perspektiv. 453 00:22:33,390 --> 00:22:36,830 Så vi er i begyndelsen af ​​vores liste, vi fortsætter igennem, 454 00:22:36,830 --> 00:22:40,510 vi ønsker at slette denne node. 455 00:22:40,510 --> 00:22:43,440 Hvis vi bare slette det, vi har brudt kæden. 456 00:22:43,440 --> 00:22:45,950 Denne knude lige her refererer til alt andet, 457 00:22:45,950 --> 00:22:48,260 det indeholder kæden fra nu af. 458 00:22:48,260 --> 00:22:51,190 >> Så hvad vi skal gøre rent faktisk efter at vi kommer til dette punkt, 459 00:22:51,190 --> 00:22:56,670 er vi nødt til at træde et skridt tilbage én, og forbinde denne node over til dette knudepunkt, 460 00:22:56,670 --> 00:22:58,590 så vi kan derefter slette den ene i midten. 461 00:22:58,590 --> 00:23:02,120 Men enkeltvis hægtede lister ikke giver os en måde at gå baglæns. 462 00:23:02,120 --> 00:23:05,160 Så vi er nødt til enten at holde to pegepinde, og flytte dem 463 00:23:05,160 --> 00:23:09,527 slags off trin, den ene bag den anden som vi går, eller komme til et punkt 464 00:23:09,527 --> 00:23:11,110 og sende derefter en anden pointer igennem. 465 00:23:11,110 --> 00:23:13,150 Og som du kan se, er det kan få lidt rodet. 466 00:23:13,150 --> 00:23:15,360 Heldigvis har vi En anden måde at løse dette, 467 00:23:15,360 --> 00:23:17,810 når vi taler om dobbelt hægtede lister. 468 00:23:17,810 --> 00:23:20,720 >> Jeg er Doug Lloyd, det er CS50. 469 00:23:20,720 --> 00:23:22,298