[Přehrávání hudby] DOUG LLOYD: Dobře. Takže pokud jste právě dokončili, že video na singly-provázané seznamy promiňte Nechal jsem tě pryč na trochu cliffhanger. Ale jsem rád, že jsi tady až do konce Příběh dvojitě spojových seznamů. 

Takže pokud si vzpomínáte z že video, jsme si povídali o tom, jak jednotlivě vázané Seznamy dělat navštěvovat naši schopnost se vypořádat s informacemi kde počet prvků nebo počet kusů seznam může růst nebo zmenšit. Nyní můžeme řešit něco takového, kde nemohli jsme se s tím vyrovnat s poli. 

Ale oni trpí jednoho kritická omezení, která se, že s jednotlivě vázané seznam, můžeme jen někdy pohnout v jednom směru v seznamu. A jediný skutečný stav kde, že se může stát problémem bylo, když jsme se snažili Odstranění jednoho prvku. A my jsme ani diskutovat o tom, jak na to v singly-Google seznamu v pseudokódu. To je jistě proveditelné, ale to může být trochu zmatků. Takže pokud se ocitnete v situaci, kdy se snažíte smazat jednotlivé prvky ze seznamu nebo to bude nutné že budete mazání jednotlivé prvky z seznamu, možná budete chtít zvážit použití dvojnásobně vázaný Seznam místo singly-provázaný seznam. Vzhledem k tomu, dvojitě spojové seznamy vám umožňují do pohybovat oběma dopředu a dozadu v seznamu namísto jen dopředu přes list-- jen tím, že přidá jeden navíc prvek na naší definice struktury Pro dvojitě Google seznamu uzlu. 

Opět platí, že pokud se nebudeme být mazání jednotlivých prvků od list-- protože jsme přidávání navíc pole k naší struktuře definice, samotné uzly pro dvojitě spojových seznamů se bude větší. Chystají se vzít up více bajtů paměti. A tak, pokud to není něco, budete muset udělat, se můžete rozhodnout, že je to nestojí za kompromis muset strávit další bajtů paměti požadováno pro dvojitě Google seznamu, pokud si nejste bude mazání jednotlivých prvků. Ale jsou také v pohodě pro jiné věci. 

Tak jak jsem řekl, budeme muset přidat jedno jediné pole do naší struktuře definition-- tento pojem z předchozí ukazatel. Takže s singly-provázaném seznamu, my mít hodnotu A další ukazatel, takže dvojitě provázaný seznam prostě musí způsob, jak se pohybovat zpět stejně. 

Nyní v singly-spojený Seznam video, mluvili jsme o nich je pět hlavní věci, které je třeba schopný dělat práci s spojových seznamů. A pro většinu z nich je skutečnost, že je to dvojnásob vázaný seznam není opravdu velký skok. Stále můžeme prohledávat pouhým kupředu od začátku až do konce. Stále můžeme vytvořit uzel ven řídký vzduch, skoro stejným způsobem. Můžeme smazat seznamy dost hodně stejný cesta taky. Jediné věci, které jsou nepatrně odlišné, Opravdu, vkládáte nové uzly do seznamu, a budeme konečně hovořit o odstraňování jeden prvek ze seznamu stejně. Opět platí, že do značné míry další tři, my jsme nebude mluvit o nich hned teď, protože jsou to jen velmi malé vylepší se k myšlenkám diskutovaným V singly-provázaný seznam video. 

