[Prehrávanie hudby] DOUG LLOYD: Dobre. Takže ak ste práve dokončili, že video na single-previazané zoznamy prepáčte Nechal som ťa preč na trochu Cliffhanger. Ale som rád, že si tu až do konca Príbeh dvojito spojových zoznamov. 

Takže ak si spomínate z že video, sme sa rozprávali o tom, ako jednotlivo viazané Zoznamy robiť navštevovať našu schopnosť sa vysporiadať s informáciami kde počet prvkov alebo počet kusov zoznam môže rásť alebo zmenšiť. Teraz môžeme riešiť niečo také, kde nemohli sme sa s tým vyrovnať s poli. 

Ale oni trpia jedného kritická obmedzenia, ktoré sa, že s jednotlivo viazané zoznam, môžeme len niekedy pohnúť v jednom smere v zozname. A jediný skutočný stav kde, že sa môže stať problémom bolo, keď sme sa snažili Odstránenie jedného prvku. A my sme ani diskutovať o tom, ako na to v single-Google zoznamu v pseudokódu. To je určite možné, ale to môže byť trochu zmätkov. Takže ak sa ocitnete v situácii, keď sa snažíte zmazať jednotlivé prvky zo zoznamu alebo to bude potrebné že budete mazanie jednotlivé prvky z zoznamu, možno budete chcieť zvážiť použitie dvojnásobne viazaný Zoznam miesto single-previazaný zoznam. Vzhľadom k tomu, dvojito spojové zoznamy vám umožňujú do pohybovať oboma dopredu a dozadu v zozname namiesto len dopredu cez list-- len tým, že pridá jeden navyše prvok na našej definície štruktúry Pre dvojito Google zoznamu uzla. 

Opäť platí, že ak sa nebudeme byť mazanie jednotlivých prvkov od list-- pretože sme pridávanie navyše pole k našej štruktúre definície, samotné uzly pre dvojito spojových zoznamov sa bude väčšia. Chystajú sa vziať up viac bajtov pamäte. A tak, ak to nie je niečo, budete musieť urobiť, sa môžete rozhodnúť, že je to nestojí za kompromis musieť stráviť ďalšie bajtov pamäte požadované pre dvojito Google zoznamu, ak si nie ste bude mazanie jednotlivých prvkov. Ale sú tiež v pohode pre iné veci. 

Tak ako som povedal, budeme musieť pridať jediné pole do našej štruktúre definition-- tento pojem z predchádzajúcej ukazovateľ. Takže s single-prepojenom zoznamu, my mať hodnotu A ďalší ukazovateľ, takže dvojito previazaný zoznam jednoducho musí spôsob, ako sa pohybovať späť rovnako. 

Teraz v single-spojený Zoznam video, hovorili sme o nich je päť hlavné veci, ktoré je potrebné schopný robiť prácu s spojových zoznamov. A pre väčšinu z nich je skutočnosť, že je to dvojnásobne viazaný zoznam nie je naozaj veľký skok. Stále môžeme prehľadávať obyčajným dopredu od začiatku až do konca. Stále môžeme vytvoriť uzol von riedky vzduch, skoro rovnakým spôsobom. Môžeme zmazať zoznamy dosť veľa rovnaký cesta taky. Jediné veci, ktoré sú nepatrne odlišné, Naozaj, vkladáte nové uzly do zoznamu, a budeme konečne hovoriť o odstraňovaní jeden prvok zo zoznamu rovnako. Opäť platí, že do značnej miery ďalšie tri, my sme nebude hovoriť o nich hneď teraz, pretože sú to len veľmi malé vylepší sa k myšlienkam diskutovaným V single-previazaný zoznam video. 

Takže poďme vložiť nový uzol do dvojito Google zoznamu. Hovorili sme o tom to pre jednotlivo viazané zoznamy tiež, ale je tu pár naviac chytí s dvojito spojových zoznamov. Sme [? absolvovaní?] v hlave zoznam tu a niektorí ľubovoľná hodnota, a chceme získať nové hlavy zoznamu z tejto funkcie. To je dôvod, prečo vráti dllnode hviezdu. Takže aké sú kroky? Sú opäť veľmi podobný sa jednotlivo viazané zoznamy s jednou prístelkou navyše. Chceme pridelí miesto pre nový uzol a kontrola, aby sa uistil, že je platný. Chceme naplniť tento uzol hore s tým, čo informácie, ktoré chcieť dať v ňom. Posledná vec, ktorú musíme do-- ďalšia vec, ktorú musíme urobiť, rather-- je opraviť Predchádzajúci ukazovateľ starého hlavy zoznamu. Pamätajte si, že preto, z dvojito spojové zoznamy, sa môžeme pohnúť dopredu a ktorý backwards-- Znamená to, že každý uzol v skutočnosti poukazuje ďalšími dvoma uzlami namiesto len jeden. A preto je treba opraviť stará hlava zoznamu prejdite späť do nového šéfa prepojený zoznam, čo bolo niečo, sme nemuseli robiť skôr. A rovnako ako predtým, len sme Vrátiť Ukazovateľ na nového šéfa zozname. 

