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