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