>> [Glazbom]
Doug LLOYD: U redu.
Dakle, ako ste upravo završili da Video o jednostruko-povezanim popisima žao
Te ostavio sam off na malo Cliffhanger.
Ali drago mi je da ste ovdje završiti priča o dvostruko povezane liste.
>> Dakle, ako se sjećate iz taj video, razgovarali smo
kako pojedinačno povezani popisi ne pohađaju našu sposobnost
da se bave informacijama gdje je broj elemenata
ili broj predmeta u popis može rasti ili smanjivati.
Sada možemo nositi s nešto slično, gdje
nismo mogli nositi s njom s polja.
>> Ali oni ne pate od jedne kritično ograničenje koje
je da se uz pojedinačno povezani Popis, možemo samo uvijek kretati
u jednom smjeru kroz listu.
A jedini pravi stanje gdje da može postati problem
bio je kada smo pokušali Brisanje jednog elementa.
A nismo ni razgovarali o tome kako to učiniti u popisu pojedinačno-povezane u pseudokod.
To je svakako izvodljiv, ali to može biti malo gnjavaža.
Dakle, ako se nađete u situaciji u kojoj
pokušavate izbrisati pojedinačni elementi iz popisa
ili će to biti potrebno da ćete se brisanje
pojedinačni elementi iz popis, možda želite
razmotriti pomoću dvostruko povezani popis, umjesto popisa za jednostruko-povezane.
Zbog dvostruko povezani popisi omogućuju vam premjestiti oba naprijed i natrag
kroz popis, umjesto Samo naprijed kroz list--
Samo dodavanjem jednog dodatni element u našu definiciju strukture
za dvostruko povezane liste čvora.
>> Opet, ako ne ide na se brisanje pojedinačnih elemenata
iz list-- jer mi dodajemo dodatni polje našem strukture
definiciji, sami čvorovi za dvostruko povezane liste
će biti veća.
Oni će uzeti se više bajtova memorije.
I tako, ako to nije nešto ti si idući u morati učiniti,
možda odlučiti da je nije vrijedno trgovina off
morati provesti extra bajta memorije potrebne
za popis dvostruko povezana ako niste će se brisanje pojedinačne elemente.
Ali oni su također super za druge stvari.
>> Dakle, kao što sam rekao, samo moramo dodati jedan jedini polje našem strukture
definition-- ovaj pojam prethodne pokazivača.
Tako je s popisa za jednostruko povezanom smo imaju vrijednost i sljedeći pokazivač,
tako da je popis dvostruko povezana je upravo način za pomicanje unatrag, kao dobro.
>> Sada se u pojedinačno-linked Popis videa, razgovarali smo
o su pet od Glavne stvari koje trebate biti
u mogućnosti to učiniti za rad s povezanim popisima.
A za većinu tih, činjenice da je popis s dvostruko povezani
zapravo i nije veliki skok.
Još uvijek možete pretraživati ​​po samo kreće naprijed od početka do kraja.
Još uvijek možete stvoriti čvor iz zraku, prilično mnogo na isti način.
Možemo brisati popise lijepa mnogo na isti način previše.
Jedine stvari koje su suptilno različita,
stvarno su umetanje novi čvorovi u popisu,
pa ćemo napokon razgovarati o brisanju jedan element iz ljestvicu.
Opet, prilično mnogo ostale tri, mi smo
ne ide razgovarati o njima upravo sada, jer oni su samo
vrlo male tweaks na idejama raspravlja u pojedinačno-povezanog popisa videozapisa.
>> Tako ćemo umetnuti novi čvor u popisu dvostruko povezani.
Razgovarali smo o to za pojedinačno povezani liste i,
ali ima par extra hvata s dvostruko povezanim popisima.
Mi smo [? prolazi?] u glavi od popis ovdje, a neke proizvoljne vrijednosti,
i želimo dobiti novu glavu popisa iz ove funkcije.
Zato vraća dllnode zvijezdu.
Pa što su koraci?
Oni su, opet, vrlo sličan za pojedinačno povezani liste
s pomoćnim toga.
Želimo dodjeljuje prostor za nova čvor i provjera kako bi bili sigurni da je valjana.
Želimo ispuniti tu čvor se sa što informacije koje
želite staviti u njega.
Zadnje što trebamo do-- extra stvar koju trebate učiniti, rather--
je popraviti Prethodna pokazivač stare glave popisa.
Zapamtite da zbog od dvostruko povezane liste,
možemo krenuti naprijed i backwards-- koji
znači da je svaki čvor zapravo ukazuje druga dva čvora, umjesto samo jednog.
I tako moramo popraviti stari šef popisa
ukazati natrag na novu glavu popis povezani, što je nešto
nismo imali za napraviti prije.
A kao i prije, samo smo se vratiti pokazivač na novu glavu na popisu.
>> Dakle, ovdje je popis.
Želimo umetnuti 12 u ovaj popis.
Obavijest da je dijagram je malo drugačija.
Svaki čvor ima tri fields-- podataka, a Sljedeća pokazivač crveno,
a Prethodna pokazivač u plavom.
Ništa dolazi prije 15 čvora, tako da je njegova Prethodna pointer je null.
To je početak popisa.
Nema ništa prije njega.
I ništa ne dolazi nakon 10 čvora, te tako da je kazaljka Sljedeća je ništavan, kao dobro.
>> Tako ćemo dodati 12 na ovaj popis.
Trebamo [nečujan] prostor za čvor.
Mi smo stavili 12 unutar nje.
A onda opet, moramo biti jako Pazite da ne razbiti lanac.
Želimo preurediti upućuje u ispravnom redoslijedu.
A ponekad da bi mogli mean-- kao što ćemo vidjeti posebno
s delete-- da imamo neke suvišne pokazivače, ali to je u redu.
>> Dakle, ono što želimo učiniti prvi?
Ja bih preporučiti stvari koje bi trebali vjerojatno
to su popuniti naputke od 12 čvor prije nego što dodirnete bilo tko drugi.
Pa što je 12 će ukazati na sljedeće?
15.
Što dolazi prije 12?
Ništa.
Sada smo ispuni dodatne informacije u 12
tako da ima Prethodna, sljedeći, i vrijednosti.
>> Sada možemo imati 15-- ovaj dodatni korak smo razgovarali about-- mi
može imati 15 bod natrag na 12.
I sada možemo pomaknuti glavu popis povezani i da se 12.
Dakle, to je prilično slično onome što smo radili s pojedinačno-povezane liste,
osim za dodatni korak povezivanje staru glavu na popis
Natrag na novog šefa popisa.
>> Sada ćemo konačno brisanje čvor s popisa povezane.
Tako recimo imamo neke druge funkcije koje
je pronalaženje čvor želimo obrisati i da nam je dao pokazivač na točno
čvor koji želimo izbrisati.
Mi ni ne need-- reći Glava je još uvijek globalno proglašen.
Ne trebamo glavu ovdje.
Sve to omogućuje radi je imamo pronašao pokazivač na točno čvor mi
Želite se riješiti.
Idemo dobiti osloboditi od njega.
To je puno lakše s dvostruko povezane liste.
First-- to je zapravo samo par stvari.
Mi samo trebate popraviti okolno čvorovi 'pokazivače tako da oni preskaču
čvor želimo izbrisati.
A onda možemo izbrisati taj čvor.
Pa opet, mi samo idemo ovuda.
Mi očito su odlučili da želimo izbrisati čvor X.
I opet, što sam radi here-- od way--
je opći slučaj za čvor koji je u sredini.
Postoji nekoliko dodatni upozorenja da
morate uzeti u obzir kada ste brisanja samog početka popisa
ili samom kraju liste.
Postoji nekoliko posebna Kutak za slučajeve da se bave tamo.
>> Tako to radi za brisanje bilo čvor u sredini onoga koji list--
ima legitiman pokazivač naprijed i legitimna pokazivač unatrag,
legitimna Prethodna Sljedeća i pokazivač.
Opet, ako radite s krajevima, što
morati nositi one malo drugačije,
i nećemo se razgovarati o tome sada.
Ali vjerojatno možete shvatiti što treba
treba učiniti samo gledajući ovaj video.
>> Tako smo izolirani X. X čvor želimo izbrisati s popisa.
Što nam je činiti?
Prvo, moramo preurediti vanjski naputke.
Moramo preurediti 9 je uz preskočiti 13
a točka na kojoj 10-- je ono što smo upravo učinili.
I mi također trebaju preurediti 10 prethodnih
ukazati na 9 umjesto ukazujući na 13.
>> Pa opet, to je bio dijagram za početak.
To je bio naš lanac.
Moramo preskočiti 13, ali moramo i sačuvati
cjelovitost popisa.
Mi ne želimo izgubiti bilo Informacije u oba smjera.
Dakle, moramo preurediti se upućuje pozorno
tako da ne razbiti lanac na sve.
>> Tako možemo reći je sljedeće pokazivač 9 ukazuje na isto mjesto
da trinaest je sljedeće pokazivač ističe upravo sada.
Budući da smo na kraju će htjeti preskočiti 13.
Dakle, gdje god je 13 bodova Sljedeći, te Želite devet ukazati tamo umjesto.
Dakle, to je to.
A onda gdje god 13 bodova natrag da, sve što dolazi prije 13 godina,
želimo ukazati 10 da da, umjesto 13.
Sada primijetite, ako slijedite strelice, možemo ispustiti 13
zapravo bez gubitka podataka.
Mi smo zadržao cjelovitost popisa, kreće i naprijed i nazad.
A onda možemo samo vrsta ga počistiti malo
povlačenjem popis zajedno.
Tako smo preuredio upućuje na obje strane.
A onda smo oslobodili x čvor koji je sadržavao 13,
a nismo razbiti lanac.
Dobar Tako smo i učinili.
>> Završna napomena ovdje na povezanim popisima.
Tako i singly- i dvostruko povezani popisi, kao što smo vidjeli,
Podrška jako učinkovit umetanje i brisanje elemenata.
Možete prilično mnogo učiniti je u stalnom vremenu.
Što moramo učiniti za brisanje element samo sekundu prije?
Preselili smo jedan pokazivač.
Krenuli smo još jedan pokazivač.
Oslobođeni smo X-- uzeo tri operacije.
Uvijek traje tri operacije na izbrišite node-- da oslobodi čvor.
>> Kako umetnuti?
Pa, mi smo samo uvijek letanja na početku
Ako smo umetanje učinkovito.
Dakle, moramo rearrange-- ovisno o tome je li to
singly- ili dvostruko povezani Popis, možda moramo učiniti tri
ili četiri operacije max.
Ali opet, to je uvijek tri ili četiri.
Nije bitno koliko je elementi u našem listu,
to je uvijek tri ili četiri operations-- baš kao i brisanje je uvijek
tri ili četiri operacije.
To je konstanta vrijeme.
Dakle, to je stvarno super.
>> S polja, bili smo radili nešto poput umetanja vrste.
Vjerojatno se sjetiti da je umetanje vrsta nije konstantna vremena algoritam.
To je zapravo prilično skupo.
Dakle, ovo je puno bolje za umetanje.
Ali kao što sam spomenuo u pojedinačno povezani popis videozapisa,
imamo downside ovdje, zar ne?
Mi smo izgubili sposobnost slučajno pristupiti elemente.
Ne možemo reći, želim elementa broj četiri ili je element broj 10 od popisa povezan
isti način na koji možemo učiniti da se s nizom
ili možemo jednostavno izravno indeksa u našu Array u elementu.
>> I tako pokušava pronaći element u povezanom list--
Ako potrazi je important-- Sada mogu uzeti linearno vrijeme.
Kao popis dobiva više, to možda uzeti jedan dodatni korak
za svaki pojedini element u popisu u kako bi se pronašli ono što tražite.
Dakle, postoji trgovina off.
Tu je malo pro i protiv elementa ovdje.
>> A dvostruko povezani popisi nisu Posljednji vrsta kombinacije strukture podataka
da ćemo razgovarati, da sve osnovne zgrade
blokovi C stavljajući zajedno.
Jer, u stvari, možemo čak i bolje od toga
stvoriti strukturu podataka koji možda ćete biti u mogućnosti da pretraživanje
u stalnom vrijeme previše.
No, više o tome u drugom videu.
>> Ja sam Doug Lloyd.
Ovo je CS50.