>> [MUSIC JOC]
DOUG LLOYD: Bine.
Deci, dacă tocmai ați terminat că video de pe listele individual legate rău
Ți-am lăsat pe o pic de cliffhanger.
Dar mă bucur că ești aici pentru a termina povestea de liste dublu-legate.
>> Deci, dacă vă amintiți de la că video, am vorbit
despre modul în care-legate individual Listele merg capacitatea noastră
să se ocupe de informații în cazul în care numărul de elemente
sau numărul de articole în o listă poate să crească sau micsora.
Putem face acum cu ceva de genul asta, în cazul în care
nu am putut face cu o cu tablouri.
>> Dar ei suferă de o limitare critică care
este că cu un legat individual Lista, ne putem muta doar vreodată
într-o singură direcție prin lista.
Și singurul situația reală în cazul în care, care poate deveni o problemă
a fost atunci când am încercat să șterge un singur element.
Și nu am nici discuta cum se face într-o listă individual legat în pseudocod.
Este cu siguranță greu de realizat, dar acesta poate fi un pic de un hassle.
Deci, dacă vă aflați în situația în care
pe care încercați să ștergeți elemente singulare din lista
sau va fi necesară că veți fi ștergerea
elemente unice din lista, ați putea dori
să ia în considerare utilizarea unui legată de două ori lista în loc de o listă individual legat.
Deoarece listele de două ori legate permiteți pentru a muta înainte și înapoi atât
prin lista în loc de doar înainte prin list--
doar prin adăugarea unui element suplimentar la definiția noastră structură
pentru nodul lista de două ori legat.
>> Din nou, dacă nu sunteți de gând să fie ștergerea elemente unice
de la list-- pentru că suntem adăugarea de un câmp suplimentar pentru a structurii noastre
definiție, nodurile înșiși pentru liste dublu-legate
vor fi mai mari.
Vor să ia Mai multe bytes de memorie.
Și așa, dacă acest lucru nu este ceva ai de gând să nevoie pentru a face,
s-ar putea să decidă că e nu merita compromisul
să să-și petreacă extra bytes de memorie necesară
Pentru o listă de două ori legată, dacă nu sunteți va fi ștergerea elemente unice.
Dar sunt, de asemenea, se răcească pentru alte lucruri.
>> Deci, după cum am spus, trebuie doar să adăugați un singur câmp pentru a structurii noastre
definition-- această noțiune de un pointer precedent.
Deci, cu o listă individual-legate, am au valoarea și indicatorul continuare,
astfel încât lista dublu-legat doar are un mod de a muta înapoi, de asemenea.
>> Acum, în individual legat Lista video, am vorbit
despre acestea sunt cinci dintre lucruri principale pe care trebuie să fie
în stare să facă pentru a lucra cu liste legate.
Și pentru cele mai multe dintre acestea, faptul că este o listă de două ori legată
nu este cu adevărat un salt mare.
Putem căuta în continuare prin doar prin avansează de la început până la sfârșit.
Putem crea încă un nod din aer subțire, destul de mult în același mod.
Putem șterge liste destul de același fel de mult prea.
Singurele lucruri care sunt subtil diferite,
într-adevăr, sunt introducerea noi noduri în listă,
și vom vorbi în cele din urmă despre ștergerea un singur element din listă, de asemenea.
Din nou, destul de mult celelalte trei, suntem
Nu vorbi despre ele acum pentru că sunt doar
trucuri minore pe ideile discutate în lista video separat legat.
>> Deci, haideți să introduceți un nou nod într-o listă de două ori legată.
Am vorbit despre a face acest lucru pentru liste individual legat de asemenea,
dar există o serie de plus prinde cu liste dublu-legate.
Suntem [? trece?] în capul lista de aici și o valoare arbitrară,
și vrem să ajungem noul șef din lista din această funcție.
De aceea, se întoarce o stea dllnode.
Deci, care sunt pașii?
Ele sunt, din nou, foarte asemănător listelor legată individual
cu o plus suplimentar.
Vrem să alocă spațiu pentru un nou nod și verificați pentru a vă asigura că este valabil.
Vrem să umple acel nod până cu orice informații pe care le
doriți să puneți în ea.
Ultimul lucru de care avem nevoie pentru a do-- lucru suplimentar trebuie să facem, rather--
este de a stabili indicatorul precedent a capului vechi listei.
Amintiți-vă că, din cauza liste de dublu-legate,
putem merge mai departe și backwards-- care
înseamnă că fiecare nod punctele de fapt la alte două noduri loc de unul singur.
Și așa că trebuie să se stabilească vechiul cap al listei
la punctul înapoi la noul șef al listei de legătura, care era ceva
nu am avut de a face înainte de.
Și ca și mai înainte, ne întoarcem doar o pointer la noul șef al listei.
>> Deci, aici este o listă.
Vrem să introduceți 12 în această listă.
Observați că diagrama este ușor diferit.
Fiecare nod conține trei câmpuri sub date, și un pointer Următorul în roșu,
și un pointer anterioară în albastru.
Nimic nu vine înainte de nodul de 15, astfel încât sa pointer precedent este nul.
Este începutul listei.
Nu e nimic în fața sa.
Și nimic nu vine dupa nodul 10, și asa ca este pointer Următorul este nul, de asemenea.
>> Deci, haideți să adăugați 12 la această listă.
Avem nevoie de [neauzit] spațiu pentru nodul.
Am pus 12 în interiorul acestuia.
Și apoi din nou, trebuie să fie într-adevăr Aveți grijă să nu pentru a rupe lantul.
Vrem să rearanja indicii în ordinea corectă.
Și, uneori, care ar putea mean-- cum vom vedea în special
cu delete-- că avem niște indicii redundante, dar e OK.
>> Deci, ceea ce vrem să facem mai întâi?
Mi-ar recomanda lucruri pe care le ar fi trebuit probabil
face să umple indicii ale 12 nod înainte de a atinge altcineva.
Deci, ce este de 12 de gând să arate la următorul?
15.
Ceea ce vine înainte de 12?
Nimic.
Acum ne-am umplut informații suplimentare în 12
deci are Anterior, Next, și valoarea.
>> Acum 15-- putem avea această suplimentar pas am vorbit about-- noi
poate avea 15 laturi Inapoi la 12.
Și acum ne putem muta capul de listei de legătura să fie, de asemenea, 12.
Deci, este destul de similar cu ceea ce am făceau cu liste individual-legate,
excepție pentru etapa suplimentara de conectarea vechiul cap al listei
înapoi la noul șef al listei.
>> Acum, haideți să ștergeți în cele din urmă un nod dintr-o listă legată.
Așa că haideți să spunem că avem o altă funcție care
este de a găsi un nod vrem să ștergeți și ne-a dat un pointer la exact
nodul pe care dorim să-l ștergeți.
Noi nici măcar nu need-- spun cap este încă declarată la nivel global.
Nu avem nevoie de capul aici.
Toate această funcție este de a face este ne-am găsit un pointer la exact WE nod
vrei sa scapi de.
Să scăpăm de ea.
Este mult mai ușor cu liste de două ori legat.
First-- este de fapt doar câteva lucruri.
Avem nevoie doar de a stabili jurul indicii noduri, astfel încât acestea trece peste
nodul vrem să ștergeți.
Și atunci putem sterge acel nod.
Deci, din nou, vom merge doar pe aici.
Am decis că, aparent vrem să ștergeți X. nod
Și din nou, ceea ce eu sunt face here-- de way--
este un caz general de nod, care este în mijloc.
Există o serie de limitări suplimentare pe care le
trebuie să ia în considerare atunci când sunteți ștergerea Chiar de la începutul listei
sau chiar la sfârșitul listei.
Există o serie de special cazuri colț pentru a face față acolo.
>> Deci, acest lucru funcționează pentru ștergerea orice nod în mijlocul celui list-- care
are un indicator legitim înainte și un pointer legitim înapoi,
legitim Anterioară și următoare de pointer.
Din nou, dacă sunteți de lucru cu capetele, vă
trebuie să se ocupe de cei ușor diferit,
și noi nu vom vorbim despre asta acum.
Dar puteți, probabil, dau seama ce are nevoie
să fie făcut doar prin vizionarea acestui film.
>> Deci ne-am izolat X. X este nodul vrem să ștergeți din listă.
Ce facem?
În primul rând, avem nevoie pentru a rearanja indicii exterioare.
Avem nevoie pentru a rearanja 9 de pe lângă săriți peste 13
și punctul de 10-- care este ceea ce tocmai am făcut.
Și avem nevoie, de asemenea, să rearanja 10 Înapoi
pentru a indica 9 în loc de arătând spre 13.
>> Deci, din nou, acest lucru a fost diagrama pentru a începe cu.
Acest lucru a fost lanțul nostru.
Avem nevoie pentru a trece peste 13, dar avem nevoie pentru a păstra, de asemenea,
integritatea listei.
Nu vrem să-și piardă orice informații în orice direcție.
Deci, avem nevoie pentru a rearanja indicii cu atenție
așa că nu rupe lantul, la toate.
>> Deci, putem spune 9 lui pointer Urmatorul subliniază în același loc
că treisprezece Next pointer puncte acum.
Pentru că suntem în cele din urmă gând să doriți să săriți peste 13.
Deci, ori de câte ori 13 puncte viitoare, doresc nouă la punctul acolo în loc.
Deci asta e.
Și apoi ori de câte ori 13 puncte înapoi la, orice vine înainte de 13,
vrem 10 de la punctul în acest loc de 13.
Acum observați, dacă urmați săgeți, putem scădea 13
fără a pierde de fapt nici o informație.
Am păstrat integritatea a listei, în mișcare atât înainte și înapoi.
Și apoi putem doar un fel de curăța un pic
trăgând lista împreună.
Asa ca am reamenajat indicii pe fiecare parte.
Și apoi ne-am eliberat X nod care conținea 13,
și nu am rupe lantul.
Așa că am făcut bine.
>> Notă finală aici, pe liste legate.
Deci, atât singly- și dublu-legate liste, așa cum am văzut,
suport de inserție într-adevăr eficient și ștergerea elementelor.
Puteți face destul de mult o în timp constant.
Ce a trebuie să facem pentru a șterge un element doar o secundă în urmă?
Ne-am mutat un pointer.
Ne-am mutat un alt pointer.
Am eliberat X- luat trei operațiuni.
Este nevoie de trei operații la Întotdeauna șterge care node-- pentru a elibera un nod.
>> Cum putem introduce?
Ei bine, suntem doar mereu tacking pe la începutul
dacă ne introduce în mod eficient.
Deci, avem nevoie să rearrange-- în funcție de dacă este
un singly- sau dublu-legat Lista, am putea să facem trei trebuie
sau patru operațiuni max.
Dar, din nou, este întotdeauna trei sau patru.
Nu contează cât de multe elemente sunt în lista noastră,
este întotdeauna trei sau patru operations-- la fel ca ștergerea este întotdeauna
trei sau patru operațiuni.
E timpul constant.
Așa că e foarte mare.
>> Cu tablouri, făceam ceva de genul sortare prin inserție.
Probabil vă amintiți că inserție fel nu este un algoritm de timp constant.
Este de fapt destul de scump.
Deci, acest lucru este mult mai bine pentru a introduce.
Dar, așa cum am menționat în individual-legate de listă video,
avem un dezavantaj aici, nu?
Am pierdut capacitatea de a acces aleatoriu elemente.
Nu putem spune, vreau numărul element de patru sau numărul element de 10 de o listă legată
în același mod în care putem face acest lucru cu o serie
sau putem doar direct index în elementul gama noastre.
>> Și astfel încercarea de a găsi un element dintr-o list-- legat
dacă căutarea este important-- poate lua acum timp liniar.
Ca lista devine mai lungă, aceasta s-ar putea lua un pas suplimentar
pentru fiecare element unic în lista de la scopul de a găsi ceea ce căutați.
Deci nu e off comerciale.
Există un pic de o pro și elementul con aici.
>> Și liste de doua ori-legate nu de sunt Ultima fel de combinație structură de date
că vom vorbi despre, luând toată clădirea de bază
blocuri de C o pune împreună.
Pentru că, de fapt, putem chiar face mai bine decât acest lucru
pentru a crea o structură de date care s-ar putea fi capabil de a căuta prin
în timp constant prea.
Dar mai mult pe faptul că într-un alt film.
>> Sunt Doug Lloyd.
Acest lucru este CS50.