Takže pojďme vložit nový uzel do dvojitě Google seznamu. Mluvili jsme o tom to pro jednotlivě vázané seznamy také, ale je tu pár navíc chytí s dvojitě spojových seznamů. Jsme [? absolvování?] v hlavě seznam zde a někteří libovolná hodnota, a chceme získat nové hlavy seznamu z této funkce. To je důvod, proč vrátí dllnode hvězdu. Takže jaké jsou kroky? Jsou opět velmi podobný se jednotlivě vázané seznamy s jednou přistýlkou ​​navíc. Chceme přidělí místo pro nový uzel a kontrola, aby se ujistil, že je platný. Chceme naplnit tento uzel nahoru s tím, co informace, které chtít dát v něm. Poslední věc, kterou musíme do-- další věc, kterou musíme udělat, rather-- je opravit Předchozí ukazatel starého hlavy seznamu. Pamatujte si, že proto, z dvojitě spojové seznamy, se můžeme pohnout kupředu a který backwards-- Znamená to, že každý uzel ve skutečnosti poukazuje dalšími dvěma uzly namísto jen jeden. A proto je třeba opravit stará hlava seznamu přejděte zpět do nového šéfa propojený seznam, což bylo něco, jsme nemuseli dělat dřív. A stejně jako předtím, jen jsme Vrátit Ukazatel na nového šéfa seznamu. 

Takže tady je seznam. Chceme vložit 12 do tohoto seznamu. Všimněte si, že diagram se mírně liší. Každý uzel obsahuje tři fields-- dat, a další ukazatel v červené barvě, a předchozí ukazatel v modré barvě. Nic přijde před uzel 15, tak jeho předchozí ukazatel je null. Je to začátek seznamu. Je tu před ním nic není. A nic po uzlu 10 přichází a tak to je další ukazatel null stejně. 

Takže pojďme se přidat 12 do tohoto seznamu. Potřebujeme [neslyšitelný] prostor pro uzel. My jsme dali 12 uvnitř ní. A pak znovu, musíme být opravdu Dejte pozor, abyste přerušit řetěz. Chceme změnit uspořádání ukazatele ve správném pořadí. A někdy, že by mohly mean-- jak uvidíme zvláště s delete--, že máme nějaké redundantní ukazatele, ale to je v pořádku. 

Takže to, co chceme udělat jako první? Chtěl bych doporučit věci, které by pravděpodobně cílů, se naplnit ukazatele z 12 uzel, než se dotknete někdo jiný. Takže to, co se 12 bude ukazovat na další? 15. To, co je před 12? Nic. Nyní jsme již obsazeno další informace ve 12 tak to má předchozí, příští, a hodnotu. 

Nyní můžeme mít 15-- to navíc krokem, který jsme mluvili about-- my může mít 15 bodů zpět na 12 let. A teď se můžeme přesunout hlavu propojený seznam také bude 12. Takže je to dost podobné tomu, co jsme dělali s singly-provázané seznamy, s výjimkou pro další krok spojující starou hlavu seznamu zpět na nového šéfa seznamu. 

Nyní pojďme konečně smazat uzel z propojeného seznamu. Takže řekněme, že máme některé další funkce, která je najít uzel chceme smazat a dal nám ukazatel přesně uzel, který chceme odstranit. Nemáme ani need-- říkají Hlava je stále globálně deklarován. My to tady není třeba hlavu. Všechna tato funkce dělá, je máme našel ukazatel přesně na uzlu my chtějí zbavit. Pojďme se zbavit toho. Je to mnohem jednodušší s dvojitě spojený seznamy. First-- je to vlastně Jen pár věcí. Potřebujeme jen opravit okolí ukazatele uzlů, "tak, aby přeskočit uzel chceme odstranit. A pak můžeme smazat tento uzel. Takže znovu, my jsme jen tak tudy. Zřejmě jsme se rozhodli, že chceme smazat uzlu X. A opět, to, co jsem si dělá here-- podle way-- je obecný případě takového uzel, který je uprostřed. Existuje pár další výhrady, které jste je třeba vzít v úvahu, když jste mazání samého začátku seznamu nebo velmi konec seznamu. K dispozici je několik speciálních rohové případy zabývat se tam. 

Tak to funguje pro vymazání libovolný uzel ve středu list-- ten, který má oprávněný ukazatel vpřed a legitimní ukazatel zpět, legitimní Předchozí a Další ukazatel. Opět platí, že pokud pracujete s konci, budete muset zvládnout ty, trochu jinak, a my nebudeme o tom mluvit teď. Ale můžete nejspíš přijít na to, co je potřeba je třeba udělat jen tím, že sledování tohoto videa. 

