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