Takže tu je zoznam. Chceme vložiť 12 do tohto zoznamu. Všimnite si, že diagram sa mierne líšia. Každý uzol obsahuje tri fields-- dát, a ďalší ukazovateľ v červenej farbe, a predchádzajúce ukazovateľ v modrej farbe. Nič príde pred uzol 15, tak jeho predchádzajúci ukazovateľ je null. Je to začiatok zoznamu. Je tu pred ním nič nie je. A nič po uzla 10 prichádza a tak to je ďalší ukazovateľ null rovnako. 

Takže poďme sa pridať 12 do tohto zoznamu. Potrebujeme [nepočuteľný] priestor pre uzol. My sme dali 12 vnútri nej. A potom znova, musíme byť naozaj Dajte pozor, aby ste prerušiť reťaz. Chceme zmeniť usporiadanie ukazovatele v správnom poradí. A niekedy, že by mohli mean-- ako uvidíme obzvlášť s delete--, že máme nejaké redundantné ukazovatele, ale to je v poriadku. 

Takže to, čo chceme urobiť ako prvé? Chcel by som odporučiť veci, ktoré by pravdepodobne cieľov, sa naplniť ukazovatele z 12 uzol, než sa dotknete niekto iný. Takže to, čo sa 12 bude ukazovať na ďalší? 15. To, čo je pred 12? Nič. Teraz sme už obsadené ďalšie informácie v 12 tak to má predchádzajúce, budúci, a hodnotu. 

Teraz môžeme mať 15-- to navyše krokom, ktorý sme hovorili about-- my môže mať 15 bodov späť na 12 rokov. A teraz sa môžeme presunúť hlavu prepojený zoznam tiež bude 12. Takže je to dosť podobné tomu, čo sme robili s single-previazané zoznamy, s výnimkou pre ďalší krok spájajúci starú hlavu zoznamu späť na nového šéfa zozname. 

Teraz poďme konečne zmazať uzol z prepojeného zoznamu. Takže povedzme, že máme niektoré ďalšie funkcie, ktorá je nájsť uzol chceme zmazať a dal nám ukazovateľ presne uzol, ktorý chceme odstrániť. Nemáme ani need-- hovoria Hlava je stále globálne deklarovaný. My to tu nie je treba hlavu. Všetky tieto funkcie robí, je máme našiel ukazovateľ presne na uzle my chcú zbaviť. Poďme sa zbaviť toho. Je to oveľa jednoduchšie s dvojito spojený zoznamy. First-- je to vlastne Len pár vecí. Potrebujeme len opraviť okolí ukazovatele uzlov, "tak, aby preskočiť uzol chceme odstrániť. A potom môžeme zmazať tento uzol. Takže znovu, my sme len tak tadiaľ. Zrejme sme sa rozhodli, že chceme zmazať uzla X. A opäť, to, čo som si robí here-- podľa way-- je všeobecný prípade takéhoto uzol, ktorý je uprostred. Existuje pár ďalšie výhrady, ktoré ste je potrebné vziať do úvahy, keď ste mazanie samého začiatku zoznamu alebo veľmi koniec zoznamu. K dispozícii je niekoľko špeciálnych rohové prípady zaoberať sa tam. 

Tak to funguje pre vymazanie ľubovoľný uzol v stredu list-- ten, ktorý má oprávnený ukazovateľ vpred a legitímne ukazovateľ späť, legitímne Predchádzajúce a Ďalšie ukazovateľ. Opäť platí, že ak pracujete s konci, budete musieť zvládnuť tie, trochu inak, a my nebudeme o tom hovoriť teraz. Ale môžete nejspíš prísť na to, čo je potrebné je potrebné urobiť len tým, že sledovanie tohto videa. 

