1 00:00:00,000 --> 00:00:02,832 >> [TÓNLIST spila] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, þannig að þetta atriði í námskeiðinu, 4 00:00:08,560 --> 00:00:15,300 við höfum fjallað mikið á grunnatriði C Við vitum mikið um breytur, fylki, 5 00:00:15,300 --> 00:00:17,610 ábendingum, allt sem gott efni. 6 00:00:17,610 --> 00:00:21,610 Þeir eru allir tegund af innbyggður til að sjá sem grundvallaratriði, 7 00:00:21,610 --> 00:00:23,880 en við getum gert meira, ekki satt? 8 00:00:23,880 --> 00:00:27,930 Við getum sameina hlutina saman á áhugaverðan hátt. 9 00:00:27,930 --> 00:00:31,010 >> Og svo við skulum gera það, við skulum byrja að útibú út um hvað C gefur okkur, 10 00:00:31,010 --> 00:00:35,270 og byrja að búa til eigin gögn okkar mannvirki sem nota þessar bygging 11 00:00:35,270 --> 00:00:40,590 blokkir saman til að gera eitthvað mjög mikilvægt, að gagni. 12 00:00:40,590 --> 00:00:43,420 Ein leið til að geta gert þetta er að tala um söfn. 13 00:00:43,420 --> 00:00:48,360 Svo svo langt að við höfum haft eina tegund af gögnum uppbygging fyrir hönd söfn 14 00:00:48,360 --> 00:00:51,030 af eins gildi, svipuð gildi. 15 00:00:51,030 --> 00:00:52,350 Það væri fylki. 16 00:00:52,350 --> 00:00:57,020 Við höfum söfn heiltölur eða söfn af stöfum og svo framvegis. 17 00:00:57,020 --> 00:01:00,890 >> Mannvirki eru einnig tegund af gögnum uppbygging til að safna upplýsingum, 18 00:01:00,890 --> 00:01:03,220 en það er ekki að safna eins gildum. 19 00:01:03,220 --> 00:01:08,090 Það blandar yfirleitt mismunandi gögn gerðir saman inni í einn kassa. 20 00:01:08,090 --> 00:01:10,750 En það er ekki sjálft er notað til að keðja saman 21 00:01:10,750 --> 00:01:16,920 eða tengja saman svipað atriði, eins og fylki. 22 00:01:16,920 --> 00:01:20,960 Fylki eru frábær fyrir þáttur líta upp, en muna 23 00:01:20,960 --> 00:01:24,262 að það er mjög erfitt að setja inn í array, 24 00:01:24,262 --> 00:01:26,470 nema við erum að setja á mjög lok þess array. 25 00:01:26,470 --> 00:01:29,730 >> Og besta dæmið sem ég hef fyrir því er innsetning tegund. 26 00:01:29,730 --> 00:01:31,650 Ef þú manst vídeó okkar á innsetningu tagi, 27 00:01:31,650 --> 00:01:34,110 það var mikið af kostnað þátt í að hafa 28 00:01:34,110 --> 00:01:37,970 að taka upp þætti, og skipta þeim út af leiðinni til að passa eitthvað 29 00:01:37,970 --> 00:01:41,290 í miðju fylkisins þinn. 30 00:01:41,290 --> 00:01:44,690 Fylki þjást einnig af öðru Vandamálið, sem er ósveigjanleika. 31 00:01:44,690 --> 00:01:47,150 Þegar við lýsa fylki, við fáum eitt skot á það. 32 00:01:47,150 --> 00:01:49,790 Við fáum að segja, ég vil þetta margir þættir. 33 00:01:49,790 --> 00:01:51,940 Gæti verið 100, gæti það vera 1.000, gæti það 34 00:01:51,940 --> 00:01:55,930 vera x þar sem x er tala sem notandinn gaf okkur á a hvetja eða á stjórn 35 00:01:55,930 --> 00:01:56,630 lína. 36 00:01:56,630 --> 00:01:59,905 >> En við fáum aðeins eitt skot á það, að við fæ ekki að þá segja ó, reyndar 37 00:01:59,905 --> 00:02:04,360 þarf 101, eða ég þurfti x plús 20. 38 00:02:04,360 --> 00:02:07,910 Of seint, við höfum nú þegar lýsti array, og ef við viljum fá 101 eða x 39 00:02:07,910 --> 00:02:12,050 auk 20, verðum við að lýsa algjörlega mismunandi array, 40 00:02:12,050 --> 00:02:15,540 afrita alla þætti array yfir, og þá höfum við nóg. 41 00:02:15,540 --> 00:02:19,880 Og hvað ef við erum rangt aftur, hvað ef við þurfum í raun 102 eða x plús 40, 42 00:02:19,880 --> 00:02:21,970 við verðum að gera þetta aftur. 43 00:02:21,970 --> 00:02:26,250 Svo þeir eru mjög ósveigjanleg fyrir resizing gögn okkar, 44 00:02:26,250 --> 00:02:29,360 en ef við sameina saman nokkrum grunnatriði sem við höfum nú þegar 45 00:02:29,360 --> 00:02:33,230 lært um ábendingum og mannvirki, einkum með dynamic minni 46 00:02:33,230 --> 00:02:36,180 úthlutun með malloc, við getur sett þessi stykki saman 47 00:02:36,180 --> 00:02:40,960 til að búa til ný gögn structure-- A eintengdan lista við gætum say-- 48 00:02:40,960 --> 00:02:45,400 sem gerir okkur kleift að vaxa og skreppa safn af gildum 49 00:02:45,400 --> 00:02:48,800 og við munum ekki hafa allir spara pláss. 50 00:02:48,800 --> 00:02:53,320 >> Svo aftur, við köllum þessa hugmynd, Þessi hugmynd, tengda listanum. 51 00:02:53,320 --> 00:02:56,320 Einkum í þessu myndbandi sem við erum að tala um stakar tengda listanum, 52 00:02:56,320 --> 00:02:59,185 og þá annað video sem við munum tala um tvöfalt tengd listum, sem 53 00:02:59,185 --> 00:03:01,560 er bara tilbrigði þema hér. 54 00:03:01,560 --> 00:03:05,200 En ein tengda listanum er samsett af hnúður, 55 00:03:05,200 --> 00:03:08,559 hnúður bara að vera ágrip term-- það er bara eitthvað sem ég er að hringja 56 00:03:08,559 --> 00:03:10,350 það er eins konar uppbyggingu, í grundvallaratriðum, ég? 57 00:03:10,350 --> 00:03:16,190 Bara að fara að kalla það node-- og þetta hnútur hefur tvo fulltrúa eða tveimur sviðum. 58 00:03:16,190 --> 00:03:20,300 Það hefur gögn, yfirleitt heiltala, persónu fljóta, 59 00:03:20,300 --> 00:03:23,790 eða gæti verið einhver önnur gögn tegund sem þú hefur skilgreint með gerð def. 60 00:03:23,790 --> 00:03:29,290 Og það inniheldur bendi annan hnút af sömu gerð. 61 00:03:29,290 --> 00:03:34,710 >> Þannig að við höfum tvennt inni þetta hnút, gögn og bendi 62 00:03:34,710 --> 00:03:36,380 til annars hnút. 63 00:03:36,380 --> 00:03:39,370 Og ef þú byrjar að sjón þetta, getur þú hugsa um það 64 00:03:39,370 --> 00:03:42,280 eins keðju hnúður sem eru tengdir saman. 65 00:03:42,280 --> 00:03:45,070 Við höfum í fyrsta hnút, það inniheldur gögn og bendi 66 00:03:45,070 --> 00:03:49,110 til seinni hnút, sem inniheldur gögn, og bendi á þriðja hnút. 67 00:03:49,110 --> 00:03:52,940 Og svo er það þess vegna sem við köllum það í tengda listanum, þeir tengdir saman. 68 00:03:52,940 --> 00:03:56,070 >> Hvað þýðir þetta sérstaka hnút uppbyggingu líta út? 69 00:03:56,070 --> 00:04:01,120 Jæja, ef þú manst frá vídeó okkar á skilgreina sérsniðna tegundir, með gerð def, 70 00:04:01,120 --> 00:04:05,400 getum við að skilgreina structure-- og slá skilgreina uppbyggingu svona. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, og þá er ég nota orðið gildi hér geðþótta 72 00:04:11,240 --> 00:04:13,891 að gefa til kynna hvaða gögn tegund í raun. 73 00:04:13,891 --> 00:04:16,890 Þú gætir fara á heiltala eða fljóta, þú gætir hafa það sem þú vilt. 74 00:04:16,890 --> 00:04:19,389 Það er ekki bundin við bara heiltölur, eða eitthvað svoleiðis. 75 00:04:19,389 --> 00:04:22,790 Svo er gildi bara handahófskennt gögn gerð, og þá bendi 76 00:04:22,790 --> 00:04:26,310 til annars hnút af sömu gerð. 77 00:04:26,310 --> 00:04:29,690 >> Nú, það er a lítill afli hér með að skilgreina uppbyggingu 78 00:04:29,690 --> 00:04:33,030 þegar það er sjálf vísun uppbyggingu. 79 00:04:33,030 --> 00:04:35,340 Ég verð að hafa tímabundið nafn fyrir uppbyggingu mína. 80 00:04:35,340 --> 00:04:37,640 Í lok dagsins I greinilega vilt kalla það 81 00:04:37,640 --> 00:04:43,030 SLL hnút, það er að lokum nýja nefna hluta af gerð skilgreiningu mína, 82 00:04:43,030 --> 00:04:47,450 en ég get ekki notað SLL hnút í miðju þessu. 83 00:04:47,450 --> 00:04:51,430 Ástæðan sé, ég hef ekki skapað tegund heitir SLL hnút 84 00:04:51,430 --> 00:04:55,200 þangað til ég lenti þessu endanlega lið hér. 85 00:04:55,200 --> 00:04:59,720 Fram að þeim tímapunkti, ég verð að hafa önnur leið til að vísa til þessa tegund gagna. 86 00:04:59,720 --> 00:05:02,440 >> Og þetta er sjálf vísun gögn tegund. 87 00:05:02,440 --> 00:05:06,314 Það; s a gögn tegund a mannvirki sem inniheldur gögn, 88 00:05:06,314 --> 00:05:08,480 og bendi til annars Uppbygging af sömu gerð. 89 00:05:08,480 --> 00:05:11,750 Þannig að ég þarf að vera fær um að vísa til þessi gögn tegund amk tímabundið, 90 00:05:11,750 --> 00:05:14,910 svo gefa það a tímabundinn nafn struct sllist 91 00:05:14,910 --> 00:05:18,540 leyfa mér að þá segja að ég vil að bendi á annan struct sllist, 92 00:05:18,540 --> 00:05:24,690 a struct sllist stjarna, og þá eftir að ég hef lokið við skilgreiningu, 93 00:05:24,690 --> 00:05:27,220 Ég get nú kalla þessa tegund er SLL hnút. 94 00:05:27,220 --> 00:05:30,520 >> Svo er það hvers vegna þú sérð að það er tímabundið nafn hér, 95 00:05:30,520 --> 00:05:31,879 en varanleg nafn hér. 96 00:05:31,879 --> 00:05:33,920 Stundum þú gætir séð skilgreiningar á uppbyggingu, 97 00:05:33,920 --> 00:05:36,570 til dæmis, sem eru ekki sjálf vísun, sem 98 00:05:36,570 --> 00:05:39,390 hafa ekki specifier nafn hér. 99 00:05:39,390 --> 00:05:43,040 Það myndi bara segja typedef strúktúr, opna hrokkið Brace og þá skilgreina það. 100 00:05:43,040 --> 00:05:45,620 En ef þú ert struct er sjálf vísun, sem þetta er, 101 00:05:45,620 --> 00:05:49,010 þú þarft að tilgreina a tímabundin tegund nafn. 102 00:05:49,010 --> 00:05:51,310 En að lokum, nú sem við höfum gert þetta, 103 00:05:51,310 --> 00:05:53,620 við getum bara átt við þessir hnútar, þessar einingar, 104 00:05:53,620 --> 00:05:57,900 sem SLL hnúður fyrir tilgangi af the hvíla af this vídeó. 105 00:05:57,900 --> 00:06:00,900 >> Allt í lagi, þannig að við vitum hvernig á að búa til tengda listanum hnút. 106 00:06:00,900 --> 00:06:03,240 Við vitum hvernig á að skilgreina tengda listanum hnút. 107 00:06:03,240 --> 00:06:06,670 Nú, ef við erum að fara að byrja nota þær til að safna upplýsingum, 108 00:06:06,670 --> 00:06:10,360 það er a par af rekstri við þurfa að skilja og vinna með. 109 00:06:10,360 --> 00:06:12,860 Við þurfum að vita hvernig á að búa til tengdur listi úr lausu lofti. 110 00:06:12,860 --> 00:06:14,901 Ef það er enginn listi þegar, Við viljum byrja einn. 111 00:06:14,901 --> 00:06:16,960 Þannig að við þurfum að vera fær um til að búa til tengdan lista, 112 00:06:16,960 --> 00:06:19,130 við þurfum að öllum líkindum að leita í gegnum tengilinn listann 113 00:06:19,130 --> 00:06:21,830 að finna stak við erum að leita að. 114 00:06:21,830 --> 00:06:24,430 Við þurfum að vera fær um að setja nýja hluti í listanum, 115 00:06:24,430 --> 00:06:25,930 við viljum lista okkar til að vera fær um að vaxa. 116 00:06:25,930 --> 00:06:28,638 Og sömuleiðis, við viljum vera fær um að eyða hlutum úr listanum okkar, 117 00:06:28,638 --> 00:06:30,250 við viljum lista okkar til að vera fær um að skreppa saman. 118 00:06:30,250 --> 00:06:32,160 Og í lok okkar forrit, sérstaklega 119 00:06:32,160 --> 00:06:34,550 ef þú manst að við erum virk úthluta minni 120 00:06:34,550 --> 00:06:38,337 til að byggja þessar listum yfirleitt, við viljum að losa öll þessi minni 121 00:06:38,337 --> 00:06:39,670 þegar við erum búin að vinna með það. 122 00:06:39,670 --> 00:06:44,627 Og svo þurfum við að vera fær um að eyða Allt tengda listanum í einu mistakast punda. 123 00:06:44,627 --> 00:06:46,460 Svo skulum við fara í gegnum sumir af þessum aðgerðum 124 00:06:46,460 --> 00:06:51,192 og hvernig við gætum sjón þá, tala í sauðakóðanum kóða sérstaklega. 125 00:06:51,192 --> 00:06:53,150 Þannig að við viljum búa til tengd lista, svo kannski við 126 00:06:53,150 --> 00:06:56,480 vilja til að skilgreina hlutverk með þessari frumgerð. 127 00:06:56,480 --> 00:07:01,690 SLL hnút stjarna, búa til, og ég er liggur í einni rifrildi, sumir handahófskennt gögn 128 00:07:01,690 --> 00:07:05,530 tegund aftur, einhvern handahófskenndan gögn tegund. 129 00:07:05,530 --> 00:07:10,482 En ég er returning-- þessa aðgerð ætti Hverf aftur til mín bendi til a ein 130 00:07:10,482 --> 00:07:11,190 tengda listanum hnút. 131 00:07:11,190 --> 00:07:14,050 Aftur erum við að reyna að búa til tengdur listi úr lausu lofti, 132 00:07:14,050 --> 00:07:17,900 þannig að ég þarf bendi þessi listi þegar ég er búin. 133 00:07:17,900 --> 00:07:19,420 >> Svo það eru skref sem taka þátt hér? 134 00:07:19,420 --> 00:07:20,960 Jæja, fyrsta sem ég að fara að gera er virk 135 00:07:20,960 --> 00:07:22,550 úthluta pláss fyrir nýja hnút. 136 00:07:22,550 --> 00:07:26,689 Aftur, við erum að búa það út af þunnt loft, þannig að við þurfum að malloc pláss fyrir það. 137 00:07:26,689 --> 00:07:28,480 Og auðvitað, strax eftir að við malloc, 138 00:07:28,480 --> 00:07:31,692 við athugum alltaf að ganga úr skugga um að okkar pointer-- við ekki fá til baka null. 139 00:07:31,692 --> 00:07:33,650 Vegna þess að ef við reynum og tillitssemi núll músina, 140 00:07:33,650 --> 00:07:36,190 við erum að fara að þjást segfault og við viljum ekki að. 141 00:07:36,190 --> 00:07:39,510 >> Þá viljum við fylla á sviði, við viljum að frumstilla gildi sviði 142 00:07:39,510 --> 00:07:41,690 og frumstilla næsta reit. 143 00:07:41,690 --> 00:07:45,450 Og þá viljum to-- lokum sem virka frumgerð indicates-- við viljum 144 00:07:45,450 --> 00:07:49,940 að skila bendi til SLL hnút. 145 00:07:49,940 --> 00:07:51,710 Svo hvað gera þetta líta út eins sjónrænt? 146 00:07:51,710 --> 00:07:55,230 Jæja, fyrst við erum að fara að virk úthluta pláss fyrir nýja SLL hnút, 147 00:07:55,230 --> 00:07:58,320 svo við malloc-- það er Myndræn 148 00:07:58,320 --> 00:08:00,020 hnútarins við bjuggum bara. 149 00:08:00,020 --> 00:08:02,757 Og við athuga til að tryggja það er ekki null-- í þessu tilfelli, 150 00:08:02,757 --> 00:08:04,840 myndin myndi ekki hafa sýnt upp ef það var null, 151 00:08:04,840 --> 00:08:07,298 við hefðum keyrt út af minni, þannig að við erum gott að fara þangað. 152 00:08:07,298 --> 00:08:10,200 Svo nú erum við á að stíga C, frumstillt hnúður gildi sviði. 153 00:08:10,200 --> 00:08:12,280 Jæja, byggt á þessari aðgerð kalla ég nota hér, 154 00:08:12,280 --> 00:08:16,700 lítur út eins og ég vil að fara í 6, Svo ég 6 í gildi sviði. 155 00:08:16,700 --> 00:08:18,865 Nú, frumstilla næsta reit. 156 00:08:18,865 --> 00:08:21,640 Jæja, hvað er ég að fara að gera það, það er ekkert næst, rétt, 157 00:08:21,640 --> 00:08:23,600 þetta er það eina sem á listanum. 158 00:08:23,600 --> 00:08:27,206 Svo er það næsta sem á listanum? 159 00:08:27,206 --> 00:08:29,660 >> Það ætti ekki að benda á neitt, ekki satt. 160 00:08:29,660 --> 00:08:33,600 Það er ekkert annað þarna, svo er það hugtakið sem við vitum af því er nothing-- 161 00:08:33,600 --> 00:08:35,638 ábendingum að engu? 162 00:08:35,638 --> 00:08:37,929 Það ætti að vera kannski að við viljum að setja núll músina þar, 163 00:08:37,929 --> 00:08:40,178 og ég ætla að tákna null bendillinn eins bara rauðan kassa, 164 00:08:40,178 --> 00:08:41,559 við getum ekki farið lengra. 165 00:08:41,559 --> 00:08:44,430 Eins og við munum sjá smá seinna, munum við hafa að lokum keðjur 166 00:08:44,430 --> 00:08:46,330 örvum tengja þessir hnútar saman, 167 00:08:46,330 --> 00:08:48,480 en þegar þú högg the rauður kassi, það er null, 168 00:08:48,480 --> 00:08:51,150 við getum ekki farið lengra, það er enda á listanum. 169 00:08:51,150 --> 00:08:53,960 >> Og loks, við viljum bara að aftur bendi þessum hnút. 170 00:08:53,960 --> 00:08:56,160 Þannig að við munum kalla hann nýjan, og mun skila nýja 171 00:08:56,160 --> 00:08:59,370 svo það er hægt að nota í hvað virka skapaði það. 172 00:08:59,370 --> 00:09:03,100 Þannig að það sem við förum, við höfum sett ein tengda listanum hnút úr lausu lofti, 173 00:09:03,100 --> 00:09:05,920 og nú erum við með lista sem við getum unnið með. 174 00:09:05,920 --> 00:09:08,260 >> Nú, við skulum segja að við nú þegar hafa stóra keðju 175 00:09:08,260 --> 00:09:09,800 og við viljum að finna eitthvað í það. 176 00:09:09,800 --> 00:09:12,716 Og við viljum að aðgerð sem er að fara til að fara aftur satt eða ósatt, fer 177 00:09:12,716 --> 00:09:15,840 um hvort gildi er í þeim lista. 178 00:09:15,840 --> 00:09:18,160 Fall frumgerð, eða Yfirlýsing fyrir að virka, 179 00:09:18,160 --> 00:09:23,320 gæti litið út this-- bool finna, og þá viljum við fara í tveimur rök. 180 00:09:23,320 --> 00:09:26,996 >> Sú fyrsta, er bendi til Fyrsta þáttur í tengda listanum. 181 00:09:26,996 --> 00:09:29,620 Þetta er í raun eitthvað sem þú munt alltaf vilja til að halda utan um, 182 00:09:29,620 --> 00:09:33,110 og í raun gæti verið eitthvað sem þú setur jafnvel í alþjóðlegum breytu. 183 00:09:33,110 --> 00:09:35,360 Þegar þú býrð til lista, alltaf, alltaf 184 00:09:35,360 --> 00:09:38,990 langar að halda utan um það Fyrsti þátturinn af listanum. 185 00:09:38,990 --> 00:09:43,690 Þannig að þú getur átt við allar aðrar þættir með bara eftir keðju, 186 00:09:43,690 --> 00:09:47,300 án þess að þurfa að halda ábendingum ósnortinn hverjum einasta frumefni. 187 00:09:47,300 --> 00:09:50,920 Þú þarft aðeins að halda utan um fyrsta einn ef þeir eru allir handjárnaða saman. 188 00:09:50,920 --> 00:09:52,460 >> Og þá seinni sem við erum liggur aftur 189 00:09:52,460 --> 00:09:54,376 er geðþótta some-- hvað gögn tegund við erum 190 00:09:54,376 --> 00:09:59,640 að leita að þar er inni vonandi einn af hnúður á listanum. 191 00:09:59,640 --> 00:10:00,980 Svo það eru skref? 192 00:10:00,980 --> 00:10:04,250 Jæja, það fyrsta sem við gerum er við að búa til þversum músina 193 00:10:04,250 --> 00:10:06,015 benda til minnislista höfuð. 194 00:10:06,015 --> 00:10:08,890 Jæja, hvers vegna eigum við að gera það, sem við nú þegar hafa músina á listum höfuð, 195 00:10:08,890 --> 00:10:10,974 Hvers vegna eigum við ekki að fara bara að einn í kring? 196 00:10:10,974 --> 00:10:13,140 Jæja, eins og ég sagði bara, það er mjög mikilvægt fyrir okkur 197 00:10:13,140 --> 00:10:17,580 að alltaf að halda utan um Fyrsti þáttur í listanum. 198 00:10:17,580 --> 00:10:21,270 Og svo er það í raun betra til að búa til afrit af því, 199 00:10:21,270 --> 00:10:25,350 og nota það til að færa sig svo við aldrei óvart flytja í burtu, eða við alltaf 200 00:10:25,350 --> 00:10:30,430 hafa músina á einhverjum tímapunkti sem er rétt á fyrstu frumefni á listanum. 201 00:10:30,430 --> 00:10:33,290 Svo það er betra að búa til seinni sem við notum til að hreyfa. 202 00:10:33,290 --> 00:10:35,877 >> Þá erum við saman bara hvort gildi sviði í hnút 203 00:10:35,877 --> 00:10:38,960 er það sem við erum að leita að, og ef það er ekki, hreyfa við bara í næsta hnút. 204 00:10:38,960 --> 00:10:41,040 Og við höldum að gera það yfir, og aftur, og aftur, 205 00:10:41,040 --> 00:10:44,811 þar til við annað hvort að finna þáttur, eða við högg 206 00:10:44,811 --> 00:10:47,310 null-- við höfum náð enda af listanum og það er ekki þar. 207 00:10:47,310 --> 00:10:50,540 Þetta ætti vonandi hringja bjöllu til þín sem bara línuleg leit, 208 00:10:50,540 --> 00:10:54,430 við erum bara afrit það í eintengdan lista uppbygging 209 00:10:54,430 --> 00:10:56,280 í stað þess að nota array að gera það. 210 00:10:56,280 --> 00:10:58,210 >> Svo er hér dæmi um eintengdan lista. 211 00:10:58,210 --> 00:11:00,043 Þetta eitt samanstendur af fimm hnúta, og við höfum 212 00:11:00,043 --> 00:11:04,330 bendi á höfuð hins lista, sem heitir lista. 213 00:11:04,330 --> 00:11:07,385 The fyrstur hlutur sem við viljum gera er að aftur, búa til að Traversal músina. 214 00:11:07,385 --> 00:11:09,760 Þannig að við höfum nú tvær ábendingum sem benda til það sama. 215 00:11:09,760 --> 00:11:15,025 >> Nú, eftir hingað, ég gerði ekki að malloc allir pláss fyrir Trav. 216 00:11:15,025 --> 00:11:18,970 Ég sagði ekki Trav jafngildir malloc eitthvað, sem hnút þegar til, 217 00:11:18,970 --> 00:11:21,160 sem pláss í minni er þegar til. 218 00:11:21,160 --> 00:11:24,290 Svo er allt sem ég er í raun að gera búa til annað músina til þess. 219 00:11:24,290 --> 00:11:28,210 Ég er ekki að mallocing til viðbótar rúm, bara nú tvær ábendingum 220 00:11:28,210 --> 00:11:31,370 benda til það sama. 221 00:11:31,370 --> 00:11:33,710 >> Svo er 2 sem ég er að leita að? 222 00:11:33,710 --> 00:11:37,220 Jæja, nei, þannig að í stað ég er að fara að flytja til the næstur einn. 223 00:11:37,220 --> 00:11:41,740 Svo í rauninni ég myndi segja, Trav jafngildir Trav næst. 224 00:11:41,740 --> 00:11:43,630 Er 3 það sem ég er að leita að nr. 225 00:11:43,630 --> 00:11:45,780 Svo ég held áfram að fara í gegnum, þar til að lokum 226 00:11:45,780 --> 00:11:48,690 fá til 6 sem er það sem ég er að leita fyrir miðað við virka símtalinu 227 00:11:48,690 --> 00:11:51,600 Ég hef efst þar, og svo ég er búin. 228 00:11:51,600 --> 00:11:54,150 >> Nú, hvað ef þátturinn ég að leita að er ekki á listanum, 229 00:11:54,150 --> 00:11:55,510 er það að fara enn að vinna? 230 00:11:55,510 --> 00:11:57,120 Jæja, eftir að listinn hér er subtly mismunandi, 231 00:11:57,120 --> 00:11:59,410 og þetta er annar hlutur sem er mikilvægt við tengd listum, 232 00:11:59,410 --> 00:12:01,780 þú þarft ekki að varðveita þá í einhverju tilteknu skyni. 233 00:12:01,780 --> 00:12:05,390 Þú getur ef þú vilt, en þú kannt að hafa þegar tekið 234 00:12:05,390 --> 00:12:09,310 að við erum ekki að halda utan um hvað fjölda þáttur sem við erum á. 235 00:12:09,310 --> 00:12:13,150 >> Og það er tegund af einum viðskiptum sem við hafa með tengda listanum vísur fylki, 236 00:12:13,150 --> 00:12:15,300 er það að við höfum ekki handahófi aðgang lengur. 237 00:12:15,300 --> 00:12:18,150 Við getum ekki bara segja, ég vil að fara í 0th frumefni, 238 00:12:18,150 --> 00:12:21,410 eða 6 þáttur array minn, sem ég get gert í fylki. 239 00:12:21,410 --> 00:12:25,080 Ég get ekki sagt að ég vil fara til 0 þáttur, eða 6 þáttur, 240 00:12:25,080 --> 00:12:30,360 eða 25 þáttur tengda listanum mínum, það er engin Vísitala tengslum við þá. 241 00:12:30,360 --> 00:12:33,660 Og svo það skiptir ekki máli ef við varðveita lista okkar í röð. 242 00:12:33,660 --> 00:12:36,080 Ef þú vilt að þér vissulega getur, en það er 243 00:12:36,080 --> 00:12:38,567 engin ástæða fyrir því að þeir þurfa að varðveitist í hvaða röð. 244 00:12:38,567 --> 00:12:40,400 Svo aftur, við skulum reyna að finna 6 í þessum lista. 245 00:12:40,400 --> 00:12:43,200 Jæja, byrjum við á að farin, finnum við ekki 6, 246 00:12:43,200 --> 00:12:47,690 og þá erum við að halda áfram að finna 6, þar til við fáum loksins að hér. 247 00:12:47,690 --> 00:12:52,790 Svo núna Trav stig til hnút inniheldur 8 og sex er ekki þar. 248 00:12:52,790 --> 00:12:55,250 >> Þannig að næsta skref væri til að fara á næsta músina, 249 00:12:55,250 --> 00:12:57,440 svo segja trav jafngildir Trav næst. 250 00:12:57,440 --> 00:13:00,750 Jæja, Trav næsta, táknuð með rauða kassi það er null. 251 00:13:00,750 --> 00:13:03,020 Þannig að það er hvergi annars staðar að fara, og svo á þessum tímapunkti 252 00:13:03,020 --> 00:13:06,120 við getum gert það sem við höfum náð the endir af the tengda listanum, 253 00:13:06,120 --> 00:13:07,190 og 6 er ekki þar. 254 00:13:07,190 --> 00:13:10,980 Og það væri aftur rangar í þessu tilfelli. 255 00:13:10,980 --> 00:13:14,540 >> OK, hvernig eigum við að setja nýtt hnút í tengda listanum? 256 00:13:14,540 --> 00:13:17,310 Þannig að við höfum getað til að búa til tengdur listi út af hvergi, 257 00:13:17,310 --> 00:13:19,370 en við viljum líklega að byggja upp keðju og ekki 258 00:13:19,370 --> 00:13:22,620 búa til fullt af mismunandi listum. 259 00:13:22,620 --> 00:13:25,700 Við viljum hafa einn lista sem hefur fullt af hnúður í það, 260 00:13:25,700 --> 00:13:28,040 ekki fullt af listum með einum hnút. 261 00:13:28,040 --> 00:13:31,260 Þannig að við getum ekki bara haldið áfram að nota Búa virka við skilgreint fyrr, nú erum við 262 00:13:31,260 --> 00:13:33,860 langar að setja inn a listi sem er þegar til. 263 00:13:33,860 --> 00:13:36,499 >> Svo þessu tilfelli erum við að fara að fara í tvær breytur, 264 00:13:36,499 --> 00:13:39,290 bendillinn höfuð sem tengd lista sem við viljum bæta við. 265 00:13:39,290 --> 00:13:40,910 Aftur, það er hvers vegna það er svo mikilvægt að við alltaf 266 00:13:40,910 --> 00:13:43,400 halda utan um það, vegna þess að það er eina leiðin sem við raunverulega 267 00:13:43,400 --> 00:13:46,690 að vísa til allt listi er bara með því að bendi á fyrstu frumefni. 268 00:13:46,690 --> 00:13:49,360 Þannig að við viljum fara í bendi á að fyrsta frumefni, 269 00:13:49,360 --> 00:13:52,226 og hvað sem gildi vér langar að bæta við listann. 270 00:13:52,226 --> 00:13:54,600 Og að lokum þessi aðgerð er að fara að skila bendi 271 00:13:54,600 --> 00:13:57,980 að nýr yfirmaður tengda listanum. 272 00:13:57,980 --> 00:13:59,700 >> Hvaða skref sem taka þátt hér? 273 00:13:59,700 --> 00:14:02,249 Jæja, bara eins og með að búa, við þurfum að virk úthluta 274 00:14:02,249 --> 00:14:05,540 pláss fyrir nýja hnút, og þess viss um að við keyri ekki út af minni, aftur, 275 00:14:05,540 --> 00:14:07,150 vegna þess að við erum að nota malloc. 276 00:14:07,150 --> 00:14:09,080 Þá viljum við byggja og settu hnút, 277 00:14:09,080 --> 00:14:12,730 svo setja fjölda, hvað Val er í hnút. 278 00:14:12,730 --> 00:14:17,310 Við viljum að setja hnút á upphaf tengda listanum. 279 00:14:17,310 --> 00:14:19,619 >> Það er ástæðan fyrir því að ég langar að gera þetta, og það 280 00:14:19,619 --> 00:14:21,910 gæti verið þess virði að taka annað að gera hlé á vídeó hér, 281 00:14:21,910 --> 00:14:25,860 og hugsa um hvers vegna ég myndi vilja setja í upphafi tengdur 282 00:14:25,860 --> 00:14:26,589 lista. 283 00:14:26,589 --> 00:14:28,630 Aftur, ég nefndi áðan að það er í raun ekki 284 00:14:28,630 --> 00:14:33,020 máli hvort við varðveita það í hvaða röð, svo kannski er það vísbending. 285 00:14:33,020 --> 00:14:36,040 Og þú sást hvað myndi gerast ef við vildi to-- eða bara annað 286 00:14:36,040 --> 00:14:37,360 síðan þegar við vorum að fara gegnum leit þú 287 00:14:37,360 --> 00:14:39,235 gat séð hvað gæti gerast ef við vorum að reyna 288 00:14:39,235 --> 00:14:41,330 til að setja í lok listanum. 289 00:14:41,330 --> 00:14:44,750 Þar sem við höfum ekki bendillinn til loka listanum. 290 00:14:44,750 --> 00:14:47,490 >> Svo ástæða þess að ég myndi vilja til að setja í upphafi, 291 00:14:47,490 --> 00:14:49,380 er vegna þess að ég get gert það strax. 292 00:14:49,380 --> 00:14:52,730 Ég er með músina í upphafi, og við munum sjá þetta í sjón í annað. 293 00:14:52,730 --> 00:14:55,605 En ef ég vil setja í lokin, Ég verð að byrja á byrjun, 294 00:14:55,605 --> 00:14:58,760 fara yfir alla leið til enda, og þá tittur á því. 295 00:14:58,760 --> 00:15:01,420 Svo sem myndi þýða að að setja í lok listanum 296 00:15:01,420 --> 00:15:04,140 myndi verða eða n rekstur, að fara aftur 297 00:15:04,140 --> 00:15:06,720 að umfjöllun okkar um computational flókið. 298 00:15:06,720 --> 00:15:10,140 Það myndi verða eða af n rekstri, þar sem listinn fékk stærri og stærri, 299 00:15:10,140 --> 00:15:13,310 og stærri, verður það verða fleiri og erfiðara að tittur eitthvað 300 00:15:13,310 --> 00:15:14,661 á í lokin. 301 00:15:14,661 --> 00:15:17,410 En það er alltaf mjög auðvelt að tittur eitthvað á í upphafi, 302 00:15:17,410 --> 00:15:19,060 þú ert alltaf í upphafi. 303 00:15:19,060 --> 00:15:21,620 >> Og við munum sjá sjón af þessu aftur. 304 00:15:21,620 --> 00:15:24,100 Og þá þegar við erum búin, einu sinni við höfum sett nýja hnút, 305 00:15:24,100 --> 00:15:26,880 við viljum aftur bendi okkar til nýr yfirmaður tengda listanum, sem 306 00:15:26,880 --> 00:15:29,213 þar sem við erum að setja á the farin, mun reyndar vera 307 00:15:29,213 --> 00:15:31,060 bendi á hnút við að búa til. 308 00:15:31,060 --> 00:15:33,280 Skulum sjón þetta, vegna þess að ég held að það mun hjálpa. 309 00:15:33,280 --> 00:15:36,661 >> Svo er hér listi okkar, samanstendur það af fjórir þættir, hnút inniheldur 15, 310 00:15:36,661 --> 00:15:38,410 sem bendir til hnút sem inniheldur 9, þar sem 311 00:15:38,410 --> 00:15:41,370 bendir til hnút inniheldur 13, sem bendir til hnút inniheldur 312 00:15:41,370 --> 00:15:44,840 10, sem hefur núll bendillinn eins næsta bendillinn birtist 313 00:15:44,840 --> 00:15:47,010 svo er að í lok listanum. 314 00:15:47,010 --> 00:15:50,200 Þannig að við viljum að setja a Ný hnút með gildi 12 315 00:15:50,200 --> 00:15:52,720 í upphafi þessa lista, hvað gerum við? 316 00:15:52,720 --> 00:15:58,770 Jæja, fyrst við malloc pláss fyrir hnút, og þá erum við að setja 12 í það. 317 00:15:58,770 --> 00:16:02,211 >> Svo nú höfum við náð Ákvörðun lið, ekki satt? 318 00:16:02,211 --> 00:16:03,960 Við hafa a par af ábendingar sem við gátum 319 00:16:03,960 --> 00:16:06,770 færa, sem maður á að við fara fyrst? 320 00:16:06,770 --> 00:16:09,250 Ættum við að gera 12 stig til nýr yfirmaður list-- 321 00:16:09,250 --> 00:16:13,020 eða afsakið, ættum við að gera 12 benda á gamla höfuð listanum? 322 00:16:13,020 --> 00:16:15,319 Eða ættum við að segja að Listinn hefst nú á 12. 323 00:16:15,319 --> 00:16:17,110 Það er greinarmunur þar, og við munum líta 324 00:16:17,110 --> 00:16:19,870 á hvað gerist með bæði í annað. 325 00:16:19,870 --> 00:16:23,350 >> En þetta leiðir til a mikill efni fyrir skenkur, 326 00:16:23,350 --> 00:16:26,280 sem er að ein af erfiðustu hluti með tengd listum 327 00:16:26,280 --> 00:16:30,980 er að raða ábendingum í réttri röð. 328 00:16:30,980 --> 00:16:34,520 Ef þú færir fram úr röð, þú getur endað óvart 329 00:16:34,520 --> 00:16:36,050 orphaning restina af listanum. 330 00:16:36,050 --> 00:16:37,300 Og hér er dæmi um það. 331 00:16:37,300 --> 00:16:40,540 Svo skulum við fara með þá hugmynd of-- jæja við höfum bara búið 12. 332 00:16:40,540 --> 00:16:43,180 Við vitum 12 er að fara að vera nýr yfirmaður lista, 333 00:16:43,180 --> 00:16:47,660 og svo hvers vegna eigum við ekki að fara bara listi bendillinn að benda þar. 334 00:16:47,660 --> 00:16:49,070 >> OK, svo er það gott. 335 00:16:49,070 --> 00:16:51,560 Svo nú hvar 12 næsta lið? 336 00:16:51,560 --> 00:16:54,580 Ég meina, sjónrænt getum við séð að það muni benda til 15, 337 00:16:54,580 --> 00:16:57,250 eins og menn það er mjög augljóst að okkur. 338 00:16:57,250 --> 00:17:00,300 Hvernig virkar tölva veit? 339 00:17:00,300 --> 00:17:02,720 Við höfum ekki neitt benda til 15 lengur, ekki satt? 340 00:17:02,720 --> 00:17:05,869 >> Við höfum misst neina getu til að vísa til 15. 341 00:17:05,869 --> 00:17:11,460 Við getum ekki sagt nýtt örina við hliðina jafn eitthvað, það er ekkert þar. 342 00:17:11,460 --> 00:17:13,510 Í raun höfum við munaðarlaus restin af listanum 343 00:17:13,510 --> 00:17:16,465 með því að gera það, höfum við óvart brotið keðju. 344 00:17:16,465 --> 00:17:18,089 Og við vissulega vil ekki að gera það. 345 00:17:18,089 --> 00:17:20,000 >> Svo við skulum fara aftur og reyna þetta aftur. 346 00:17:20,000 --> 00:17:24,060 Kannski rétt að gera er að setja næstu músina 12 er 347 00:17:24,060 --> 00:17:28,290 að gamla höfuð listanum fyrsta, þá getum við flutt listann yfir. 348 00:17:28,290 --> 00:17:30,420 Og í raun, það er rétt til þess að vér 349 00:17:30,420 --> 00:17:32,836 þarf að fylgja þegar við erum vinna með stakar tengda listanum. 350 00:17:32,836 --> 00:17:36,460 Við viljum alltaf að tengja Ný þáttur í listanum, 351 00:17:36,460 --> 00:17:41,010 áður en við förum svona mikilvægt skref í að breyta 352 00:17:41,010 --> 00:17:43,360 þar sem yfirmaður tengda listanum er. 353 00:17:43,360 --> 00:17:46,740 Aftur, það er svo grundvallaratriði hlutur, við viljum ekki að missa utan um það. 354 00:17:46,740 --> 00:17:49,310 >> Þannig að við viljum tryggja að allt er hlekkjaður saman, 355 00:17:49,310 --> 00:17:52,040 áður en við fara að bendilinn. 356 00:17:52,040 --> 00:17:55,300 Og svo þetta væri rétta röð, sem er að tengja 12 á listann, 357 00:17:55,300 --> 00:17:57,630 þá segja að listinn byrjar 12. 358 00:17:57,630 --> 00:18:00,860 Ef við sagði listinn byrjar á 12 og þá reynt að tengja 12 á listann, 359 00:18:00,860 --> 00:18:02,193 við höfum þegar séð hvað gerist. 360 00:18:02,193 --> 00:18:04,920 Við missa listann mistök. 361 00:18:04,920 --> 00:18:06,740 >> OK, svo eitt í viðbót til að tala um. 362 00:18:06,740 --> 00:18:09,750 Hvað ef við viljum losna við heilt tengd lista í einu? 363 00:18:09,750 --> 00:18:11,750 Aftur, við erum mallocing allt þetta pláss, og svo við 364 00:18:11,750 --> 00:18:13,351 þarf að losa það þegar við erum búin. 365 00:18:13,351 --> 00:18:15,350 Svo nú viljum við að eyða allt tengda listanum. 366 00:18:15,350 --> 00:18:16,850 Jæja, hvað viljum við gera? 367 00:18:16,850 --> 00:18:20,460 >> Ef við höfum náð núll músina, við vilt hætta, annars, bara eyða 368 00:18:20,460 --> 00:18:23,420 restin af listanum og síðan losa mig. 369 00:18:23,420 --> 00:18:28,890 Eyða restinni af listanum, og þá losa núverandi hnút. 370 00:18:28,890 --> 00:18:32,850 Hvað gerir þessi hljóð eins, hvað tækni höfum við ræddum 371 00:18:32,850 --> 00:18:35,440 um áður Hefur þessi hljóð eins? 372 00:18:35,440 --> 00:18:39,560 Eyða allir aðrir, þá koma aftur og eyða mér. 373 00:18:39,560 --> 00:18:42,380 >> Það er endurkvæmni, höfum við gert Vandamálið svolítið minni, 374 00:18:42,380 --> 00:18:46,910 við erum að segja að eyða allir annars, þá er hægt að eyða mér. 375 00:18:46,910 --> 00:18:50,940 Og lengra niður veginn, sem hnút mun segja, eyða og allir aðrir. 376 00:18:50,940 --> 00:18:53,940 En að lokum munum við fá til the málið þar sem listinn er null, 377 00:18:53,940 --> 00:18:55,310 og það er undirstaða málið okkar. 378 00:18:55,310 --> 00:18:57,010 >> Svo skulum taka a líta á þetta, og hvernig þetta gæti virkað. 379 00:18:57,010 --> 00:18:59,759 Svo er hér listi okkar, það er sama listi við vorum bara að tala um, 380 00:18:59,759 --> 00:19:00,980 og það er skref. 381 00:19:00,980 --> 00:19:04,200 There 'a einhver fjöldi af texta hér, en vonandi visualization mun hjálpa. 382 00:19:04,200 --> 00:19:08,557 >> Þannig að við have-- og ég dró líka upp stafla ramma okkar dæmi 383 00:19:08,557 --> 00:19:10,890 frá vídeó okkar á vakt stafla, og vonandi allt þetta 384 00:19:10,890 --> 00:19:13,260 saman mun sýna þér hvað er að gerast. 385 00:19:13,260 --> 00:19:14,510 Svo hér sauðakóðanum númerið okkar. 386 00:19:14,510 --> 00:19:17,830 Ef við náum null músina, stöðva, annars, 387 00:19:17,830 --> 00:19:21,320 eyða restinni af listanum, þá frjáls núverandi hnút. 388 00:19:21,320 --> 00:19:25,700 Svo núna, list-- bendillinn að við erum 389 00:19:25,700 --> 00:19:28,410 liggur í að eyða stig til 12. 390 00:19:28,410 --> 00:19:33,340 12 er ekki null músina, þannig að við erum að fara að eyða restina af listanum. 391 00:19:33,340 --> 00:19:35,450 >> Hvað er að eyða restin af okkur að ræða? 392 00:19:35,450 --> 00:19:37,950 Jæja, það þýðir að a kalla að eyðileggja, segja 393 00:19:37,950 --> 00:19:42,060 að 15 er upphaf af restin af listanum sem við viljum eyða. 394 00:19:42,060 --> 00:19:47,480 Og svo hringt til að eyða 12 er góður af á bið. 395 00:19:47,480 --> 00:19:52,690 Það er fryst þar, bíða eftir kalla að eyða 15, til að ljúka starfi sínu. 396 00:19:52,690 --> 00:19:56,280 >> Jæja, 15 er ekki null músina, og svo það er að fara að segja, allt í lagi, 397 00:19:56,280 --> 00:19:58,450 vel, eyða restina af listanum. 398 00:19:58,450 --> 00:20:00,760 The hvíla af listanum byrjar á 9, og svo við verðum bara 399 00:20:00,760 --> 00:20:04,514 bíddu þar til þú eyðir öllu sem efni, þá komið aftur og eyða mér. 400 00:20:04,514 --> 00:20:06,680 Jæja 9 er að fara að segja, vel, Ég er ekki null músina, 401 00:20:06,680 --> 00:20:09,020 svo eyða hinum listanum hér. 402 00:20:09,020 --> 00:20:11,805 Og svo reyna og eyðileggja 13. 403 00:20:11,805 --> 00:20:15,550 13 segir, ég er ekki null músina, sama, fer það peninginn. 404 00:20:15,550 --> 00:20:17,930 10 er ekki null músina, 10 inniheldur núll músina, 405 00:20:17,930 --> 00:20:20,200 en 10 er ekki sjálf null músina núna, 406 00:20:20,200 --> 00:20:22,470 og svo fer það peninginn líka. 407 00:20:22,470 --> 00:20:25,560 >> Og nú lista stig þar, það virkilega myndi benda til some-- 408 00:20:25,560 --> 00:20:28,710 ef ég hefði meira pláss í myndinni, það myndi benda til sumir af handahófi rúm 409 00:20:28,710 --> 00:20:29,960 að við vitum ekki hvað það er. 410 00:20:29,960 --> 00:20:34,680 Það er null bendillinn þó listi er bókstaflega nú sett það gildi null. 411 00:20:34,680 --> 00:20:36,820 Það er að benda beint í þeirri rauðum kassa. 412 00:20:36,820 --> 00:20:39,960 Við náð núll músina, svo við getum hætt, og við erum að gera. 413 00:20:39,960 --> 00:20:46,230 >> Og svo er að fjólublátt ramma now-- minnsta Efst á stack-- það er virka ramma, 414 00:20:46,230 --> 00:20:47,017 en það er gert. 415 00:20:47,017 --> 00:20:48,600 Ef við höfum náð núll músina, hætta. 416 00:20:48,600 --> 00:20:51,290 Við gerum ekki neitt, við getur ekki frjáls núll músina, 417 00:20:51,290 --> 00:20:55,070 við vissum ekki malloc eitthvað rúm, og svo við erum að gera. 418 00:20:55,070 --> 00:20:57,590 Þannig að hlutverk ramma er eytt, og við 419 00:20:57,590 --> 00:21:00,930 resume-- við taka upp þar sem við var burt með næsthæsta einn, sem 420 00:21:00,930 --> 00:21:02,807 er þetta dökk blár rammi hér. 421 00:21:02,807 --> 00:21:04,390 Þannig að við taka upp hægri þar sem við var horfið. 422 00:21:04,390 --> 00:21:06,598 Við eytt restina af Listinn þegar, svo nú erum við 423 00:21:06,598 --> 00:21:08,000 að fara að losa núverandi hnúta. 424 00:21:08,000 --> 00:21:12,920 Svo nú getum við frjáls þennan hnút, og nú við höfum náð enda fallsins. 425 00:21:12,920 --> 00:21:16,810 Og þannig að hlutverk ramma er eytt, og við tekið upp á ljósbláu einn. 426 00:21:16,810 --> 00:21:20,650 >> Svo það says-- ég hef þegar done-- eyða restina af listanum, svo 427 00:21:20,650 --> 00:21:23,140 frjáls núverandi hnút. 428 00:21:23,140 --> 00:21:26,520 Og nú er gulur ramma aftur ofan á stafla. 429 00:21:26,520 --> 00:21:29,655 Og svo eins og þú sérð, við erum nú eyðileggja listann frá hægri til vinstri. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Hvað hefði gerst, þó, ef við hefðum gert hlutina á rangan hátt? 432 00:21:37,280 --> 00:21:39,410 Rétt eins og þegar við reyndum að bæta þáttur. 433 00:21:39,410 --> 00:21:41,909 Ef við boðberi upp keðju, ef við vissum ekki tengja ábendingum 434 00:21:41,909 --> 00:21:44,690 í réttri röð, ef við bara leysti fyrsta þáttur, 435 00:21:44,690 --> 00:21:47,420 ef við leystur bara yfirmaður lista, nú erum við 436 00:21:47,420 --> 00:21:49,642 hafa enga leið til að vísa til restin af listanum. 437 00:21:49,642 --> 00:21:51,350 Og svo við hefðum munaðarlaus allt, 438 00:21:51,350 --> 00:21:53,880 við hefðum haft það sé kallað minni leka. 439 00:21:53,880 --> 00:21:56,800 Ef þú manst frá vídeó okkar á dynamic minni úthlutun, 440 00:21:56,800 --> 00:21:58,650 það er ekki mjög gott. 441 00:21:58,650 --> 00:22:00,810 >> Svo eins og ég sagði, það eru nokkrir aðgerðir 442 00:22:00,810 --> 00:22:04,010 sem við þurfum að nota til að vinna með tengda listanum raun. 443 00:22:04,010 --> 00:22:08,430 Og þú gætir hafa tekið eftir að ég sleppt einn, eyða einn þáttur frá tengdur 444 00:22:08,430 --> 00:22:09,064 lista. 445 00:22:09,064 --> 00:22:10,980 Ástæðan ég gerði það er að það er í raun eins konar 446 00:22:10,980 --> 00:22:14,360 erfiður að hugsa um hvernig á að eyða einn þáttur frá a ein 447 00:22:14,360 --> 00:22:15,600 tengda listanum. 448 00:22:15,600 --> 00:22:19,950 Við þurfum að vera fær um að sleppa yfir eitthvað á listanum, sem 449 00:22:19,950 --> 00:22:22,975 þýðir að við fá að point-- vér viljir eyða þessari node-- 450 00:22:22,975 --> 00:22:25,350 en í því skyni að gera það svo við missir ekki neinar upplýsingar, 451 00:22:25,350 --> 00:22:30,530 við þurfum að tengja þetta hnút hérna, hér. 452 00:22:30,530 --> 00:22:33,390 >> Svo ég gerði líklega að rangt frá sjón sjónarhorni. 453 00:22:33,390 --> 00:22:36,830 Þannig að við erum í upphafi okkar lista, við erum áfram í gegnum, 454 00:22:36,830 --> 00:22:40,510 við viljum eyða þennan hnút. 455 00:22:40,510 --> 00:22:43,440 Ef við eyða bara það, við höfum brotið keðju. 456 00:22:43,440 --> 00:22:45,950 Þetta hnút hérna er átt við allt annað, 457 00:22:45,950 --> 00:22:48,260 það inniheldur keðja frá hér á út. 458 00:22:48,260 --> 00:22:51,190 >> Svo það sem við þurfum að gera í raun og veru eftir að við fáum að þessum tímapunkti, 459 00:22:51,190 --> 00:22:56,670 er að við þurfum að stíga til baka einn, og tengja þennan hnút yfir þessari hnút, 460 00:22:56,670 --> 00:22:58,590 svo við getum þá eytt einn í miðju. 461 00:22:58,590 --> 00:23:02,120 En ein tengd listum ekki veita okkur leið til að fara aftur á bak. 462 00:23:02,120 --> 00:23:05,160 Þannig að við þurfum að annaðhvort halda tveir ábendingum og færa þau 463 00:23:05,160 --> 00:23:09,527 konar burt skref, einn á bak við annað sem við förum, eða komast í lið 464 00:23:09,527 --> 00:23:11,110 og þá senda annan músina í gegnum. 465 00:23:11,110 --> 00:23:13,150 Og eins og þú geta sjá, það Hægt er að fá svolítið sóðalegur. 466 00:23:13,150 --> 00:23:15,360 Sem betur fer, höfum við önnur leið til að leysa það, 467 00:23:15,360 --> 00:23:17,810 þegar við tölum um tvöfalt tengd listum. 468 00:23:17,810 --> 00:23:20,720 >> Ég er Doug Lloyd, þetta er CS50. 469 00:23:20,720 --> 00:23:22,298