[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.