>> [TÓNLIST spila]
DOUG LLOYD: Allt í lagi.
Svo ef þú lokið bara að vídeó á ein-tengd listum sorry
Ég lét þig burt á a hluti af cliffhanger.
En ég er ánægð að þú ert hér til að klára sagan af tvöfalt-tengd listum.
>> Þannig að ef þú manst frá þessi vídeó, talaði við
um hvernig ein tengd listar gera mæta getu okkar
að takast á við upplýsingar þar sem fjöldi þátta
eða fjölda hluta í listi geta vaxið eða skreppa saman.
Við getum nú að takast á við eitthvað svoleiðis, þar
við gátum ekki takast á við það með fylki.
>> En þeir þjást af einu mikilvægt takmörkun sem
er að með ein tengd lista, getum við bara alltaf fara
í einn farveg í gegnum listann.
Og eina raunverulega ástand þar sem getur orðið vandamál
var þegar við vorum að reyna að eyða einn þáttur.
Og við fengum ekki einu sinni að ræða hvernig á að gera það í ein-tengda listanum í sauðakóðanum.
Það er vissulega mögulegt, en það geta vera a hluti af a þræta.
Svo ef þú finnur þig í aðstæðum þar
þú ert að reyna að eyða einn þætti úr listanum
eða það er að fara að vera nauðsynlegt að þú munt vera eyða
einn þætti úr listi, þú might vilja
íhuga að nota a tvöfalt tengd lista í stað þess að ein-tengda listanum.
Vegna tvöfalt-tengd listum leyfa þér til að færa bæði fram og til baka
í gegnum listann í stað bara áfram í gegnum list--
bara með því að bæta við einum auka þáttur að uppbyggingu skilgreiningu okkar
fyrir tvöfalt-tengda listanum hnút.
>> Aftur, ef þú ert ekki að fara að að eyða einstaklings- þætti
frá list-- vegna þess að við erum að bæta auka reit til uppbyggingu okkar
skýring, hnútar sjálfir fyrir tvöfalt-tengd listum
eru að fara að vera stærri.
Þeir eru að fara að taka upp fleiri bæti af minni.
Og svo ef þetta er ekki eitthvað þú ert að fara að þurfa að gera,
þú getur ákveðið það er ekki þess virði að viðskipti burt
að þurfa að eyða auka bytes af minni þörf
fyrir tvöfalt-tengda listanum ef þú ert ekki að fara að eyða einstaklings- þætti.
En þeir eru líka kúl fyrir aðra hluti líka.
>> Svo eins og ég sagði, við höfum bara að bæta eitt reit til uppbyggingu okkar
definition-- þessa hugmynd á fyrri músina.
Svo með ein-tengda listanum, við hafa gildi og næsta músina,
svo tvöfalt-tengda listanum hefur bara leið til að færa aftur á bak eins og heilbrigður.
>> Nú í ein-tengd Listinn video, talaði við
um þetta eru fimm af Helstu hlutir sem þú þarft að vera
fær um að gera að vinna með tengd listum.
Og fyrir flest þessara, því að það er tvöfalt-tengda listanum
er ekki mjög stórt stökk.
Við getum samt leitað eftir bara áfram frá upphafi til enda.
Við getum samt sem áður stofnað hnút út af þunnt loft, nánast á sama hátt.
Við getum eytt lista nokkuð Á svipaðan hátt líka.
Eina það sem eru subtly mismunandi,
í raun, eru að setja nýja hnúta í listanum,
og við munum að lokum að tala um að eyða einn þáttur af listanum eins og heilbrigður.
Aftur, ansi mikið hin þrjú, við erum
ekki að fara að tala um þá núna því þeir eru bara
mjög minniháttar klip á þeim hugmyndum rætt í ein-tengda listanum vídeó.
>> Svo skulum setja nýjan hnút í tvöfalt-tengda listanum.
Við töluðum um að gera þetta fyrir ein tengd listum eins og heilbrigður,
en það er a par af auka veiðir með tvöfalt-tengd listum.
Við erum [? liggur?] í höfuð hins skrá hér og sumir handahófskennt gildi,
og við viljum fá nýja höfuð á listanum út af þessari aðgerð.
Það er hvers vegna það skilar dllnode stjörnu.
Svo það eru skref?
Þau eru, aftur, mjög svipuð að ein tengd listum
með einu auka viðbót.
Við viljum úthlutar pláss fyrir nýja hnút og athuga til að tryggja að það sé í gildi.
Við viljum að fylla það hnút upp allar upplýsingar sem við
vilja til að setja í það.
Það síðasta sem við þurfum að do-- á auka sem við þurfum að gera, rather--
er að laga Fyrri músina gamla höfuð listanum.
Mundu að því af tvöfalt-tengd listum,
við getum flutt áfram og backwards-- sem
þýðir að hver hnútur í raun bendir tveimur öðrum hnúður í staðinn af réttlátur einn.
Og svo þurfum við að laga gamla yfirmaður lista
að benda aftur á nýja höfuð tengda lista, sem var eitthvað
við ekki að gera áður.
Og eins og áður, aftur við bara bendi á nýja höfuð á listanum.
>> Svo hér er listi.
Við viljum að setja 12 í þennan lista.
Takið eftir að skýringarmynd er aðeins öðruvísi.
Hver hnútur inniheldur þrjú fields-- gögn og Next músina í rauðu,
og Fyrri bendi í bláu.
Ekkert kemur fyrir 15 hnút, svo er Fyrri bendi þess null.
Það er upphaf listanum.
Það er ekkert fyrir það.
Og ekkert kemur á eftir 10 hnút, og svo það er næst bendillinn er null eins og heilbrigður.
>> Svo skulum bæta 12 við þennan lista.
Við þurfum [inaudible] pláss fyrir hnút.
Við að setja 12 inni af því.
Og þá aftur, við þurfum að vera mjög varkár ekki til að rjúfa keðju.
Við viljum endurraða ábendingum í réttri röð.
Og stundum sem gæti mean-- eins og við munum sjá sérstaklega
með delete-- að við höfum sumir óþarfi ábendingum, en það er allt í lagi.
>> Svo hvað við viljum gera fyrst?
Ég myndi mæla með að hlutir sem þú ættir sennilega
gera eru að fylla ábendingum hinna 12 hnút áður en þú snertir allir aðrir.
Svo hvað er 12 að fara að benda á næst?
15.
Hvað kemur fyrir 12?
Ekkert.
Nú höfum við fyllt auka upplýsingar í 12
svo það hefur Fyrri Next og gildi.
>> Nú getum við höfum 15-- þetta auka skref sem við vorum að tala about-- vér
Hægt er að hafa 15 lið aftur til 12.
Og nú getum við flutt höfuð tengda listanum einnig að vera 12.
Svo það er nokkuð svipað og við voru að gera með stakar-tengd listum,
nema fyrir auka skref tengja gamla höfuð listanum
aftur í nýja höfuð á listanum.
>> Nú skulum að lokum eyða hnút frá tengda listanum.
Svo skulum segja að við höfum einhver önnur aðgerð sem
er að finna hnút við viljum að eyða og hefur gefið okkur bendi einmitt
hnúturinn sem við viljum eyða.
Við gerum ekki einu sinni need-- segja Höfuðið er enn á heimsvísu lýst.
Við þurfum ekki höfuð hér.
Allt þetta hlutverk er að gera er að við höfum fann bendi nákvæmlega hnút vér
langar að losna við.
Skulum fá losa af það.
Það er mun auðveldara með tvöfalt-tengd listum.
First-- það er í raun bara nokkra hluti.
Við þurfum bara að laga nærliggjandi ábendingum hnútar svo að þau sleppa yfir
hnúturinn við viljum eyða.
Og þá getum við eytt því hnút.
Svo aftur, við erum bara að fara í gegnum hér.
Við höfum greinilega ákveðið að við viljum eyða hnút X.
Og aftur, hvað ég er gera here-- af way--
er almenn rök fyrir hnút sem er í miðjunni.
There ert a par af auka hellir sem þú
þarf að hafa í huga þegar þú ert að eyða upphafi listanum
eða mjög aftast í listanum.
There er a par af sérstökum horn tilvikum að takast á við það.
>> Svo virkar þetta til að eyða allir hnút í miðju list-- einn sem
hefur lögmæt músina áfram og lögmæt bendi afturábak,
lögmæt Fyrri og næsta músina.
Aftur, ef þú ert að vinna með enda, þú
þarf að sinna þeim örlítið öðruvísi,
og við erum ekki að fara að tala um það núna.
En þú getur sennilega reikna út hvað þarf
að gera bara með því að horfa á þetta myndband.
>> Þannig að við höfum einangrað X. X er hnúturinn við viljum eyða af listanum.
Hvað gerum við?
Í fyrsta lagi þurfum við að endurraða að utan ábendingum.
Við þurfum að endurraða 9 er næst að sleppa yfir 13
og benda á 10-- sem er það sem við höfum bara gert.
Og við þurfum líka að endurraða 10 er Previous
til að benda á 9 í stað þess að benda á að 13.
>> Svo aftur, þetta var skýringarmynd til að byrja með.
Þetta var keðja okkar.
Við þurfum að sleppa yfir 13, en við þurfum einnig að varðveita
heiðarleiki af listanum.
Við viljum ekki að missa eitthvað upplýsingar í hvora átt.
Þannig að við þurfum að endurskipuleggja ábendingum vandlega
svo við brjóta ekki keðju á öllum.
>> Þannig að við getum sagt 9 Next músina bendir á sama stað
að þrettán Next bendillinn bendir núna.
Vegna þess að við erum loksins fara til að vilja sleppa yfir 13.
Svo hvar 13 stig næst, þér langar níu benda það í staðinn.
Svo er það þessi.
Og þá hvar 13 stig aftur að, hvað kemur fyrir 13.,
við viljum 10 benda til að að í stað þess 13.
Nú taka, ef þú fylgir örvarnar, getum við sleppt 13
án þess í raun að tapa öllum upplýsingum.
Við höfum haldið heilleika listanum, færa bæði áfram og afturábak.
Og þá getum við bara svona af hreinsa það upp svolítið
með því að toga listann saman.
Þannig að við endurraðað á ábendingum á hvorri hlið.
Og þá erum við frelsi x hnút sem innihélt 13,
og við fengum ekki rjúfa keðju.
Svo við gerðum gott.
>> Final huga hér á tengd listum.
Svo bæði singly- og tvöfalt-tengt listum, eins og við höfum séð,
Stuðningur virkilega duglegur innsetningu og eyðing þætti.
Þú getur nokkurn veginn gert það í föstu tíma.
Hvað gerði við þurfum að gera til að eyða þáttur bara annað síðan?
Við fluttum einn músina.
Við fluttum annað músina.
Við leystur X-- tók þrjár aðgerðir.
Það tekur alltaf þrjá starfsemi til eyða því node-- að losa hnút.
>> Hvernig eigum við að setja?
Jæja, við erum bara alltaf klísturvamandi á byrjun
ef við erum að setja á skilvirkan hátt.
Þannig að við þurfum að rearrange-- eftir því hvort það er
a singly- eða tvöfalt linked lista, gætum við þurft að gera þremur
eða fjögur starfsemi max.
En aftur, það er alltaf þrír eða fjórir.
Það skiptir ekki máli hversu margir þættir eru í listanum okkar,
það er alltaf þrír eða fjórir operations-- bara eins og eyðingu er alltaf
þrjár eða fjórar aðgerðir.
Það er stöðug tími.
Svo er það mjög mikill.
>> Með fylki, við vorum að gera eitthvað eins og innsetningu tagi.
Þú manst líklega að innsetning tegund er ekki fasti tími reiknirit.
Það er reyndar mjög dýrt.
Svo er þetta mikið betri til að setja.
En eins og ég nefndi í ein-tengda listanum vídeó,
við höfum fengið hæðir hér líka, ekki satt?
Við höfum misst getu til að handahófi aðgang þætti.
Við getum ekki sagt, ég vil þátturinn númer fjögur eða þáttur númer 10 af tengda listanum
á sama hátt og við getum gera það með fjölda
eða við getum bara beint Vísitala í frumefni array okkar.
>> Og svo að reyna að finna þáttur í tengslum list--
ef rannsakandi er important-- getur nú tekið línulega tíma.
Sem listinn fær lengur, það gæti tekið einn til viðbótar skref
fyrir hvert einasta þáttur í skránni í Til að finna það sem við erum að leita að.
Svo er það viðskipti offs.
Það er a hluti af a atvinnumaður og sam þáttur hér.
>> Og tvöfalt-tengd listar eru ekki Síðast konar gögn uppbygging samhliða
sem við munum tala um, taka allar helstu bygging
blokkir C er að setja saman.
Því að í raun getum við jafnvel gera betur en þetta
til að búa til gögn uppbygging sem þú might vera fær til að leita í gegnum
í föstu tíma líka.
En meira um það í öðru vídeó.
>> Ég er Doug Lloyd.
Þetta er CS50.