1 00:00:00,000 --> 00:00:03,381 >> [TÓNLIST spila] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Allt í lagi. 4 00:00:05,520 --> 00:00:07,860 Svo ef þú lokið bara að vídeó á ein-tengd listum sorry 5 00:00:07,860 --> 00:00:09,568 Ég lét þig burt á a hluti af cliffhanger. 6 00:00:09,568 --> 00:00:12,790 En ég er ánægð að þú ert hér til að klára sagan af tvöfalt-tengd listum. 7 00:00:12,790 --> 00:00:15,250 >> Þannig að ef þú manst frá þessi vídeó, talaði við 8 00:00:15,250 --> 00:00:18,500 um hvernig ein tengd listar gera mæta getu okkar 9 00:00:18,500 --> 00:00:22,090 að takast á við upplýsingar þar sem fjöldi þátta 10 00:00:22,090 --> 00:00:24,442 eða fjölda hluta í listi geta vaxið eða skreppa saman. 11 00:00:24,442 --> 00:00:26,400 Við getum nú að takast á við eitthvað svoleiðis, þar 12 00:00:26,400 --> 00:00:28,310 við gátum ekki takast á við það með fylki. 13 00:00:28,310 --> 00:00:30,560 >> En þeir þjást af einu mikilvægt takmörkun sem 14 00:00:30,560 --> 00:00:33,790 er að með ein tengd lista, getum við bara alltaf fara 15 00:00:33,790 --> 00:00:36,200 í einn farveg í gegnum listann. 16 00:00:36,200 --> 00:00:39,010 Og eina raunverulega ástand þar sem getur orðið vandamál 17 00:00:39,010 --> 00:00:41,250 var þegar við vorum að reyna að eyða einn þáttur. 18 00:00:41,250 --> 00:00:46,000 Og við fengum ekki einu sinni að ræða hvernig á að gera það í ein-tengda listanum í sauðakóðanum. 19 00:00:46,000 --> 00:00:48,797 Það er vissulega mögulegt, en það geta vera a hluti af a þræta. 20 00:00:48,797 --> 00:00:50,630 Svo ef þú finnur þig í aðstæðum þar 21 00:00:50,630 --> 00:00:53,175 þú ert að reyna að eyða einn þætti úr listanum 22 00:00:53,175 --> 00:00:55,430 eða það er að fara að vera nauðsynlegt að þú munt vera eyða 23 00:00:55,430 --> 00:00:57,970 einn þætti úr listi, þú might vilja 24 00:00:57,970 --> 00:01:02,090 íhuga að nota a tvöfalt tengd lista í stað þess að ein-tengda listanum. 25 00:01:02,090 --> 00:01:06,320 Vegna tvöfalt-tengd listum leyfa þér til að færa bæði fram og til baka 26 00:01:06,320 --> 00:01:09,340 í gegnum listann í stað bara áfram í gegnum list-- 27 00:01:09,340 --> 00:01:13,950 bara með því að bæta við einum auka þáttur að uppbyggingu skilgreiningu okkar 28 00:01:13,950 --> 00:01:16,690 fyrir tvöfalt-tengda listanum hnút. 29 00:01:16,690 --> 00:01:19,770 >> Aftur, ef þú ert ekki að fara að að eyða einstaklings- þætti 30 00:01:19,770 --> 00:01:24,810 frá list-- vegna þess að við erum að bæta auka reit til uppbyggingu okkar 31 00:01:24,810 --> 00:01:28,340 skýring, hnútar sjálfir fyrir tvöfalt-tengd listum 32 00:01:28,340 --> 00:01:29,550 eru að fara að vera stærri. 33 00:01:29,550 --> 00:01:31,600 Þeir eru að fara að taka upp fleiri bæti af minni. 34 00:01:31,600 --> 00:01:34,160 Og svo ef þetta er ekki eitthvað þú ert að fara að þurfa að gera, 35 00:01:34,160 --> 00:01:36,300 þú getur ákveðið það er ekki þess virði að viðskipti burt 36 00:01:36,300 --> 00:01:39,360 að þurfa að eyða auka bytes af minni þörf 37 00:01:39,360 --> 00:01:43,940 fyrir tvöfalt-tengda listanum ef þú ert ekki að fara að eyða einstaklings- þætti. 38 00:01:43,940 --> 00:01:46,760 En þeir eru líka kúl fyrir aðra hluti líka. 39 00:01:46,760 --> 00:01:51,260 >> Svo eins og ég sagði, við höfum bara að bæta eitt reit til uppbyggingu okkar 40 00:01:51,260 --> 00:01:55,360 definition-- þessa hugmynd á fyrri músina. 41 00:01:55,360 --> 00:01:58,620 Svo með ein-tengda listanum, við hafa gildi og næsta músina, 42 00:01:58,620 --> 00:02:02,850 svo tvöfalt-tengda listanum hefur bara leið til að færa aftur á bak eins og heilbrigður. 43 00:02:02,850 --> 00:02:04,960 >> Nú í ein-tengd Listinn video, talaði við 44 00:02:04,960 --> 00:02:07,210 um þetta eru fimm af Helstu hlutir sem þú þarft að vera 45 00:02:07,210 --> 00:02:09,449 fær um að gera að vinna með tengd listum. 46 00:02:09,449 --> 00:02:12,880 Og fyrir flest þessara, því að það er tvöfalt-tengda listanum 47 00:02:12,880 --> 00:02:14,130 er ekki mjög stórt stökk. 48 00:02:14,130 --> 00:02:17,936 Við getum samt leitað eftir bara áfram frá upphafi til enda. 49 00:02:17,936 --> 00:02:20,810 Við getum samt sem áður stofnað hnút út af þunnt loft, nánast á sama hátt. 50 00:02:20,810 --> 00:02:23,591 Við getum eytt lista nokkuð Á svipaðan hátt líka. 51 00:02:23,591 --> 00:02:25,340 Eina það sem eru subtly mismunandi, 52 00:02:25,340 --> 00:02:28,970 í raun, eru að setja nýja hnúta í listanum, 53 00:02:28,970 --> 00:02:33,722 og við munum að lokum að tala um að eyða einn þáttur af listanum eins og heilbrigður. 54 00:02:33,722 --> 00:02:35,430 Aftur, ansi mikið hin þrjú, við erum 55 00:02:35,430 --> 00:02:37,888 ekki að fara að tala um þá núna því þeir eru bara 56 00:02:37,888 --> 00:02:43,920 mjög minniháttar klip á þeim hugmyndum rætt í ein-tengda listanum vídeó. 57 00:02:43,920 --> 00:02:46,292 >> Svo skulum setja nýjan hnút í tvöfalt-tengda listanum. 58 00:02:46,292 --> 00:02:48,750 Við töluðum um að gera þetta fyrir ein tengd listum eins og heilbrigður, 59 00:02:48,750 --> 00:02:52,020 en það er a par af auka veiðir með tvöfalt-tengd listum. 60 00:02:52,020 --> 00:02:55,280 Við erum [? liggur?] í höfuð hins skrá hér og sumir handahófskennt gildi, 61 00:02:55,280 --> 00:02:58,600 og við viljum fá nýja höfuð á listanum út af þessari aðgerð. 62 00:02:58,600 --> 00:03:01,414 Það er hvers vegna það skilar dllnode stjörnu. 63 00:03:01,414 --> 00:03:02,330 Svo það eru skref? 64 00:03:02,330 --> 00:03:04,496 Þau eru, aftur, mjög svipuð að ein tengd listum 65 00:03:04,496 --> 00:03:05,670 með einu auka viðbót. 66 00:03:05,670 --> 00:03:08,900 Við viljum úthlutar pláss fyrir nýja hnút og athuga til að tryggja að það sé í gildi. 67 00:03:08,900 --> 00:03:11,510 Við viljum að fylla það hnút upp allar upplýsingar sem við 68 00:03:11,510 --> 00:03:12,564 vilja til að setja í það. 69 00:03:12,564 --> 00:03:15,480 Það síðasta sem við þurfum að do-- á auka sem við þurfum að gera, rather-- 70 00:03:15,480 --> 00:03:19,435 er að laga Fyrri músina gamla höfuð listanum. 71 00:03:19,435 --> 00:03:21,310 Mundu að því af tvöfalt-tengd listum, 72 00:03:21,310 --> 00:03:23,110 við getum flutt áfram og backwards-- sem 73 00:03:23,110 --> 00:03:27,080 þýðir að hver hnútur í raun bendir tveimur öðrum hnúður í staðinn af réttlátur einn. 74 00:03:27,080 --> 00:03:29,110 Og svo þurfum við að laga gamla yfirmaður lista 75 00:03:29,110 --> 00:03:32,151 að benda aftur á nýja höfuð tengda lista, sem var eitthvað 76 00:03:32,151 --> 00:03:33,990 við ekki að gera áður. 77 00:03:33,990 --> 00:03:37,420 Og eins og áður, aftur við bara bendi á nýja höfuð á listanum. 78 00:03:37,420 --> 00:03:38,220 >> Svo hér er listi. 79 00:03:38,220 --> 00:03:40,144 Við viljum að setja 12 í þennan lista. 80 00:03:40,144 --> 00:03:42,060 Takið eftir að skýringarmynd er aðeins öðruvísi. 81 00:03:42,060 --> 00:03:47,710 Hver hnútur inniheldur þrjú fields-- gögn og Next músina í rauðu, 82 00:03:47,710 --> 00:03:50,170 og Fyrri bendi í bláu. 83 00:03:50,170 --> 00:03:54,059 Ekkert kemur fyrir 15 hnút, svo er Fyrri bendi þess null. 84 00:03:54,059 --> 00:03:55,350 Það er upphaf listanum. 85 00:03:55,350 --> 00:03:56,560 Það er ekkert fyrir það. 86 00:03:56,560 --> 00:04:03,350 Og ekkert kemur á eftir 10 hnút, og svo það er næst bendillinn er null eins og heilbrigður. 87 00:04:03,350 --> 00:04:05,616 >> Svo skulum bæta 12 við þennan lista. 88 00:04:05,616 --> 00:04:08,070 Við þurfum [inaudible] pláss fyrir hnút. 89 00:04:08,070 --> 00:04:11,480 Við að setja 12 inni af því. 90 00:04:11,480 --> 00:04:14,840 Og þá aftur, við þurfum að vera mjög varkár ekki til að rjúfa keðju. 91 00:04:14,840 --> 00:04:17,144 Við viljum endurraða ábendingum í réttri röð. 92 00:04:17,144 --> 00:04:19,519 Og stundum sem gæti mean-- eins og við munum sjá sérstaklega 93 00:04:19,519 --> 00:04:24,120 með delete-- að við höfum sumir óþarfi ábendingum, en það er allt í lagi. 94 00:04:24,120 --> 00:04:25,750 >> Svo hvað við viljum gera fyrst? 95 00:04:25,750 --> 00:04:28,290 Ég myndi mæla með að hlutir sem þú ættir sennilega 96 00:04:28,290 --> 00:04:35,350 gera eru að fylla ábendingum hinna 12 hnút áður en þú snertir allir aðrir. 97 00:04:35,350 --> 00:04:38,640 Svo hvað er 12 að fara að benda á næst? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Hvað kemur fyrir 12? 100 00:04:42,430 --> 00:04:43,640 Ekkert. 101 00:04:43,640 --> 00:04:46,280 Nú höfum við fyllt auka upplýsingar í 12 102 00:04:46,280 --> 00:04:49,320 svo það hefur Fyrri Next og gildi. 103 00:04:49,320 --> 00:04:53,505 >> Nú getum við höfum 15-- þetta auka skref sem við vorum að tala about-- vér 104 00:04:53,505 --> 00:04:56,590 Hægt er að hafa 15 lið aftur til 12. 105 00:04:56,590 --> 00:04:59,634 Og nú getum við flutt höfuð tengda listanum einnig að vera 12. 106 00:04:59,634 --> 00:05:02,550 Svo það er nokkuð svipað og við voru að gera með stakar-tengd listum, 107 00:05:02,550 --> 00:05:06,940 nema fyrir auka skref tengja gamla höfuð listanum 108 00:05:06,940 --> 00:05:09,810 aftur í nýja höfuð á listanum. 109 00:05:09,810 --> 00:05:12,170 >> Nú skulum að lokum eyða hnút frá tengda listanum. 110 00:05:12,170 --> 00:05:14,350 Svo skulum segja að við höfum einhver önnur aðgerð sem 111 00:05:14,350 --> 00:05:18,080 er að finna hnút við viljum að eyða og hefur gefið okkur bendi einmitt 112 00:05:18,080 --> 00:05:19,710 hnúturinn sem við viljum eyða. 113 00:05:19,710 --> 00:05:22,360 Við gerum ekki einu sinni need-- segja Höfuðið er enn á heimsvísu lýst. 114 00:05:22,360 --> 00:05:23,590 Við þurfum ekki höfuð hér. 115 00:05:23,590 --> 00:05:26,830 Allt þetta hlutverk er að gera er að við höfum fann bendi nákvæmlega hnút vér 116 00:05:26,830 --> 00:05:28,090 langar að losna við. 117 00:05:28,090 --> 00:05:28,940 Skulum fá losa af það. 118 00:05:28,940 --> 00:05:31,859 Það er mun auðveldara með tvöfalt-tengd listum. 119 00:05:31,859 --> 00:05:33,650 First-- það er í raun bara nokkra hluti. 120 00:05:33,650 --> 00:05:38,760 Við þurfum bara að laga nærliggjandi ábendingum hnútar svo að þau sleppa yfir 121 00:05:38,760 --> 00:05:40,240 hnúturinn við viljum eyða. 122 00:05:40,240 --> 00:05:43,484 Og þá getum við eytt því hnút. 123 00:05:43,484 --> 00:05:45,150 Svo aftur, við erum bara að fara í gegnum hér. 124 00:05:45,150 --> 00:05:49,625 Við höfum greinilega ákveðið að við viljum eyða hnút X. 125 00:05:49,625 --> 00:05:51,500 Og aftur, hvað ég er gera here-- af way-- 126 00:05:51,500 --> 00:05:54,580 er almenn rök fyrir hnút sem er í miðjunni. 127 00:05:54,580 --> 00:05:56,547 There ert a par af auka hellir sem þú 128 00:05:56,547 --> 00:05:59,380 þarf að hafa í huga þegar þú ert að eyða upphafi listanum 129 00:05:59,380 --> 00:06:01,040 eða mjög aftast í listanum. 130 00:06:01,040 --> 00:06:03,730 There er a par af sérstökum horn tilvikum að takast á við það. 131 00:06:03,730 --> 00:06:07,960 >> Svo virkar þetta til að eyða allir hnút í miðju list-- einn sem 132 00:06:07,960 --> 00:06:11,550 hefur lögmæt músina áfram og lögmæt bendi afturábak, 133 00:06:11,550 --> 00:06:14,460 lögmæt Fyrri og næsta músina. 134 00:06:14,460 --> 00:06:16,530 Aftur, ef þú ert að vinna með enda, þú 135 00:06:16,530 --> 00:06:18,500 þarf að sinna þeim örlítið öðruvísi, 136 00:06:18,500 --> 00:06:19,570 og við erum ekki að fara að tala um það núna. 137 00:06:19,570 --> 00:06:21,319 En þú getur sennilega reikna út hvað þarf 138 00:06:21,319 --> 00:06:24,610 að gera bara með því að horfa á þetta myndband. 139 00:06:24,610 --> 00:06:28,910 >> Þannig að við höfum einangrað X. X er hnúturinn við viljum eyða af listanum. 140 00:06:28,910 --> 00:06:30,140 Hvað gerum við? 141 00:06:30,140 --> 00:06:32,800 Í fyrsta lagi þurfum við að endurraða að utan ábendingum. 142 00:06:32,800 --> 00:06:35,815 Við þurfum að endurraða 9 er næst að sleppa yfir 13 143 00:06:35,815 --> 00:06:38,030 og benda á 10-- sem er það sem við höfum bara gert. 144 00:06:38,030 --> 00:06:41,180 Og við þurfum líka að endurraða 10 er Previous 145 00:06:41,180 --> 00:06:44,610 til að benda á 9 í stað þess að benda á að 13. 146 00:06:44,610 --> 00:06:46,490 >> Svo aftur, þetta var skýringarmynd til að byrja með. 147 00:06:46,490 --> 00:06:47,730 Þetta var keðja okkar. 148 00:06:47,730 --> 00:06:51,027 Við þurfum að sleppa yfir 13, en við þurfum einnig að varðveita 149 00:06:51,027 --> 00:06:52,110 heiðarleiki af listanum. 150 00:06:52,110 --> 00:06:54,680 Við viljum ekki að missa eitthvað upplýsingar í hvora átt. 151 00:06:54,680 --> 00:06:59,620 Þannig að við þurfum að endurskipuleggja ábendingum vandlega 152 00:06:59,620 --> 00:07:02,240 svo við brjóta ekki keðju á öllum. 153 00:07:02,240 --> 00:07:05,710 >> Þannig að við getum sagt 9 Next músina bendir á sama stað 154 00:07:05,710 --> 00:07:08,040 að þrettán Next bendillinn bendir núna. 155 00:07:08,040 --> 00:07:10,331 Vegna þess að við erum loksins fara til að vilja sleppa yfir 13. 156 00:07:10,331 --> 00:07:13,750 Svo hvar 13 stig næst, þér langar níu benda það í staðinn. 157 00:07:13,750 --> 00:07:15,200 Svo er það þessi. 158 00:07:15,200 --> 00:07:20,370 Og þá hvar 13 stig aftur að, hvað kemur fyrir 13., 159 00:07:20,370 --> 00:07:24,800 við viljum 10 benda til að að í stað þess 13. 160 00:07:24,800 --> 00:07:29,290 Nú taka, ef þú fylgir örvarnar, getum við sleppt 13 161 00:07:29,290 --> 00:07:32,380 án þess í raun að tapa öllum upplýsingum. 162 00:07:32,380 --> 00:07:36,002 Við höfum haldið heilleika listanum, færa bæði áfram og afturábak. 163 00:07:36,002 --> 00:07:38,210 Og þá getum við bara svona af hreinsa það upp svolítið 164 00:07:38,210 --> 00:07:40,930 með því að toga listann saman. 165 00:07:40,930 --> 00:07:43,270 Þannig að við endurraðað á ábendingum á hvorri hlið. 166 00:07:43,270 --> 00:07:46,231 Og þá erum við frelsi x hnút sem innihélt 13, 167 00:07:46,231 --> 00:07:47,480 og við fengum ekki rjúfa keðju. 168 00:07:47,480 --> 00:07:50,980 Svo við gerðum gott. 169 00:07:50,980 --> 00:07:53,000 >> Final huga hér á tengd listum. 170 00:07:53,000 --> 00:07:55,990 Svo bæði singly- og tvöfalt-tengt listum, eins og við höfum séð, 171 00:07:55,990 --> 00:07:58,959 Stuðningur virkilega duglegur innsetningu og eyðing þætti. 172 00:07:58,959 --> 00:08:00,750 Þú getur nokkurn veginn gert það í föstu tíma. 173 00:08:00,750 --> 00:08:03,333 Hvað gerði við þurfum að gera til að eyða þáttur bara annað síðan? 174 00:08:03,333 --> 00:08:04,440 Við fluttum einn músina. 175 00:08:04,440 --> 00:08:05,920 Við fluttum annað músina. 176 00:08:05,920 --> 00:08:07,915 Við leystur X-- tók þrjár aðgerðir. 177 00:08:07,915 --> 00:08:14,500 Það tekur alltaf þrjá starfsemi til eyða því node-- að losa hnút. 178 00:08:14,500 --> 00:08:15,280 >> Hvernig eigum við að setja? 179 00:08:15,280 --> 00:08:17,280 Jæja, við erum bara alltaf klísturvamandi á byrjun 180 00:08:17,280 --> 00:08:19,400 ef við erum að setja á skilvirkan hátt. 181 00:08:19,400 --> 00:08:21,964 Þannig að við þurfum að rearrange-- eftir því hvort það er 182 00:08:21,964 --> 00:08:24,380 a singly- eða tvöfalt linked lista, gætum við þurft að gera þremur 183 00:08:24,380 --> 00:08:26,824 eða fjögur starfsemi max. 184 00:08:26,824 --> 00:08:28,365 En aftur, það er alltaf þrír eða fjórir. 185 00:08:28,365 --> 00:08:30,531 Það skiptir ekki máli hversu margir þættir eru í listanum okkar, 186 00:08:30,531 --> 00:08:33,549 það er alltaf þrír eða fjórir operations-- bara eins og eyðingu er alltaf 187 00:08:33,549 --> 00:08:35,320 þrjár eða fjórar aðgerðir. 188 00:08:35,320 --> 00:08:36,919 Það er stöðug tími. 189 00:08:36,919 --> 00:08:38,169 Svo er það mjög mikill. 190 00:08:38,169 --> 00:08:40,620 >> Með fylki, við vorum að gera eitthvað eins og innsetningu tagi. 191 00:08:40,620 --> 00:08:44,739 Þú manst líklega að innsetning tegund er ekki fasti tími reiknirit. 192 00:08:44,739 --> 00:08:46,030 Það er reyndar mjög dýrt. 193 00:08:46,030 --> 00:08:48,840 Svo er þetta mikið betri til að setja. 194 00:08:48,840 --> 00:08:51,840 En eins og ég nefndi í ein-tengda listanum vídeó, 195 00:08:51,840 --> 00:08:54,030 við höfum fengið hæðir hér líka, ekki satt? 196 00:08:54,030 --> 00:08:57,580 Við höfum misst getu til að handahófi aðgang þætti. 197 00:08:57,580 --> 00:09:02,310 Við getum ekki sagt, ég vil þátturinn númer fjögur eða þáttur númer 10 af tengda listanum 198 00:09:02,310 --> 00:09:04,990 á sama hátt og við getum gera það með fjölda 199 00:09:04,990 --> 00:09:08,630 eða við getum bara beint Vísitala í frumefni array okkar. 200 00:09:08,630 --> 00:09:10,930 >> Og svo að reyna að finna þáttur í tengslum list-- 201 00:09:10,930 --> 00:09:15,880 ef rannsakandi er important-- getur nú tekið línulega tíma. 202 00:09:15,880 --> 00:09:18,330 Sem listinn fær lengur, það gæti tekið einn til viðbótar skref 203 00:09:18,330 --> 00:09:22,644 fyrir hvert einasta þáttur í skránni í Til að finna það sem við erum að leita að. 204 00:09:22,644 --> 00:09:23,560 Svo er það viðskipti offs. 205 00:09:23,560 --> 00:09:25,780 Það er a hluti af a atvinnumaður og sam þáttur hér. 206 00:09:25,780 --> 00:09:29,110 >> Og tvöfalt-tengd listar eru ekki Síðast konar gögn uppbygging samhliða 207 00:09:29,110 --> 00:09:32,840 sem við munum tala um, taka allar helstu bygging 208 00:09:32,840 --> 00:09:34,865 blokkir C er að setja saman. 209 00:09:34,865 --> 00:09:37,900 Því að í raun getum við jafnvel gera betur en þetta 210 00:09:37,900 --> 00:09:41,970 til að búa til gögn uppbygging sem þú might vera fær til að leita í gegnum 211 00:09:41,970 --> 00:09:43,360 í föstu tíma líka. 212 00:09:43,360 --> 00:09:46,080 En meira um það í öðru vídeó. 213 00:09:46,080 --> 00:09:47,150 >> Ég er Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Þetta er CS50. 215 00:09:49,050 --> 00:09:50,877