Preto sme izolované X. X je uzol chceme vymazať zo zoznamu. Čo budeme robiť? Po prvé, musíme preskupiť vonkajšie ukazovatele. Musíme zmeniť usporiadanie 9 je vedľa preskočiť 13 a bod, ktorý 10-- je to, čo sme práve urobili. A musíme tiež preskupiť 10 je Predchádzajúci poukázať na 9. miesto a ukázal na 13. 

Takže znovu, to bolo diagram začať. To bol náš reťazec. Musíme preskočiť 13, ale musíme tiež zachovať celistvosť zoznamu. Nechceme stratiť akýkoľvek Informácie v oboch smeroch. Preto musíme preskupiť Ukazovatele starostlivo takže neporušujú reťaz vôbec. 

Takže môžeme povedať 9 Next ukazovateľ poukazuje na rovnaké miesto že trinásť Budúci Ukazovateľ poukazuje práve teraz. Vzhľadom k tomu, že sme sa nakoniec bude chcieť preskočiť 13. Takže tam, kde 13 bodov ďalšie, vám Ak nine tam bodu miesto. Tak to je to. A potom tam, kde 13 bodov späť sa, čo nastane skôr 13, Chceme 10 bodu sa, že miesto 13. A teraz si všimnúť, ak budete postupovať šípky, môžeme klesnúť 13 bez toho by v skutočnosti straty akejkoľvek informácie. Sme stále integrity zoznamu Posunutím oboch dopredu a dozadu. A potom môžeme jednoducho tak nejako z upratať trochu zatiahnutím zoznamu dohromady. Takže sme preskupí ukazovatele na oboch stranách. A potom sme oslobodil x Uzol, ktorý obsahoval 13, a nemali prerušiť reťaz. Tak sme urobili dobre. 

Záverečná poznámka tu na spojových zoznamov. Tak ako singly- a dvojnásobne viazané zoznamy, ako sme videli, Pomoc skutočne efektívne vkladanie a vymazanie prvkov. Môžete si skoro robiť to v konštantnom čase. Čo musíme urobiť vymazať prvok len sekunda? Presťahovali sme sa jeden ukazovateľ. Presťahovali sme ďalší ukazovateľ. Oslobodil sme X-- trvalo tri operácie. Vždy trvá tri operácie na odstrániť, node-- uvoľniť uzol. 

Ako môžeme vložiť? No, my sme proste vždy pripínanie na začiatku či máme vkladanie efektívne. Preto musíme rearrange-- V závislosti na tom, či je to singly- alebo dvojito-viazanej zoznam, možno musíme urobiť tri alebo štyri operácie max. Ale na druhú stranu, je to vždy tri alebo štyri. Nezáleží na tom, koľko prvky sú v našom zozname, je to vždy tri alebo štyri operations-- rovnako ako vypustenie je vždy tri alebo štyri operácie. Je to konštantný čas. Tak to je naozaj skvelé. 

S poli, sme robili niečo ako vloženie druhu. Pravdepodobne ste pripomenúť, že vloženie sort nie je konštantná algoritmus. Je to vlastne dosť drahé. Tak je to oveľa lepšie pre vkladanie. Ale ako som sa zmienil v single-spojený zoznam videa, máme nevýhodu tady taky, že jo? Stratili sme schopnosť náhodne prístup k prvkom. Nemôžeme povedať, chcem prvok číslo štyri alebo prvok číslo 10 prepojeného zoznamu rovnakým spôsobom, že môžeme tomu, že s radom Alebo môžeme len priamo index do elementu našej ponuku je. 

A tak sa snaží nájsť prvok v Google list-- ak vyhľadávanie DÔLEŽITÉ Teraz môže trvať lineárny čas. Ako sa zoznam dostane dlhší, to môže trvať ďalší krok pre každé jednotlivé súčasti v zozname v s cieľom nájsť to, čo hľadáme. Takže je tu kompromisy. Je tu trochu profík a con prvkom je tu. 

A dvojnásobne-spojové zoznamy nie sú Posledný druh kombinácia dátové štruktúry že budeme hovoriť o, pričom všetky základné budovy bloky C bol dávať dohromady. Pretože v skutočnosti, môžeme ešte lepšie, než to vytvoriť štruktúru dát, ktorá by ste mali byť schopní prehľadávať v konštantnom čase tiež. Ale o tom viac v inom videu. 

Som Doug Lloyd. To je CS50.