Proto jsme izolované X. X je uzel chceme vymazat ze seznamu. Co děláme? Za prvé, musíme přeskupit vnější ukazatele. Musíme změnit uspořádání 9 je vedle přeskočit 13 a bod, který 10-- je to, co jsme právě udělali. A musíme také přeskupit 10 je Předchozí poukázat na 9. místo a ukázal na 13. 

Takže znovu, to bylo diagram začít. To byl náš řetězec. Musíme přeskočit 13, ale musíme také zachovat celistvost seznamu. Nechceme ztratit jakýkoli Informace v obou směrech. Proto musíme přeskupit Ukazatele pečlivě takže neporušují řetěz vůbec. 

Takže můžeme říci 9 Next ukazatel poukazuje na stejné místo že třináct Příští Ukazatel poukazuje právě teď. Vzhledem k tomu, že jsme se nakonec bude chtít přeskočit 13. Takže tam, kde 13 bodů další, vám Chcete-nine tam bodu místo. Tak to je to. A pak tam, kde 13 bodů zpět se, co nastane dříve 13, Chceme 10 bodu se, že místo 13. A teď si všimnout, pokud budete postupovat šipky, můžeme klesnout 13 aniž by ve skutečnosti ztráty jakékoli informace. Jsme stále integrity seznamu Posunutím obou dopředu a dozadu. A pak můžeme prostě tak nějak z uklidit trochu zatažením seznamu dohromady. Takže jsme přeskupila ukazatele na obou stranách. A pak jsme osvobodil x Uzel, který obsahoval 13, a neměli přerušit řetěz. Tak jsme udělali dobře. 

Závěrečná poznámka tady na spojových seznamů. Tak jak singly- a dvojnásobně vázané seznamy, jak jsme viděli, Podpora skutečně efektivní vkládání a vymazání prvků. Můžete si skoro dělat to v konstantním čase. Co musíme udělat vymazat prvek jen sekunda? Přestěhovali jsme se jeden ukazatel. Přestěhovali jsme další ukazatel. Osvobodil jsme X-- trvalo tři operace. Vždy trvá tři operace na odstranit, node-- uvolnit uzel. 

Jak můžeme vložit? No, my jsme prostě vždycky připínání na začátku jestli máme vkládání efektivně. Proto musíme rearrange-- V závislosti na tom, zda je to singly- nebo dvojitě-vázané seznam, možná musíme udělat tři nebo čtyři operace max. Ale na druhou stranu, je to vždy tři nebo čtyři. Nezáleží na tom, kolik prvky jsou v našem seznamu, je to vždy tři nebo čtyři operations-- stejně jako vypuštění je vždy tři nebo čtyři operace. Je to konstantní čas. Tak to je opravdu skvělé. 

S poli, jsme dělali něco jako vložení druhu. Pravděpodobně jste připomenout, že vložení sort není konstantní algoritmus. Je to vlastně dost drahé. Tak je to mnohem lepší pro vkládání. Ale jak jsem se zmínil v singly-spojený seznam videa, máme nevýhodu tady taky, že jo? Ztratili jsme schopnost náhodně přístup k prvkům. Nemůžeme říci, chci prvek číslo čtyři nebo prvek číslo 10 propojeného seznamu stejným způsobem, že můžeme tomu, že s řadou Nebo můžeme jen přímo index do elementu naší nabídku je. 

A tak se snaží najít prvek v Google list-- pokud vyhledávání DŮLEŽITÉ Nyní může trvat lineární čas. Jak se seznam dostane delší, to může trvat další krok pro každé jednotlivé součásti v seznamu v s cílem nalézt to, co hledáme. Takže je tu kompromisy. Je tu trochu profík a con prvkem je zde. 

A dvojnásobně-spojové seznamy nejsou Poslední druh kombinace datové struktury že budeme mluvit o, přičemž všechny základní budovy bloky C byl dávat dohromady. Protože ve skutečnosti, můžeme ještě lépe, než to vytvořit strukturu dat, která byste měli být schopni prohledávat v konstantním čase také. Ale o tom více v jiném videu. 

Jsem Doug Lloyd. To je CS50.