1 00:00:00,000 --> 00:00:02,832 >> [MUSIK SPELA] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG Lloyd: OK, så på denna punkt i kursen, 4 00:00:08,560 --> 00:00:15,300 Vi har täckt en hel del av grunderna i C. Vi vet en hel del om variabler, arrayer, 5 00:00:15,300 --> 00:00:17,610 pekare, så bra grejer. 6 00:00:17,610 --> 00:00:21,610 De är alla slags inbyggt i att se som grunderna, 7 00:00:21,610 --> 00:00:23,880 men vi kan göra mer, eller hur? 8 00:00:23,880 --> 00:00:27,930 Vi kan kombinera saker tillsammans på ett intressant sätt. 9 00:00:27,930 --> 00:00:31,010 >> Och så låt oss göra det, låt oss börja filial ut vad C ger oss, 10 00:00:31,010 --> 00:00:35,270 och börja skapa våra egna uppgifter strukturer med hjälp av dessa byggnad 11 00:00:35,270 --> 00:00:40,590 block tillsammans för att göra något riktigt värdefullt, användbar. 12 00:00:40,590 --> 00:00:43,420 Ett sätt som vi kan göra det här är att prata om samlingarna. 13 00:00:43,420 --> 00:00:48,360 Så hittills har vi haft en typ av data struktur för att representera samlingar 14 00:00:48,360 --> 00:00:51,030 av gillar värden, liknande värden. 15 00:00:51,030 --> 00:00:52,350 Det skulle vara en matris. 16 00:00:52,350 --> 00:00:57,020 Vi har samlingar av heltal, eller samlingar av tecken och så vidare. 17 00:00:57,020 --> 00:01:00,890 >> Strukturer också sortera av ett data struktur för insamling av information, 18 00:01:00,890 --> 00:01:03,220 men det är inte för att samla liknande värden. 19 00:01:03,220 --> 00:01:08,090 Det blandar oftast olika datatyper tillsammans inne i en enda låda. 20 00:01:08,090 --> 00:01:10,750 Men det är inte i sig används för att kedja ihop 21 00:01:10,750 --> 00:01:16,920 eller koppla samman liknande poster, som en array. 22 00:01:16,920 --> 00:01:20,960 Arrayer är bra för elementet titta upp, men minns 23 00:01:20,960 --> 00:01:24,262 att det är mycket svårt att infoga i en matris, 24 00:01:24,262 --> 00:01:26,470 om vi införa åtmin alldeles i slutet av denna matris. 25 00:01:26,470 --> 00:01:29,730 >> Och det bästa exemplet jag har för det är insättningssortering. 26 00:01:29,730 --> 00:01:31,650 Om ni minns vår video på insättningssortering, 27 00:01:31,650 --> 00:01:34,110 Det fanns en hel del kostnader inblandade i att ha 28 00:01:34,110 --> 00:01:37,970 att plocka upp delar, och flytta dem ur vägen för att passa något 29 00:01:37,970 --> 00:01:41,290 i mitten av matrisen. 30 00:01:41,290 --> 00:01:44,690 Arrayer lider också av en annan problem, som är stelhet. 31 00:01:44,690 --> 00:01:47,150 När vi förklarar en array, vi får ett skott på det. 32 00:01:47,150 --> 00:01:49,790 Vi får säga, jag vill här många element. 33 00:01:49,790 --> 00:01:51,940 Kan vara 100, kanske det vara 1000, kanske det 34 00:01:51,940 --> 00:01:55,930 vara där x är ett nummer som användaren gav oss vid en prompt eller kommandot 35 00:01:55,930 --> 00:01:56,630 linje. 36 00:01:56,630 --> 00:01:59,905 >> Men vi får bara ett skott på det, vi inte får sedan säga åh, jag faktiskt 37 00:01:59,905 --> 00:02:04,360 behövs 101, eller jag behövde x plus 20. 38 00:02:04,360 --> 00:02:07,910 För sent, vi har redan förklarat array, och om vi vill få 101 eller X 39 00:02:07,910 --> 00:02:12,050 plus 20, måste vi förklara en helt annan uppsättning, 40 00:02:12,050 --> 00:02:15,540 kopiera alla element i arrayen över, och sedan har vi nog. 41 00:02:15,540 --> 00:02:19,880 Och tänk om vi har fel igen, vad om vi verkligen behöver 102, eller x plus 40, 42 00:02:19,880 --> 00:02:21,970 Vi måste göra detta igen. 43 00:02:21,970 --> 00:02:26,250 Så de är mycket oflexibel för att ändra storlek våra data, 44 00:02:26,250 --> 00:02:29,360 men om vi kombinerar ihop några av grunderna som vi redan har 45 00:02:29,360 --> 00:02:33,230 lärt sig om pekare och strukturer, särskilt genom dynamiskt minne 46 00:02:33,230 --> 00:02:36,180 tilldelning med malloc, vi kan sätta in dessa bitar tillsammans 47 00:02:36,180 --> 00:02:40,960 att skapa en ny data structure-- en Listan kan vi säga-- ensamma kopplade 48 00:02:40,960 --> 00:02:45,400 som tillåter oss att växa och krympa en samling värden 49 00:02:45,400 --> 00:02:48,800 och vi kommer inte att ha någon slösat utrymme. 50 00:02:48,800 --> 00:02:53,320 >> Så återigen, vi kallar denna idé, detta begrepp, en länkad lista. 51 00:02:53,320 --> 00:02:56,320 I synnerhet i den här videon är vi talar om enskilt länkad lista, 52 00:02:56,320 --> 00:02:59,185 och sedan en annan video vi ska prata om dubbelt länkade listor, som 53 00:02:59,185 --> 00:03:01,560 är bara en variation på ett tema här. 54 00:03:01,560 --> 00:03:05,200 Men en enskilt länkad lista består av noder, 55 00:03:05,200 --> 00:03:08,559 noder bara vara ett abstrakt term-- Det är bara något jag ringer 56 00:03:08,559 --> 00:03:10,350 det är en sorts struktur, i princip, jag är? 57 00:03:10,350 --> 00:03:16,190 Bara kommer att kalla det en node-- och detta nod har två medlemmar, eller två fält. 58 00:03:16,190 --> 00:03:20,300 Det har data, vanligtvis ett heltal, en karaktär flyta, 59 00:03:20,300 --> 00:03:23,790 eller kan vara någon annan datatyp att du har definierat med en typ def. 60 00:03:23,790 --> 00:03:29,290 Och den innehåller en pekare till annan nod av samma typ. 61 00:03:29,290 --> 00:03:34,710 >> Så vi har två saker inuti denna nod, information och en pekare 62 00:03:34,710 --> 00:03:36,380 till en annan nod. 63 00:03:36,380 --> 00:03:39,370 Och om du börjar att visualisera detta kan du tänka på det 64 00:03:39,370 --> 00:03:42,280 som en kedja av noder som är förbundna med varandra. 65 00:03:42,280 --> 00:03:45,070 Vi har den första noden, det innehåller data, och en pekare 66 00:03:45,070 --> 00:03:49,110 till den andra noden, som innehåller uppgifter, och en pekare till den tredje noden. 67 00:03:49,110 --> 00:03:52,940 Och så det är därför vi kallar det en länkad lista, de är sammanlänkade. 68 00:03:52,940 --> 00:03:56,070 >> Vad gör detta speciella nod struktur ser ut? 69 00:03:56,070 --> 00:04:01,120 Tja, om du minns från vår video på definiera egna typer med typ def, 70 00:04:01,120 --> 00:04:05,400 Vi kan definiera en structure-- och Skriv definiera en struktur som denna. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, och då är jag använda ordet värde här godtyckligt 72 00:04:11,240 --> 00:04:13,891 att ange någon datatyp verkligen. 73 00:04:13,891 --> 00:04:16,890 Du kan vidarebefordra ett heltal eller float, du kan ha vad du vill. 74 00:04:16,890 --> 00:04:19,389 Det är inte begränsat till bara heltal, eller nåt sånt. 75 00:04:19,389 --> 00:04:22,790 Så värdet är bara en godtycklig datatyp och sedan en pekare 76 00:04:22,790 --> 00:04:26,310 till en annan nod av samma typ. 77 00:04:26,310 --> 00:04:29,690 >> Nu finns det en liten hake här med att definiera en struktur 78 00:04:29,690 --> 00:04:33,030 när det är en självrefererande struktur. 79 00:04:33,030 --> 00:04:35,340 Jag måste ha en tillfällig namn för min struktur. 80 00:04:35,340 --> 00:04:37,640 I slutet av dagen I klart vill kalla det 81 00:04:37,640 --> 00:04:43,030 SLL nod, är det i slutändan nya nämna en del av min definition typ, 82 00:04:43,030 --> 00:04:47,450 men jag kan inte använda SLL nod i mitten av denna. 83 00:04:47,450 --> 00:04:51,430 Anledningen är, har jag inte skapat en typ som kallas SLL nod 84 00:04:51,430 --> 00:04:55,200 tills jag hit denna sista punkt här. 85 00:04:55,200 --> 00:04:59,720 Fram till den punkten, jag måste ha ett annat sätt att hänvisa till den här datatypen. 86 00:04:59,720 --> 00:05:02,440 >> Och detta är en själv Referens datatyp. 87 00:05:02,440 --> 00:05:06,314 Det; s en datatyp en struktur som innehåller ett data, 88 00:05:06,314 --> 00:05:08,480 och en pekare till en annan struktur av samma typ. 89 00:05:08,480 --> 00:05:11,750 Så jag behöver för att kunna hänvisa till den här datatypen åtminstone tillfälligt, 90 00:05:11,750 --> 00:05:14,910 så ger det en temporär namn struct sllist 91 00:05:14,910 --> 00:05:18,540 låter mig då säga att jag vill ha en pekare till en annan struct sllist, 92 00:05:18,540 --> 00:05:24,690 en struct sllist stjärna, och sedan efter att jag har slutfört definition, 93 00:05:24,690 --> 00:05:27,220 Jag kan nu kalla denna typ en SLL nod. 94 00:05:27,220 --> 00:05:30,520 >> Så det är därför du ser att det finns ett tillfälligt namn här, 95 00:05:30,520 --> 00:05:31,879 men en permanent namn här. 96 00:05:31,879 --> 00:05:33,920 Ibland kan du se definitioner av strukturen, 97 00:05:33,920 --> 00:05:36,570 till exempel, som inte är självrefererande, att 98 00:05:36,570 --> 00:05:39,390 inte har en specificeraren namn här. 99 00:05:39,390 --> 00:05:43,040 Det skulle bara säga typedef struct, öppna klammerparentes och sedan definiera den. 100 00:05:43,040 --> 00:05:45,620 Men om du är struct är själv referens, som denna är, 101 00:05:45,620 --> 00:05:49,010 måste du ange en temporärt namn typ. 102 00:05:49,010 --> 00:05:51,310 Men i slutändan, nu att vi har gjort detta, 103 00:05:51,310 --> 00:05:53,620 vi kan bara referera till dessa noder, dessa enheter, 104 00:05:53,620 --> 00:05:57,900 som SLL noder för ändamål av resten av den här videon. 105 00:05:57,900 --> 00:06:00,900 >> Okej, så vi vet hur man skapa en länkad lista nod. 106 00:06:00,900 --> 00:06:03,240 Vi vet hur man definierar en länkad lista nod. 107 00:06:03,240 --> 00:06:06,670 Nu, om vi ska börja använda dem för att samla in information, 108 00:06:06,670 --> 00:06:10,360 det finns ett par operationer vi måste förstå och arbeta med. 109 00:06:10,360 --> 00:06:12,860 Vi behöver veta hur man skapar en länkad lista ur luften. 110 00:06:12,860 --> 00:06:14,901 Om det inte finns någon lista redan Vi vill starta en. 111 00:06:14,901 --> 00:06:16,960 Så vi behöver för att kunna att skapa en länkad lista, 112 00:06:16,960 --> 00:06:19,130 Vi måste förmodligen söka via länken listan 113 00:06:19,130 --> 00:06:21,830 att hitta ett element som vi letar efter. 114 00:06:21,830 --> 00:06:24,430 Vi måste kunna sätta in nya saker i listan, 115 00:06:24,430 --> 00:06:25,930 Vi vill att vår lista för att kunna växa. 116 00:06:25,930 --> 00:06:28,638 Och på samma sätt vill vi kunna att ta bort saker från vår lista, 117 00:06:28,638 --> 00:06:30,250 Vi vill att vår lista för att kunna krympa. 118 00:06:30,250 --> 00:06:32,160 Och i slutet av vår program, i synnerhet 119 00:06:32,160 --> 00:06:34,550 om ni minns att vi är dynamiskt allokera minne 120 00:06:34,550 --> 00:06:38,337 att bygga dessa listor typiskt vi vill befria allt detta minne 121 00:06:38,337 --> 00:06:39,670 När vi är klara att arbeta med det. 122 00:06:39,670 --> 00:06:44,627 Och så vi måste kunna ta bort en Hela länkad lista i en misslyckas svep. 123 00:06:44,627 --> 00:06:46,460 Så låt oss gå igenom några av dessa operationer 124 00:06:46,460 --> 00:06:51,192 och hur vi kan visualisera dem, talar i pseudokod kod specifikt. 125 00:06:51,192 --> 00:06:53,150 Så vi vill skapa en lista kopplad, så kanske vi 126 00:06:53,150 --> 00:06:56,480 vill definiera en funktion med denna prototyp. 127 00:06:56,480 --> 00:07:01,690 SLL nod stjärna, skapa och jag passerar i ett argument, en del godtyckligt data 128 00:07:01,690 --> 00:07:05,530 skriver igen, av någon godtycklig datatyp. 129 00:07:05,530 --> 00:07:10,482 Men jag returning-- denna funktion bör tillbaka till mig en pekare till ett enskilt 130 00:07:10,482 --> 00:07:11,190 länkad lista nod. 131 00:07:11,190 --> 00:07:14,050 Återigen, vi försöker att skapa en länkad lista ur luften, 132 00:07:14,050 --> 00:07:17,900 så jag behöver en pekare till den listan när jag är klar. 133 00:07:17,900 --> 00:07:19,420 >> Så vad är stegen här? 134 00:07:19,420 --> 00:07:20,960 Tja, första jag kommer att göra är dynamiskt 135 00:07:20,960 --> 00:07:22,550 allokera utrymme för en ny nod. 136 00:07:22,550 --> 00:07:26,689 Återigen, vi skapar det ur tomma luft, så vi måste malloc utrymme för det. 137 00:07:26,689 --> 00:07:28,480 Och naturligtvis, omedelbart när vi malloc, 138 00:07:28,480 --> 00:07:31,692 vi alltid kontrollera att se till att vår pointer-- vi inte få tillbaka noll. 139 00:07:31,692 --> 00:07:33,650 För om vi försöker och aktning en null-pekare, 140 00:07:33,650 --> 00:07:36,190 vi kommer att drabbas av en segfault och vi vill inte ha det. 141 00:07:36,190 --> 00:07:39,510 >> Sedan vi vill fylla i fältet, Vi vill initiera värdefältet 142 00:07:39,510 --> 00:07:41,690 och initiera nästa fält. 143 00:07:41,690 --> 00:07:45,450 Och sedan vill vi att-- småningom som funktionsprototyp indicates-- vi vill 144 00:07:45,450 --> 00:07:49,940 att returnera en pekare till en SLL nod. 145 00:07:49,940 --> 00:07:51,710 Så vad gör detta ser ut visuellt? 146 00:07:51,710 --> 00:07:55,230 Tja, först ska vi dynamiskt allokera utrymme för en ny SLL nod, 147 00:07:55,230 --> 00:07:58,320 så vi malloc-- det är en visuell representation 148 00:07:58,320 --> 00:08:00,020 av noden vi just skapat. 149 00:08:00,020 --> 00:08:02,757 Och vi kontrollera att det är inte null-- i detta fall, 150 00:08:02,757 --> 00:08:04,840 bilden skulle inte ha visas upp om det var noll, 151 00:08:04,840 --> 00:08:07,298 vi skulle ha slut på minne, så vi är bra att åka dit. 152 00:08:07,298 --> 00:08:10,200 Så nu är vi vidare till steg C, initialisera noderna värdefältet. 153 00:08:10,200 --> 00:08:12,280 Tja, baserat på denna funktion kallar jag använder här, 154 00:08:12,280 --> 00:08:16,700 ser ut som jag vill passera på 6, så jag ska 6 i värdefältet. 155 00:08:16,700 --> 00:08:18,865 Nu, initiera nästa fält. 156 00:08:18,865 --> 00:08:21,640 Tja, vad ska jag göra där, det finns inget nästa, höger, 157 00:08:21,640 --> 00:08:23,600 Detta är det enda i listan. 158 00:08:23,600 --> 00:08:27,206 Så vad är nästa sak på listan? 159 00:08:27,206 --> 00:08:29,660 >> Det bör inte peka på någonting, höger. 160 00:08:29,660 --> 00:08:33,600 Det finns inget annat där, så vad är Begreppet vi känner till som är nothing-- 161 00:08:33,600 --> 00:08:35,638 pekare till ingenting? 162 00:08:35,638 --> 00:08:37,929 Det borde vara kanske vi vill att sätta en null-pekare där, 163 00:08:37,929 --> 00:08:40,178 och jag ska representera null pekaren som bara en röd ruta, 164 00:08:40,178 --> 00:08:41,559 vi kan inte gå längre. 165 00:08:41,559 --> 00:08:44,430 Som vi ser lite senare, Vi kommer att ha så småningom kedjor 166 00:08:44,430 --> 00:08:46,330 av pilar som förbinder dessa noder tillsammans, 167 00:08:46,330 --> 00:08:48,480 men när du träffar röda rutan, det är noll, 168 00:08:48,480 --> 00:08:51,150 vi kan inte gå längre, det är slutet av listan. 169 00:08:51,150 --> 00:08:53,960 >> Och slutligen, vi vill bara returnera en pekare till denna nod. 170 00:08:53,960 --> 00:08:56,160 Så vi kallar det nya, och kommer tillbaka nya 171 00:08:56,160 --> 00:08:59,370 så att den kan användas i oavsett funktion skapade den. 172 00:08:59,370 --> 00:09:03,100 Så det vi går, har vi skapat en för sig länkad lista nod ur luften, 173 00:09:03,100 --> 00:09:05,920 och nu har vi en lista som vi kan arbeta med. 174 00:09:05,920 --> 00:09:08,260 >> Nu, låt oss säga att vi redan ha en stor kedja, 175 00:09:08,260 --> 00:09:09,800 och vi vill hitta något i det. 176 00:09:09,800 --> 00:09:12,716 Och vi vill ha en funktion som kommer att återvända sant eller falskt, beroende 177 00:09:12,716 --> 00:09:15,840 om huruvida ett värde finns i listan. 178 00:09:15,840 --> 00:09:18,160 En funktion prototyp eller deklaration för denna funktion, 179 00:09:18,160 --> 00:09:23,320 kan se ut this-- Bool hitta, och då vill vi att passera i två argument. 180 00:09:23,320 --> 00:09:26,996 >> Den första är en pekare till första elementet i länklistan. 181 00:09:26,996 --> 00:09:29,620 Detta är faktiskt något du alltid vill hålla reda på, 182 00:09:29,620 --> 00:09:33,110 och faktiskt kan vara något som du även sätta i en global variabel. 183 00:09:33,110 --> 00:09:35,360 När du har skapat en lista, du alltid, alltid 184 00:09:35,360 --> 00:09:38,990 vill hålla reda på den mycket första elementet i listan. 185 00:09:38,990 --> 00:09:43,690 På så sätt kan du hänvisa till alla andra element genom att bara följa kedjan, 186 00:09:43,690 --> 00:09:47,300 utan att behöva hålla pekare intakt till varje enskilt element. 187 00:09:47,300 --> 00:09:50,920 Du behöver bara hålla reda på den första ett om de är alla kedjas ihop. 188 00:09:50,920 --> 00:09:52,460 >> Och sedan den andra saken vi passerar igen 189 00:09:52,460 --> 00:09:54,376 är godtyckligt some-- oavsett datatyp vi 190 00:09:54,376 --> 00:09:59,640 efter det är inne i förhoppningsvis en av noderna i listan. 191 00:09:59,640 --> 00:10:00,980 Så vad är stegen? 192 00:10:00,980 --> 00:10:04,250 Tja, är det första vi gör Vi skapar en övergripande pekare 193 00:10:04,250 --> 00:10:06,015 pekar på listorna huvudet. 194 00:10:06,015 --> 00:10:08,890 Tja, varför gör vi det, vi redan har en pekare på listorna huvudet, 195 00:10:08,890 --> 00:10:10,974 varför inte vi bara flytta den en runt? 196 00:10:10,974 --> 00:10:13,140 Tja, som jag just sagt, det är verkligen viktigt för oss 197 00:10:13,140 --> 00:10:17,580 att alltid hålla reda på mycket första elementet i listan. 198 00:10:17,580 --> 00:10:21,270 Och så är det faktiskt bättre att skapa en kopia av det, 199 00:10:21,270 --> 00:10:25,350 och använda det för att flytta runt så vi aldrig oavsiktligt flytta bort, eller vi alltid 200 00:10:25,350 --> 00:10:30,430 har en pekare vid någon tidpunkt som är rätt på det första elementet i listan. 201 00:10:30,430 --> 00:10:33,290 Så det är bättre att skapa en andra som vi använder för att flytta. 202 00:10:33,290 --> 00:10:35,877 >> Då vi jämför bara om värdet fältet vid denna nod 203 00:10:35,877 --> 00:10:38,960 är vad vi letar efter, och om det är inte, vi bara gå vidare till nästa nod. 204 00:10:38,960 --> 00:10:41,040 Och vi fortsätta att göra det över, och över, och över, 205 00:10:41,040 --> 00:10:44,811 tills vi antingen hitta elementet, eller vi hit 206 00:10:44,811 --> 00:10:47,310 null-- vi har nått slutet på listan och det är inte det. 207 00:10:47,310 --> 00:10:50,540 Detta bör förhoppningsvis ringa en klocka till dig som bara linjär sökning, 208 00:10:50,540 --> 00:10:54,430 vi bara replikera det i en enskilt länkad lista struktur 209 00:10:54,430 --> 00:10:56,280 istället för att använda en matris för att göra det. 210 00:10:56,280 --> 00:10:58,210 >> Så här är ett exempel på en enskilt länkad lista. 211 00:10:58,210 --> 00:11:00,043 Detta består av fem noder, och vi har 212 00:11:00,043 --> 00:11:04,330 en pekare till chefen för listan, som kallas listan. 213 00:11:04,330 --> 00:11:07,385 Det första vi vill göra är igen, skapa den genomgångs pekare. 214 00:11:07,385 --> 00:11:09,760 Så vi har nu två pekare som pekar på samma sak. 215 00:11:09,760 --> 00:11:15,025 >> Nu märker här också, det gjorde jag inte måste malloc något utrymme för trav. 216 00:11:15,025 --> 00:11:18,970 Jag sa inte trav lika malloc något, redan denna nod, 217 00:11:18,970 --> 00:11:21,160 detta utrymme i minnet finns redan. 218 00:11:21,160 --> 00:11:24,290 Så allt jag faktiskt gör är skapa en annan pekare till det. 219 00:11:24,290 --> 00:11:28,210 Jag är inte mallocing ytterligare utrymme, bara har nu två pekare 220 00:11:28,210 --> 00:11:31,370 pekar på samma sak. 221 00:11:31,370 --> 00:11:33,710 >> Så är 2 vad jag letar efter? 222 00:11:33,710 --> 00:11:37,220 Tja, nej, så i stället jag kommer att flytta till nästa. 223 00:11:37,220 --> 00:11:41,740 Så i princip skulle jag säga, trav lika trav nästa. 224 00:11:41,740 --> 00:11:43,630 Är 3 vad jag letar efter, nej. 225 00:11:43,630 --> 00:11:45,780 Så jag fortsätter att gå igenom, tills slutligen 226 00:11:45,780 --> 00:11:48,690 få till 6 vilket är vad jag ser för baserat på funktionsanrop 227 00:11:48,690 --> 00:11:51,600 Jag har på toppen där, och så jag är klar. 228 00:11:51,600 --> 00:11:54,150 >> Nu, vad händer om elementet jag söker inte finns i listan, 229 00:11:54,150 --> 00:11:55,510 är det fortfarande kommer att fungera? 230 00:11:55,510 --> 00:11:57,120 Tja, märker att listan här är subtilt olika, 231 00:11:57,120 --> 00:11:59,410 och detta är en annan sak som är viktigt med länkade listor, 232 00:11:59,410 --> 00:12:01,780 du behöver inte för att bevara dem i någon särskild ordning. 233 00:12:01,780 --> 00:12:05,390 Du kan om du vill, men Du kanske redan har märkt 234 00:12:05,390 --> 00:12:09,310 att vi inte hålla reda på vilket nummer elementet vi befinner oss i. 235 00:12:09,310 --> 00:12:13,150 >> Och det blir liksom en handel som vi har med länkad lista verser arrayer, 236 00:12:13,150 --> 00:12:15,300 är det att vi inte har direktåtkomst längre. 237 00:12:15,300 --> 00:12:18,150 Vi kan inte bara säga, jag vill att gå till 0. elementet, 238 00:12:18,150 --> 00:12:21,410 eller 6:e ​​elementet i min array, som jag kan göra i en rad. 239 00:12:21,410 --> 00:12:25,080 Jag kan inte säga att jag vill gå till 0. Element, eller 6: e elementet, 240 00:12:25,080 --> 00:12:30,360 eller den 25: e elementet i min länkad lista, det finns inget index i samband med dem. 241 00:12:30,360 --> 00:12:33,660 Och så det spelar ingen egentligen ingen roll om vi bevara vår lista i ordning. 242 00:12:33,660 --> 00:12:36,080 Om du vill kan du säkert kan, men det finns 243 00:12:36,080 --> 00:12:38,567 ingen anledning till varför de behöver bevaras i vilken som helst ordning. 244 00:12:38,567 --> 00:12:40,400 Så återigen, låt oss försöka och hitta 6 i den här listan. 245 00:12:40,400 --> 00:12:43,200 Tja, börjar vi på början, vi inte hitta 6, 246 00:12:43,200 --> 00:12:47,690 och då kan vi inte fortsätta att hitta 6, tills vi så småningom hit. 247 00:12:47,690 --> 00:12:52,790 Så just nu trav pekar på noden innehållande 8, och sex är inte där. 248 00:12:52,790 --> 00:12:55,250 >> Så nästa steg skulle vara för att gå till nästa pekaren, 249 00:12:55,250 --> 00:12:57,440 så säger trav lika trav nästa. 250 00:12:57,440 --> 00:13:00,750 Tja, trav nästa, indikeras av den röda lådan finns, är null. 251 00:13:00,750 --> 00:13:03,020 Så det finns ingen annanstans att gå, och så på denna punkt 252 00:13:03,020 --> 00:13:06,120 Vi kan konstatera att vi har nått I slutet av den länkade listan, 253 00:13:06,120 --> 00:13:07,190 och 6 är inte där. 254 00:13:07,190 --> 00:13:10,980 Och det skulle återlämnas false i detta fall. 255 00:13:10,980 --> 00:13:14,540 >> OK, hur ska vi sätta in en ny nod i den länkade listan? 256 00:13:14,540 --> 00:13:17,310 Så vi har kunnat skapa en länkad lista från ingenstans, 257 00:13:17,310 --> 00:13:19,370 men vi vill förmodligen bygga en kedja och inte 258 00:13:19,370 --> 00:13:22,620 skapa en massa olika listor. 259 00:13:22,620 --> 00:13:25,700 Vi vill ha en lista som har ett gäng noder i det, 260 00:13:25,700 --> 00:13:28,040 inte en grupp av listor med en enda nod. 261 00:13:28,040 --> 00:13:31,260 Så vi kan inte bara fortsätta att använda Skapa funktion vi definierade tidigare, nu är vi 262 00:13:31,260 --> 00:13:33,860 vill infoga i en lista som redan finns. 263 00:13:33,860 --> 00:13:36,499 >> Så det här fallet, kommer vi att passera i två argument, 264 00:13:36,499 --> 00:13:39,290 pekaren till chefen för att lista som vi vill lägga till länkade. 265 00:13:39,290 --> 00:13:40,910 Återigen, det är därför det är så viktigt att vi alltid 266 00:13:40,910 --> 00:13:43,400 hålla reda på det, eftersom Det är det enda sättet vi verkligen 267 00:13:43,400 --> 00:13:46,690 måste hänföra sig till hela listan är bara genom en pekare till det första elementet. 268 00:13:46,690 --> 00:13:49,360 Så vi vill passera på en pekare till det första elementet, 269 00:13:49,360 --> 00:13:52,226 och oavsett värde som vi vill lägga till i listan. 270 00:13:52,226 --> 00:13:54,600 Och så småningom denna funktion kommer att returnera en pekare 271 00:13:54,600 --> 00:13:57,980 till ny chef för en länkad lista. 272 00:13:57,980 --> 00:13:59,700 >> Vilka är de steg som ingår här? 273 00:13:59,700 --> 00:14:02,249 Jo, precis som med att skapa, vi behöver för att dynamiskt allokera 274 00:14:02,249 --> 00:14:05,540 utrymme för en ny nod och kontrollera att göra att vi inte får slut på minne, återigen, 275 00:14:05,540 --> 00:14:07,150 eftersom vi använder malloc. 276 00:14:07,150 --> 00:14:09,080 Då kan vi vill fylla och sätt i noden, 277 00:14:09,080 --> 00:14:12,730 så uppskattar antalet, oavsett Val är, in i noden. 278 00:14:12,730 --> 00:14:17,310 Vi vill infoga noden på början av den länkade listan. 279 00:14:17,310 --> 00:14:19,619 >> Det finns en anledning till att jag vill göra detta, och det 280 00:14:19,619 --> 00:14:21,910 kan vara värt att ta en andra att pausa videon här, 281 00:14:21,910 --> 00:14:25,860 och fundera på varför jag skulle vilja infoga i början av en länkad 282 00:14:25,860 --> 00:14:26,589 listan. 283 00:14:26,589 --> 00:14:28,630 Återigen, jag nämnde tidigare att det egentligen inte 284 00:14:28,630 --> 00:14:33,020 roll om vi bevara det på något ordning, så kanske det är en ledtråd. 285 00:14:33,020 --> 00:14:36,040 Och du såg vad som skulle hända om vi ville att-- eller bara en sekund 286 00:14:36,040 --> 00:14:37,360 sedan när vi var på väg genom ökning kan 287 00:14:37,360 --> 00:14:39,235 kunde se vad som kan hända om vi försökte 288 00:14:39,235 --> 00:14:41,330 att infoga i slutet av listan. 289 00:14:41,330 --> 00:14:44,750 Eftersom vi inte har en pekaren till slutet av listan. 290 00:14:44,750 --> 00:14:47,490 >> Så anledningen till att jag skulle vilja att infoga i början, 291 00:14:47,490 --> 00:14:49,380 är att jag kan göra det omedelbart. 292 00:14:49,380 --> 00:14:52,730 Jag har en pekare i början, och vi får se detta i ett visuellt i en sekund. 293 00:14:52,730 --> 00:14:55,605 Men om jag vill infoga i slutet, Jag måste börja från början, 294 00:14:55,605 --> 00:14:58,760 passera hela vägen till änden, och sedan lägga fram det på. 295 00:14:58,760 --> 00:15:01,420 Så det skulle innebära att införing i slutet av listan 296 00:15:01,420 --> 00:15:04,140 skulle bli en o n drift, kommer tillbaka 297 00:15:04,140 --> 00:15:06,720 till vår diskussion om beräkningskomplexitet. 298 00:15:06,720 --> 00:15:10,140 Det skulle bli en o n drift, där som listan blev större och större, 299 00:15:10,140 --> 00:15:13,310 och större, kommer det att bli mer och svårare att kryssa något 300 00:15:13,310 --> 00:15:14,661 på slutet. 301 00:15:14,661 --> 00:15:17,410 Men det är alltid riktigt enkelt att please något på i början, 302 00:15:17,410 --> 00:15:19,060 du är alltid i början. 303 00:15:19,060 --> 00:15:21,620 >> Och vi får se en visuell detta igen. 304 00:15:21,620 --> 00:15:24,100 Och sedan när vi är klara, en gång Vi har satt den nya noden, 305 00:15:24,100 --> 00:15:26,880 vi vill återvända vår pekare till ny chef för en länkad lista, som 306 00:15:26,880 --> 00:15:29,213 eftersom vi sätta in på början, faktiskt kommer att 307 00:15:29,213 --> 00:15:31,060 en pekare till noden vi just skapat. 308 00:15:31,060 --> 00:15:33,280 Låt oss visualisera detta, eftersom jag tror att det hjälper. 309 00:15:33,280 --> 00:15:36,661 >> Så här är vår lista, består av fyra delar, en nod innehåller 15, 310 00:15:36,661 --> 00:15:38,410 vilket pekar på en nod innehållande 9, som 311 00:15:38,410 --> 00:15:41,370 pekar på en nod som innehåller 13, vilket pekar på en nod som innehåller 312 00:15:41,370 --> 00:15:44,840 10, som har noll pekare som nästa pekare 313 00:15:44,840 --> 00:15:47,010 så det är i slutet av listan. 314 00:15:47,010 --> 00:15:50,200 Så vi vill infoga en nya noden med värdet 12 315 00:15:50,200 --> 00:15:52,720 i början av detta listan, vad gör vi? 316 00:15:52,720 --> 00:15:58,770 Tja, först vi malloc utrymme för nod, och sedan sätter vi 12 där. 317 00:15:58,770 --> 00:16:02,211 >> Så nu har vi nått en beslutspunkt, eller hur? 318 00:16:02,211 --> 00:16:03,960 Vi har ett par tips som vi kunde 319 00:16:03,960 --> 00:16:06,770 flytta, vilket man bör vi gå först? 320 00:16:06,770 --> 00:16:09,250 Ska vi göra 12 poäng för den nya chefen för list-- 321 00:16:09,250 --> 00:16:13,020 eller ursäkta mig, bör vi göra 12 peka på gamla chef på listan? 322 00:16:13,020 --> 00:16:15,319 Eller ska vi säga att listan börjar nu på 12. 323 00:16:15,319 --> 00:16:17,110 Det finns en skillnad där, och vi ska titta 324 00:16:17,110 --> 00:16:19,870 på vad som händer med både i en sekund. 325 00:16:19,870 --> 00:16:23,350 >> Men detta leder till en bra ämne för sidofältet, 326 00:16:23,350 --> 00:16:26,280 vilket är att en av de svåraste saker med länkade listor 327 00:16:26,280 --> 00:16:30,980 är att ordna pekarna i rätt ordning. 328 00:16:30,980 --> 00:16:34,520 Om du flyttar saker i ordning, du kan hamna oavsiktligt 329 00:16:34,520 --> 00:16:36,050 föräldralösa resten av listan. 330 00:16:36,050 --> 00:16:37,300 Och här är ett exempel på detta. 331 00:16:37,300 --> 00:16:40,540 Så låt oss gå med idén of-- Tja, vi har just skapat 12. 332 00:16:40,540 --> 00:16:43,180 Vi vet 12 kommer att vara ny chef för listan, 333 00:16:43,180 --> 00:16:47,660 och så varför inte vi går bara listan pekaren för att peka där. 334 00:16:47,660 --> 00:16:49,070 >> OK, så det är bra. 335 00:16:49,070 --> 00:16:51,560 Så nu där har 12 nästa punkt? 336 00:16:51,560 --> 00:16:54,580 Jag menar, visuellt kan vi se att det kommer att peka på 15, 337 00:16:54,580 --> 00:16:57,250 som människor det är verkligen uppenbart för oss. 338 00:16:57,250 --> 00:17:00,300 Hur datorn vet? 339 00:17:00,300 --> 00:17:02,720 Vi har inget pekar på 15 längre, eller hur? 340 00:17:02,720 --> 00:17:05,869 >> Vi har förlorat någon förmåga att hänvisa till 15. 341 00:17:05,869 --> 00:17:11,460 Vi kan inte säga nya pilen bredvid jämlikar något, det finns inget där. 342 00:17:11,460 --> 00:17:13,510 I själva verket har vi föräldralösa resten av listan 343 00:17:13,510 --> 00:17:16,465 genom att göra så, vi har oavsiktligt brutit kedjan. 344 00:17:16,465 --> 00:17:18,089 Och vi absolut inte vill göra det. 345 00:17:18,089 --> 00:17:20,000 >> Så låt oss gå tillbaka och prova det här igen. 346 00:17:20,000 --> 00:17:24,060 Kanske rätt sak att göra är att ställa in 12 nästa pekare 347 00:17:24,060 --> 00:17:28,290 till den gamla chefen för listan först, då kan vi flytta listan över. 348 00:17:28,290 --> 00:17:30,420 Och faktiskt, är att den rätt ordning att vi 349 00:17:30,420 --> 00:17:32,836 måste följa när vi är arbetar med enskilt länkad lista. 350 00:17:32,836 --> 00:17:36,460 Vi vill alltid att ansluta nytt element i listan, 351 00:17:36,460 --> 00:17:41,010 innan vi tar den typen av viktigt steget att ändra 352 00:17:41,010 --> 00:17:43,360 där chefen för den länkade listan är. 353 00:17:43,360 --> 00:17:46,740 Återigen, det är en sådan grundläggande sak, vi vill inte förlora reda på det. 354 00:17:46,740 --> 00:17:49,310 >> Så vi vill se till att allt kedjas ihop, 355 00:17:49,310 --> 00:17:52,040 innan vi går att pekaren. 356 00:17:52,040 --> 00:17:55,300 Och så detta skulle vara rätt ordning, vilket är att ansluta 12 till listan, 357 00:17:55,300 --> 00:17:57,630 sedan säga att listan börjar ett 12. 358 00:17:57,630 --> 00:18:00,860 Om vi ​​sade listan börjar vid 12 och sedan försökte ansluta 12 till listan, 359 00:18:00,860 --> 00:18:02,193 Vi har redan sett vad som händer. 360 00:18:02,193 --> 00:18:04,920 Vi förlorar listan av misstag. 361 00:18:04,920 --> 00:18:06,740 >> OK, så en sak att prata om. 362 00:18:06,740 --> 00:18:09,750 Vad händer om vi vill bli av med lista en hel kopplad på en gång? 363 00:18:09,750 --> 00:18:11,750 Återigen, vi mallocing allt detta utrymme, och så vi 364 00:18:11,750 --> 00:18:13,351 behöver frigöra den när vi är klara. 365 00:18:13,351 --> 00:18:15,350 Så nu vill vi ta bort hela den länkade listan. 366 00:18:15,350 --> 00:18:16,850 Tja, vad vill vi göra? 367 00:18:16,850 --> 00:18:20,460 >> Om vi ​​har nått nollpekare, vi vill sluta, annars bara ta bort 368 00:18:20,460 --> 00:18:23,420 resten av listan och sedan befria mig. 369 00:18:23,420 --> 00:18:28,890 Ta bort resten av listan, och sedan frigöra den aktuella noden. 370 00:18:28,890 --> 00:18:32,850 Vad gör det låter som, vilken teknik har vi pratat 371 00:18:32,850 --> 00:18:35,440 om tidigare låter det som? 372 00:18:35,440 --> 00:18:39,560 Ta bort alla andra, då komma tillbaka och ta bort mig. 373 00:18:39,560 --> 00:18:42,380 >> Det är rekursion, har vi gjort Problemet lite mindre, 374 00:18:42,380 --> 00:18:46,910 vi säger bort alla annars, då kan du ta bort mig. 375 00:18:46,910 --> 00:18:50,940 Och längre ner på gatan, nod som kommer att säga, ta bort alla andra. 376 00:18:50,940 --> 00:18:53,940 Men så småningom kommer vi att komma till punkt där listan är null 377 00:18:53,940 --> 00:18:55,310 och det är vår bas fallet. 378 00:18:55,310 --> 00:18:57,010 >> Så låt oss ta en titt på detta, och hur detta kan fungera. 379 00:18:57,010 --> 00:18:59,759 Så här är vår lista, det är samma listar vi bara talar om, 380 00:18:59,759 --> 00:19:00,980 och det finns stegen. 381 00:19:00,980 --> 00:19:04,200 Det finns en hel del text här, men förhoppningsvis visualisering kommer att hjälpa. 382 00:19:04,200 --> 00:19:08,557 >> Så vi have-- och jag drog också upp vår stackramar illustrationen 383 00:19:08,557 --> 00:19:10,890 från vår video på samtals stackar, och förhoppningsvis allt detta 384 00:19:10,890 --> 00:19:13,260 tillsammans kommer att visa dig vad som händer. 385 00:19:13,260 --> 00:19:14,510 Så här är vår pseudokoden. 386 00:19:14,510 --> 00:19:17,830 Om vi ​​når ett noll Pekare, stopp, annars 387 00:19:17,830 --> 00:19:21,320 radera resten av listan, sedan frigöra den aktuella noden. 388 00:19:21,320 --> 00:19:25,700 Så just nu, list-- pekaren att vi är 389 00:19:25,700 --> 00:19:28,410 passerar in för att förstöra punkter till 12. 390 00:19:28,410 --> 00:19:33,340 12 är inte en nollpekare, så vi är kommer att ta bort resten av listan. 391 00:19:33,340 --> 00:19:35,450 >> Vad som att ta bort resten av oss inblandade? 392 00:19:35,450 --> 00:19:37,950 Tja, betyder det att en ringa för att förstöra, säger 393 00:19:37,950 --> 00:19:42,060 att 15 är början av den resten av listan vi vill förstöra. 394 00:19:42,060 --> 00:19:47,480 Och så uppmaningen att förstöra 12 är typ av på is. 395 00:19:47,480 --> 00:19:52,690 Det är frusen där, väntar på ringa för att förstöra 15, för att avsluta sitt jobb. 396 00:19:52,690 --> 00:19:56,280 >> Tja, 15 är inte en nollpekare, och så det kommer att säga, okej, 397 00:19:56,280 --> 00:19:58,450 Tja, ta bort resten av listan. 398 00:19:58,450 --> 00:20:00,760 Resten av listan börjar vid 9, och så vi ska bara 399 00:20:00,760 --> 00:20:04,514 vänta tills du tar bort allt som grejer och sedan komma tillbaka och ta bort mig. 400 00:20:04,514 --> 00:20:06,680 Tja 9 kommer att säga, ja, Jag är inte en nollpekare, 401 00:20:06,680 --> 00:20:09,020 så radera resten listan härifrån. 402 00:20:09,020 --> 00:20:11,805 Och så försöker förstöra 13. 403 00:20:11,805 --> 00:20:15,550 13 säger: Jag är inte nollpekare, Samma sak, passerar den buck. 404 00:20:15,550 --> 00:20:17,930 10 är inte nollpekare, 10 innehåller en null-pekare, 405 00:20:17,930 --> 00:20:20,200 men 10 är inte i sig en null pekaren just nu, 406 00:20:20,200 --> 00:20:22,470 och så den passerar buck också. 407 00:20:22,470 --> 00:20:25,560 >> Och nu lista punkter där det verkligen vill påpeka att some-- 408 00:20:25,560 --> 00:20:28,710 om jag hade mer utrymme i bilden, det skulle peka på vissa slumpmässiga utrymme 409 00:20:28,710 --> 00:20:29,960 att vi inte vet vad det är. 410 00:20:29,960 --> 00:20:34,680 Det är noll pekaren men listan bokstavligen nu inställd det värden null. 411 00:20:34,680 --> 00:20:36,820 Det pekar åt höger innanför den röda rutan. 412 00:20:36,820 --> 00:20:39,960 Vi nådde en nollpekare, så vi kan stoppa, och vi är klara. 413 00:20:39,960 --> 00:20:46,230 >> Och så att lila ramen är now-- vid ovanpå stack-- som är den aktiva ramen, 414 00:20:46,230 --> 00:20:47,017 men det är gjort. 415 00:20:47,017 --> 00:20:48,600 Om vi ​​har nått en null-pekare, sluta. 416 00:20:48,600 --> 00:20:51,290 Vi gör ingenting, vi kan inte befria en null-pekare, 417 00:20:51,290 --> 00:20:55,070 vi inte malloc någon utrymme, och så vi är klara. 418 00:20:55,070 --> 00:20:57,590 Så denna funktion ram förstörs, och vi 419 00:20:57,590 --> 00:21:00,930 resume-- vi plocka upp där vi lämnade bort med nästa högsta, som 420 00:21:00,930 --> 00:21:02,807 är denna mörka blå ram här. 421 00:21:02,807 --> 00:21:04,390 Så vi plockar upp precis där vi slutade. 422 00:21:04,390 --> 00:21:06,598 Vi strök resten av listan redan, så nu är vi 423 00:21:06,598 --> 00:21:08,000 kommer att frigöra de aktuella noderna. 424 00:21:08,000 --> 00:21:12,920 Så nu kan vi frigöra denna nod, och nu Vi har kommit till slutet av funktionen. 425 00:21:12,920 --> 00:21:16,810 Och så denna funktion ram förstörs, och vi plocka upp på ljusblå ett. 426 00:21:16,810 --> 00:21:20,650 >> Så det says-- jag har redan done-- ta bort resten av listan, så 427 00:21:20,650 --> 00:21:23,140 frigöra den aktuella noden. 428 00:21:23,140 --> 00:21:26,520 Och nu den gula ramen är tillbaka på toppen av stacken. 429 00:21:26,520 --> 00:21:29,655 Och så som du ser, är vi nu förstöra listan från höger till vänster. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Vad skulle ha hänt, men Om vi ​​hade gjort saker på fel sätt? 432 00:21:37,280 --> 00:21:39,410 Precis som när vi försökte att lägga till ett element. 433 00:21:39,410 --> 00:21:41,909 Om vi ​​trasslat till kedjan, om vi inte koppla pekarna 434 00:21:41,909 --> 00:21:44,690 i rätt ordning, om vi just befriat det första elementet, 435 00:21:44,690 --> 00:21:47,420 om vi bara befriade av listan, nu vi 436 00:21:47,420 --> 00:21:49,642 har ingen möjlighet att hänvisa till resten av listan. 437 00:21:49,642 --> 00:21:51,350 Och så skulle vi ha föräldralösa allt, 438 00:21:51,350 --> 00:21:53,880 Vi skulle ha haft vad som är kallas en minnesläcka. 439 00:21:53,880 --> 00:21:56,800 Om ni minns från vår video på dynamisk minnesallokering, 440 00:21:56,800 --> 00:21:58,650 det är inte så bra. 441 00:21:58,650 --> 00:22:00,810 >> Så som sagt, det finns flera operationer 442 00:22:00,810 --> 00:22:04,010 att vi måste använda för att arbeta förteckning faktiskt samband. 443 00:22:04,010 --> 00:22:08,430 Och ni kanske har märkt jag utelämnat en, radera en enda element från en länkad 444 00:22:08,430 --> 00:22:09,064 listan. 445 00:22:09,064 --> 00:22:10,980 Anledningen till att jag gjorde det är det faktiskt typ av 446 00:22:10,980 --> 00:22:14,360 svårt att tänka på hur man tar bort en enda element från ett enskilt 447 00:22:14,360 --> 00:22:15,600 länkad lista. 448 00:22:15,600 --> 00:22:19,950 Vi måste kunna hoppa över något i listan, vilket 449 00:22:19,950 --> 00:22:22,975 innebär att vi får en point-- vi vill radera detta node-- 450 00:22:22,975 --> 00:22:25,350 men för att göra det så vi inte förlorar någon information, 451 00:22:25,350 --> 00:22:30,530 Vi måste ansluta denna nod hit, här. 452 00:22:30,530 --> 00:22:33,390 >> Så jag gjorde förmodligen är fel på det visuella planet. 453 00:22:33,390 --> 00:22:36,830 Så vi är i början av vår lista, vi fortsätter igenom, 454 00:22:36,830 --> 00:22:40,510 Vi vill ta bort denna nod. 455 00:22:40,510 --> 00:22:43,440 Om vi ​​bara ta bort det, Vi har brutit kedjan. 456 00:22:43,440 --> 00:22:45,950 Denna nod här hänvisar till allt annat, 457 00:22:45,950 --> 00:22:48,260 den innehåller kedjan från här på ut. 458 00:22:48,260 --> 00:22:51,190 >> Så vad vi behöver göra faktiskt när vi kommer till denna punkt, 459 00:22:51,190 --> 00:22:56,670 är att vi måste ta ett steg tillbaka ett och ansluta denna nod över till denna nod, 460 00:22:56,670 --> 00:22:58,590 så att vi kan sedan ta bort den i mitten. 461 00:22:58,590 --> 00:23:02,120 Men ensamma länkade listor inte ger oss ett sätt att gå bakåt. 462 00:23:02,120 --> 00:23:05,160 Så vi måste antingen behålla två pekare, och flytta dem 463 00:23:05,160 --> 00:23:09,527 sorts off steg, en bakom andra som vi går, eller komma till en punkt 464 00:23:09,527 --> 00:23:11,110 och sedan skicka en annan pekare igenom. 465 00:23:11,110 --> 00:23:13,150 Och som ni kan se, det kan bli lite rörigt. 466 00:23:13,150 --> 00:23:15,360 Lyckligtvis har vi ett annat sätt att lösa detta, 467 00:23:15,360 --> 00:23:17,810 när vi talar om dubbelt länkade listor. 468 00:23:17,810 --> 00:23:20,720 >> Jag är Doug Lloyd, är detta CS50. 469 00:23:20,720 --> 00:23:22,298