>> [Predvaja glasba]
Doug LLOYD: V redu.
Torej, če ste pravkar končali, da video na posamezno povezanih seznamov Žal
Pustila sem te odpravite na malo Cliffhanger.
Ampak sem vesela, da si tu, da konča zgodba dvakrat povezanih seznamov.
>> Torej, če se spomnimo iz da je video, smo se pogovarjali
o tem, kako posamezno vezan Seznami storiti udeležijo naše sposobnosti
da se ukvarjajo z informacijami kjer je število elementov
ali število predmetov v seznam lahko raste ali skrči.
Mi lahko zdaj ukvarjajo z nekaj takega, kjer
ne moremo ukvarjati z njo z nizi.
>> Vendar pa ne trpijo zaradi ene kritična omejitev, ki
se da s posamezno vezan seznam, bomo lahko samo kdaj premakniti
v eni smeri skozi seznam.
In edini pravi položaj če se to lahko postane problem
je bilo, ko smo poskušali Brisanje en element.
In nismo niti razpravljali, kako to storiti v posamezno povezano-seznama v psevdokoda.
Prav gotovo je izvedljivo, vendar je lahko malo težav.
Torej, če se znajdete V situaciji, ko
skušate izbrisati posameznih elementov iz seznama
ali pa se dogaja, da se zahteva da boste izbrisali
posamezni elementi iz seznam, boste morda želeli
da razmisli z uporabo dvojno vezan Seznam namesto posamezno povezano-seznam.
Ker ti dvojno povezani-seznami omogočajo premakniti tako naprej in nazaj
po seznamu namesto samo naprej skozi list--
samo z dodajanjem enega dodatnega elementa za našo opredelitvijo strukture
za dvojno povezan seznam-vozlišče.
>> Še enkrat, če ne boš šel k se brisanje posamezne elemente
od list-- ker smo dodajanjem dodatno polje za našo strukturo
definiciji vozlišča sami za dvojno povezanih seznamov
se bodo večji.
Ti boš, da sprejmejo do več bajtov pomnilnika.
In tako, če to ni nekaj, boste morali storiti,
morda ste se odločili, da je ni vredno trade off
bi morali porabiti dodatnih bajtov pomnilnika obvezna
za dvojno povezano-seznam, če niste dogaja se, da izbrišete posamezne elemente.
Ampak oni so tudi kul za preveč drugih stvari.
>> Torej, kot sem že dejal, bomo morali dodati eno samo polje za našo strukturo
definition-- ta pojem prejšnje kazalca.
Torej s posamezno povezano-seznama, smo imajo vrednost in Next kazalec,
zato je še toliko bolj povezani-seznam ima samo način, da se umakne nazaj, kot tudi.
>> Zdaj v posamezno povezana, seznam video, smo se pogovarjali
o teh pet izmed Glavne stvari, ki jih potrebujejo, da bi
sposobni narediti za delo s povezanimi seznamov.
In za večino od njih je dejstvo, da je to dvojno vezan seznam
ni res velik skok.
Še vedno lahko poiščete s pomočjo, ki ga pravkar napreduje od začetka do konca.
Še vedno lahko ustvarite vozlišče izven tanek zrak, precej na enak način.
Lahko izbrisati sezname precej skoraj enak način preveč.
Edine stvari, ki so nekoliko drugačna,
Res, vstavljate nova vozlišča v seznamu,
in bomo končno govorimo o brisanju en sam element, s seznama, kot tudi.
Again, precej ostali trije, smo
Ne bom govoril o njih prav zdaj, ker oni so samo
zelo majhnim poteg na idejah razpravljali v posamezno povezano-seznam video.
>> Torej, kaj je vstaviti novo vozlišče v dvojno povezanih seznamu.
Pogovarjali smo se o tem, za posamič-vezan seznamov, kot tudi,
vendar pa je nekaj ekstra ujame z dvakrat povezanih seznamov.
Mi smo [? poteka?] v glavi izmed seznam tukaj in nekaj arbitrarna vrednost,
in želimo, da bi dobili novo glavo seznama iz te funkcije.
Zato je vrne dllnode zvezdo.
Torej, kaj so koraki?
So spet zelo podobni za posamezno povezane sezname
z enim dodatnim dodatkom.
Želimo, da namenja prostor za novo vozlišče in preverite, da se prepričajte, da je veljavna.
Želimo, da zapolni to vozlišče up vse podatke, ki smo
želijo dati v njem.
Zadnja stvar, moramo do-- extra stvar, moramo storiti, rather--
je, da se določi Prejšnji kazalec starega glavo seznama.
Ne pozabite, da zato, ker dvakrat povezani, seznami,
lahko gremo naprej in backwards-- ki
pomeni, da je vsako vozlišče dejansko poudarja na dveh drugih vozlišč namesto samo enega.
In zato moramo popraviti stara glava seznama
za nazaj kaže na novo vodjo povezano seznam, ki je bil nekaj
mi ni bilo treba storiti, preden.
In tako kot prej, samo se vrnete kazalec na novi vodja seznama.
>> Torej, tukaj je seznam.
Želimo, da vstavite 12 v tem seznamu.
Opazimo, da je diagram je nekoliko drugačna.
Vsako vozlišče vsebuje tri fields-- podatkov, in Next kazalec v rdeči barvi,
ter Prejšnja kazalec v modri barvi.
Nič ne pride pred 15. vozlišča, zato njeno Prejšnja kazalec je nična.
To je začetek seznama.
Nič ni pred njim.
In nič ne pride po 10 vozlišča, in tako da je naslednji kazalec je nična, kot dobro.
>> Torej, kaj je dodati 12 na tem seznamu.
Potrebujemo [neslišno] prostor za vozlišče.
Mi je dal 12 notranjost nje.
In potem spet, moramo biti res Pazite, da ne bi prekinil verigo.
Želimo, da preurediti kazalci v pravilnem vrstnem redu.
In včasih, da bi mean-- kot bomo videli, zlasti
z delete-- da imamo nekaj odveč kazalci, ampak to je v redu.
>> Torej, kaj želimo storiti najprej?
Jaz bi priporočal Stvari morate verjetno
storiti je, da izpolnite kazalce od 12 vozlišče preden se boste dotaknili kdo drug.
Torej, kaj je 12 dogaja, da kaže na naslednji?
15.
Kaj pride pred 12.?
Nič.
Zdaj smo zasedena dodatne informacije v 12
tako da ima Prejšnja, Naslednja, in vrednost.
>> Zdaj imamo lahko 15-- to dodatno korak smo govorili about-- mi
ima lahko 15 pik nazaj do 12.
In zdaj lahko gremo glavo povezano seznam, da tudi 12.
Torej, to je precej podoben temu, kar smo počeli s posamezno povezanih seznamov,
razen dodatnim korakom vezni staro glavo seznamu
nazaj na novo glavo seznama.
>> Zdaj pa končno brisanje vozlišče iz povezanega seznama.
Torej, recimo, da imamo nekatere druge funkcije, ki
je najti vozlišče želimo izbrisati in nam je dal kazalec za točno
vozlišče, ki ga želimo izbrisati.
Mi sploh ne need-- reči Glava je še vedno globalno razglašena.
Mi ne potrebujemo glavo tukaj.
Vse to funkcija počne, je, ki smo jih Najdenih kazalec ravno mi vozlišča
želijo znebiti.
Oglejmo znebiti tega.
To je veliko lažje z dvojno povezani seznam.
First-- da je dejansko le nekaj stvari.
Vedeti pa je treba, da se določi okolico kazalci vozlišč ", tako da jih preskočimo
vozlišče želimo izbrisati.
In potem bomo lahko izbrišete to vozlišče.
Torej še enkrat, smo le, da bo tu skozi.
Očitno smo se odločili, da želimo izbrisati X. vozlišča
In še enkrat, kaj sem početje here--, ki jih way--
je splošni primer za vozlišče, ki je v sredini.
Obstaja nekaj extra opozorili, da ste
morali razmisliti, ko ste izbrisali na samem začetku seznama
ali zelo konec seznama.
Tukaj je nekaj posebnega primeri corner, da se ukvarjajo s tam.
>> Torej, to deluje za brisanje kateregakoli vozlišča v sredini list-- tistega, ki
ima legitimno kazalec naprej in legitimna kazalec nazaj,
legitimno Prejšnji in Naslednji kazalec.
Še enkrat, če ste delajo s konci, ki jih
potrebe po obdelavi tistih nekoliko drugače,
in ne bomo do govoriti o tem zdaj.
Vendar pa boste verjetno lahko ugotovimo, kaj je potrebno
treba storiti samo z gledanjem ta video.
>> Torej smo izolirali X. X je vozlišče želimo izbrisati iz seznama.
Kaj počnemo?
Najprej moramo preurediti zunanja kazalci.
Moramo preurediti 9 je zraven preskočiti 13
in točka, 10--, ki je tisto, kar smo pravkar končali.
In moramo tudi preurediti 10 je Prejšnja
izpostaviti 9 namesto kaže na 13.
>> Torej še enkrat, to je bil diagram za začetek.
To je bil naš verige.
Moramo preskočiti 13, vendar moramo tudi ohraniti
celovitost seznama.
Ne želimo izgubiti koli informacije v obe smeri.
Zato moramo preurediti so kazalci previdno
tako da ne bomo prekinili verigo sploh.
>> Tako lahko rečemo, 9 Next kazalec opozarja na istem mestu
da je trinajst Next Kazalec kaže zdaj.
Ker smo na koncu bomo želeli preskočiti 13.
Torej, kjerkoli 13 točk zraven vas želijo devet tam namesto točko.
Torej, to je to.
In potem kamorkoli 13 točk nazaj da, kar pride pred 13.,
želimo 10 do točke tistemu namesto 13.
Zdaj opazili, če boste sledili puščice, da lahko spusti 13
ne da bi dejansko izgubili vse podatke.
Mi smo ohranil celovitost seznamu premika naprej in nazaj.
In potem bomo lahko nekako , da počisti malo
s potegom seznam skupaj.
Tako smo preuredili kazalci na obeh straneh.
In potem smo osvobojeni x vozlišča, ki je vseboval 13,
in nismo prekinili verigo.
Tako smo naredili dobro.
>> Končna opomba tukaj na povezanih seznamih.
Torej tako singly- in dvojno vezan sezname, kot smo videli,
Podpora za res učinkovito vstavljanje in brisanje elementov.
Lahko precej storiti je v nenehnem času.
Kaj moramo storiti, da se črta element le sekundo?
Preselili smo se en kazalec.
Preselili smo se drug kazalec.
Osvobojeni smo X-- vzel tri operacije.
Vedno traja tri operacije na izbrisati to node-- sprostiti vozlišče.
>> Kako vstaviti?
No, mi smo samo vedno zlepljenje na začetku
če bomo učinkovito vstavljanje.
Zato moramo rearrange-- odvisno od tega, če je
singly- ali dvojno vezan seznam, bomo morda morali narediti tri
ali štirih operacijah maks.
Ampak še enkrat, to je vedno tri ali štiri.
Ni važno, koliko Elementi so v našem seznamu,
je vedno tri ali štiri operations-- tako kot izbris, je vedno
tri ali štiri operacije.
To je stalen čas.
Tako da je res super.
>> Z nizi, smo počeli nekaj podobnega vstavljanja vrste.
Verjetno ste se spomni, da je vključitev nekako ni konstantna čas algoritem.
To je pravzaprav zelo drago.
Torej je to veliko bolje za vstavljanje.
Toda, kot sem omenil v posamično povezane seznam video,
imamo negativna tudi tukaj, kajne?
Izgubili smo sposobnost, da naključno dostop elemente.
Ne moremo reči, želim število elementov štiri ali element številka 10 povezanega seznama
na enak način, da smo lahko to, da s paleto
ali mi lahko samo neposredno indeks v elementu naše Array je.
>> In tako poskušajo najti element v povezanem list--
če je iskanje important-- odslej lahko linearni čas.
Kot seznam dobi več, to lahko traja en dodaten korak
za vsak element v seznamu v da bi našli tisto, kar iščete.
Torej je trgovinske off.
Tam je malo pro in con element tukaj.
>> In še toliko bolj povezani, seznami niso zadnja vrsta strukture podatkov kombinaciji
da bomo govorili o tem, ob vse osnovne stavbe na
bloki C dajanje skupaj.
Ker v resnici, smo lahko še boljše kot to
ustvariti podatkovno strukturo, ki boste morda lahko iskali s pomočjo
v stalnem času preveč.
Ampak več o tem v drugem videu.
>> Sem Doug Lloyd.
To je CS50.