[MUSIC JOC] 

DOUG LLOYD: OK, deci la acest punct în curs, am acoperit o mulțime de elementele de bază ale C. Știm multe despre variabile, tablouri, indicii, toate lucrurile bune. Acestea sunt tot felul de construit pentru a vedea cum fundamentele, dar putem face mai mult, nu? Putem combina lucruri împreună în moduri interesante. 

Și așa să facem asta, să începem a se ramifica din ceea ce ne dă C, și să înceapă să creeze propria noastra de date Folosind aceste structuri de construcție blocuri impreuna pentru a face ceva într-adevăr valoros, util. O modalitate putem face acest lucru este pentru a vorbi despre colecții. Deci, până acum am avut un fel de date structură pentru reprezentarea colecții de valori, ca valori similare. Asta ar fi o matrice. Avem colectii de numere întregi, sau colecții de caractere și așa mai departe. 

Structuri sunt, de asemenea, un fel de date structură pentru colectarea de informații, dar nu e ca și cum de colectare a valorilor. De obicei amesteca diferite tipuri de date împreună în interiorul unui singur cutie. Dar nu e în sine folosit pentru a lanțului de împreună sau conectați împreună similare elemente, cum ar fi o serie. Matrice sunt foarte bune pentru Element privi în sus, dar amintesc că este foarte dificil pentru a introduce într-o matrice, dacă nu te introducerea la chiar la sfârșitul acestei matrice. 

Și cel mai bun exemplu am pentru că este un fel de introducere. Dacă vă amintiți videoclipul nostru pe sortare prin inserție, a existat o mulțime de cheltuieli implicate în a avea pentru a ridica elemente, și le-a schimba din drum pentru a se potrivi ceva în mijlocul matrice dumneavoastră. Arrays, de asemenea, suferă de o altă problemă, care este inflexibilitate. Când ne-am declara o matrice, avem o șansă ea. Noi ne să spun, vreau acest multe elemente. S-ar putea fi de 100, s-ar putea fie 1.000, s-ar putea fie x unde x este un număr care utilizatorul ne-a dat la un prompt sau la comanda line. 

Dar avem doar o singură lovitură de la ea, am nu ajung apoi să spun oh, de fapt, am nevoie de 101, sau am nevoie de X, plus 20. Prea târziu, am declarat deja matrice, și dacă doriți să obțineți 101 sau X plus 20, trebuie să declare o serie complet diferit, copia toate elementele matricei peste, iar apoi ne-am ajuns. Și ce dacă suntem din nou greșit, ceea ce dacă, de fapt avem nevoie de 102, sau x plus 40, trebuie să facem acest lucru din nou. Astfel încât acestea sunt foarte inflexibile pentru redimensionarea datelor noastre, dar dacă vom combina unele din elementele de bază pe care le-am deja învățat despre indicii și structuri, în special utilizarea de memorie dinamic alocare cu malloc, am poate pune aceste piese împreună Pentru a crea un date structure-- o Lista am putea say-- legate individual care ne permite să crească și micsora o colecție de valori și nu vom avea nici un spațiu irosit. 

Deci, din nou, noi numim această idee, această noțiune, o listă legată. În special, în acest film suntem vorbind despre lista individual legate, și apoi un alt videoclip vom vorbi liste despre legate de dublu, care este doar o variatie pe o temă aici. Dar o listă individual legat este format din noduri, noduri doar fiind un term-- abstract e doar ceva ce sun asta e un fel de structura, practic, eu sunt? Doar de gând să-l numesc un node-- și acest nod are doi membri, sau două domenii. Are date, de obicei o întreg, un float caracter, sau ar putea fi un alt tip de date care le-ați definit cu un def tip. Și conține un pointer la un alt nod de același tip. 

Deci avem două lucruri în interiorul acest nod, date și un pointer la un alt nod. Și dacă începe să vizualizeze aceasta, vă puteți gândi la asta ca un lanț de noduri care sunt conectate împreună. Avem primul nod, ea conține date, și un pointer la al doilea nod, care conține date, și un pointer la nodul treia. Și așa de aceea l-am o numim Lista legate, acestea sunt legate între ele. 

Ce face acest lucru special Structura nod arata ca? Ei bine, dacă vă amintiți de la videoclipul nostru pe definirea tipuri personalizate, cu tipul de def, putem defini o structure-- și tip defini o structură de genul asta. tyepdef struct sllist, și apoi eu sunt utilizând valoarea cuvântul aici arbitrar pentru a indica orice tip de date într-adevăr. Ai putea trece pe un număr întreg sau float, ai putea avea orice vrei. Nu este limitat la doar întregi, sau ceva de genul asta. Deci valoare nu este doar un arbitrară tip de date, și apoi un pointer la un alt nod de același tip. 

Acum, există un pic de captură aici cu definirea unei structuri atunci când este o structură de sine referențială. Trebuie să am o temporar nume pentru structura mea. La sfârșitul zilei I doresc în mod clar să-l numesc nod SLL, asta e în cele din urmă noul Nume componentă de definire mea tip, dar nu pot folosi nod SLL în mijlocul acestei. Motivul fiind, nu am a creat un nod de tip SLL numit până când am lovit acest ultim punct aici. Până în acel moment, trebuie să aibă un alt mod de a face referire la acest tip de date. 

Și aceasta este o auto tip de date referențială. Acesta, e un tip de date de o structură care conține o de date, și un pointer la un alt Structura de același tip. Așa că am nevoie pentru a putea să se refere la acest tip de date, cel puțin temporar, asa ca da o temporar Numele de struct sllist îmi permite să spun, atunci vreau o pointer la un alt sllist struct, o stea struct sllist, și apoi după ce am terminat definirea, Eu pot apela acum acest tip de un nod SLL. 

Deci, de aceea ai vedea acolo un nume temporar aici, dar un nume permanent aici. Uneori s-ar putea vedea definiții ale structurii, de exemplu, că nu sunt autoreferențiale, că Nu au un nume specificator aici. S-ar spune doar typedef struct, deschide bretele cret si apoi defini. Dar daca esti struct este de la sine referențial, așa cum aceasta este, trebuie să specificați o nume de tip temporar. Dar în cele din urmă, acum că am făcut acest lucru, ne putem referi doar pentru a aceste noduri, aceste unități, ca noduri SLL scopuri de restul acestui film. 

În regulă, deci știm cum să crea un nod listă legată. Știm cum să se definească o listă nod conectat. Acum, dacă vom începe folosindu-le pentru a colecta informații, există o serie de operațiuni noi trebuie să înțeleagă și să lucreze cu. Trebuie să știm cum să creați o listă legată din aer subțire. Dacă nu există nici o listă deja, vrem să înceapă o. Deci, avem nevoie pentru a putea pentru a crea o listă legată, avem nevoie pentru a căuta, probabil, prin lista de link-ul pentru a găsi un element căutăm. Avem nevoie pentru a putea insera lucruri noi in lista, vrem lista noastră să fie în măsură să crească. Și în mod similar, vrem să fie în măsură pentru a șterge lucruri din lista noastră, vrem lista noastră să fie în măsură să se micșoreze. Și la sfârșitul nostru programe, în special dacă vă reamintesc că suntem alocarea dinamică de memorie pentru a construi aceste liste de obicei, vrem pentru a elibera toate că memoria când am terminat de lucru cu ea. Și așa trebuie să fie în măsură pentru a șterge o întreaga listă legate într-o singură lovitură nu. Deci, haideți să mergem prin unele dintre aceste operațiuni si cum am putea le vizualiza, vorbind în codul pseudocod specific. Deci, ne-o dorim pentru a crea un Lista legate, asa ca poate ne doriți să definiți o funcție cu acest prototip. SLL stele nod, de a crea, și eu care trece într-un singur argument, unele date arbitrare introduceți din nou, de un anumit tip de date arbitrare. Dar eu sunt returning-- această funcție ar trebui să întoarcă la mine un pointer, pentru un individual Lista legate nod. Din nou, noi încercăm să creeze o listă legată din aer subțire, asa ca am nevoie de un pointer la această listă, atunci când am terminat. 

Deci, ce sunt etapele implicate aici? Ei bine, primul lucru sunt de gând să faci este dinamic aloca spațiu pentru un nou nod. Din nou, suntem o crearea de subțire aer, așa că trebuie să spațiu malloc pentru ea. Și, desigur, imediat după ce am malloc, vom verifica întotdeauna să ne asigurăm că ne pointer-- nu am reveni nul. Pentru că dacă vom încerca și deferență un pointer nul, vom suferi o segfault si nu vrem asta. 

Apoi ne-am dori să completați câmpul, dorim pentru a inițializa câmpul valoric și inițializa câmpul următor. Și apoi ne-o dorim în cele din urmă ca sa-- Funcția prototip indicates-- vrem pentru a reveni un pointer la un nod SLL. Deci, ce face acest arata vizual? Ei bine, în primul rând vom dinamic aloca spațiu pentru un nou nod SLL, asa ca am malloc-- asta e o reprezentare vizuală din nodul tocmai am creat. Si vom verifica pentru a vă asigura nu este null-- în acest caz, imaginea nu ar avea apărut în cazul în care a fost nul, ne-ar fi rămas fără memorie, asa ca suntem bine să plec acolo. Deci, acum suntem la pasul C, inițializa câmpul valoare noduri. Ei bine, pe baza această funcție apel Sunt folosind aici, arata ca vreau sa trec la 6, așa că vom 6 în câmpul valoric. Acum, inițializa câmpul următor. Ei bine, ce am de gând să fac acolo, nu este nimic următoare, dreapta, acesta este singurul lucru pe listă. Deci, ce e următorul lucru pe lista? 

Nu ar trebui să punct la nimic, chiar. Nu e nimic altceva acolo, astfel încât ceea ce este conceptul știm de care este nothing-- indicii la nimic? Ar trebui să fie, poate, ne-o dorim pentru a pune un pointer nul acolo, și voi reprezintă nul pointer ca doar o cutie roșie, nu putem merge mai departe. După cum vom vedea un pic mai târziu, vom avea în cele din urmă lanturi de săgeți de conectare aceste noduri împreună, dar atunci când a lovit casetă roșie, care este nul, nu putem merge mai departe, asta e sfârșitul listei. 

Și, în fine, vrem doar să reveni un pointer la acest nod. Deci, vom numi noi, și va reveni noi astfel încât să poată fi utilizate în indiferent de funcția a creat. Deci nu vom merge, Am creat un individual Lista nod legat din aer subțire, iar acum avem o listă, putem lucra cu. 

Acum, să spunem că am deja au un lanț mare, și vrem să găsim ceva în ea. Și dorim o functie care va pentru a reveni adevărat sau fals, în funcție dacă o valoare există în această listă. Un prototip funcție, sau declarație pentru această funcție, ar putea arata ca astea-- bool găsi, și apoi ne-o dorim pentru a trece în două argumente. 

Primul, este un pointer la primul element al listei de legătura. Aceasta este de fapt ceva ce vei dori întotdeauna pentru a urmări, și de fapt ar putea fi ceva care tine chiar pus într-o variabilă globală. După ce ați creat o listă, tu mereu, mereu doresc pentru a urmări de foarte Primul element al listei. În acest fel puteți face referire la toate celelalte Elemente de doar după lanțul, fără a fi nevoie de a păstra pointeri intact la fiecare singur element. Trebuie doar pentru a ține evidența primul o în cazul în care acestea sunt toate legate împreună. 

Și apoi al doilea lucru suntem trece din nou este some-- arbitrar indiferent de tipul de date suntem cauta există în interiorul sperăm unul dintre nodurile din lista. Deci, care sunt pașii? Ei bine, primul lucru pe care îl facem este vom crea un pointer transversal arătând spre capul liste. Ei bine, de ce facem asta, deja au un pointer la cap liste, de ce nu ne mișcăm doar că unul pe aici? Ei bine, cum am spus doar, este foarte important pentru noi pentru a ține întotdeauna evidența foarte primul element din listă. Și așa e de fapt mai bine pentru a crea un duplicat de care, și de a folosi că pentru a muta în jurul valorii de așa că nu muta accidental departe, sau ne-am mereu au un pointer la un moment dat, care este chiar pe primul element al listei. Deci, este mai bine pentru a crea un al doilea pe care le folosim pentru a muta. 

Apoi, ne-am compara dacă câmpul valoare la acel nod este ceea ce căutați, și, dacă este nu, vom trece doar la nodul următor. Și noi continuăm să facem asta peste și peste și peste, până când vom găsi fie elementul, sau am lovit null-- am ajuns la sfârșitul listei și nu este acolo. Acest lucru ar trebui să sperăm sune un clopot pentru tine, ca doar de căutare liniară, suntem doar replicare în o structură listă individual legat loc de a folosi o matrice a face acest lucru. 

Deci, aici e un exemplu de o listă individual legat. Acesta este format din cinci noduri, și ne-am un pointer la șefului Lista, care se numește listă. Primul lucru pe care doriți să faceți este din nou, a crea acel pointer traversarea. Deci, acum avem două indicii acest punct de același lucru. 

Acum, observați aici, de asemenea,, nu am Trebuie să malloc orice spațiu pentru Trav. Nu am spus trav egal malloc ceva, acel nod există deja, acest spațiu în memorie există deja. Deci, tot eu sunt de fapt face este crearea de un alt pointer la ea. Nu mă mallocing o suplimentare spațiu, trebuie doar acum două indicii arătând spre același lucru. 

Deci, este de 2 ceea ce caut? Ei bine, nu, astfel încât în ​​loc eu sunt va trece la următorul. Deci, practic, aș spune, trav Trav egal următor. Este de 3 ceea ce caut, nr. Așa că am continua să meargă prin, în cele din urmă până la ajunge la 6, care este ceea ce caut pentru bazate pe apelul funcției Am la partea de sus acolo, și așa am terminat. 

Acum, ce se întâmplă dacă elementul sunt căutați nu este în listă, este încă de gând să lucreze? Ei bine, observați că lista aici este subtil diferit, și acest lucru este un alt lucru care este important, cu liste legate, nu trebuie să păstreze le în orice ordine special. Puteți, dacă doriți, dar este posibil să fi observat deja că nu suntem urmărirea ce element de numărul suntem la. 

Și asta e un fel de un comerț pe care le au cu lista legate versuri tablouri, este că nu avem mai cu acces aleator. Nu putem spune doar, vreau pentru a merge la elementul 0th, sau elementul de matrice a 6-mea, care pot face într-o matrice. Nu pot să spun că vreau să merg la Element 0th, sau 6a elementul, sau elementul 25 lista mea legată, nu exista nici index asociate cu acestea. Și așa nu contează cu adevărat dacă ne-am păstra lista noastră în ordine. Dacă doriți să vă cu siguranță pot, dar nu e nici un motiv pentru care au nevoie pentru a fi păstrate în orice ordine. Deci, din nou, să încercăm și găsi 6 în această listă. Ei bine, vom începe de la începând, nu găsim 6, si atunci nu continua găsirea 6, până când vom ajunge în cele din urmă aici. Deci, chiar de puncte acum trav la nodul conținând 8, iar șase nu este acolo. 

Deci, urmatorul pas ar fi pentru a merge la indicatorul următor, așa spun trav Trav egal următor. Ei bine, trav viitoare, indicat de caseta de culoare roșie nu, este nul. Deci nu e nicăieri în altă parte a du-te, și așa mai departe în acest moment putem concluziona că am ajuns sfârșitul listei de legătura, și 6 nu este acolo. Și ar fi returnat fals în acest caz. 

OK, cum putem introduce o nouă nod în lista legat? Deci am fost capabili de a crea o listă legată de nicăieri, dar, probabil, vrem să construi un lanț și nu a crea o grămadă de liste distincte. Vrem să avem o listă care are o grămadă de noduri în ea, nu o grămadă de liste cu un singur nod. Deci, nu putem ține folosind Creare Funcția am definit mai devreme, acum ne doriți să inserați într-un Lista care există deja. 

Deci acest caz, vom pentru a trece în două argumente, indicatorul la cap de care Lista pe care ne-o dorim pentru a adăuga la legat. Din nou, de aceea este atât de important ca noi mereu urmări, pentru că e singurul mod cu adevarat trebuie să se refere la întreaga listă este doar de un pointer la primul element. Deci, vrem să treacă într-o pointer la care prim element, si indiferent de valoarea am doriți să adăugați la lista. Și, eventual, această funcție este de gând să se întoarcă un pointer la noul șef al unei liste legate. 

Care sunt etapele implicate aici? Ei bine, la fel ca și cu crearea, avem nevoie pentru a aloca dinamic spațiu pentru un nou nod, și verificați pentru a face sigur că nu a alerga afară de memorie, din nou, pentru că suntem folosind malloc. Apoi, ne-o dorim pentru a popula și introduceți nodul, asa ca pune numărul, indiferent de val este, în nodul. Vrem să introduceți nodul la începutul listei de legătura. 

Exista un motiv pentru care am vreau să fac asta, și ar putea fi în valoare de a lua un al doilea pentru a întrerupe videoclipul aici, și cred că de ce aș vrea să introduce la începutul unui legat Lista. Din nou, am menționat mai devreme că aceasta nu prea contează dacă am păstra în orice ordine, astfel poate că e un indiciu. Și ai văzut ce se va întâmpla dacă am a vrut sa-- sau de la doar o secundă Acum, când am fost de gând prin căutare vă ar putea vedea ce s-ar putea întâmpla dacă am încercat pentru a insera la sfârșitul listei. Pentru ca nu avem o pointer la sfârșitul listei. 

Deci motivul pentru care mi-aș dori pentru a insera la început, este pentru că eu pot face imediat. Am un pointer la început, și vom vedea acest lucru într-un vizual într-o secundă. Dar dacă vreau să insera la sfârșitul anului, Trebuie să începem cu începutul, traversa tot drumul la scop, și apoi tac pe. Deci aceasta ar însemna că inserarea la sfârșitul listei ar deveni un o de n funcționare, merge înapoi la discuția noastră de complexitate de calcul. Ar deveni un o operație de n, în cazul în care ca lista sa mărit, și mai mare, și mai mare, acesta va deveni mai mult și mai dificil de tac ceva pe la sfârșitul anului. Dar este întotdeauna foarte ușor de tac ceva pe la început, esti mereu la început. 

Și vom vedea o vizuală a acestui nou. Și apoi o dată am terminat, o dată am introdus noul nod, vrem să se întoarcă la indicatorul nostru noul șef al unei liste legate, care deoarece suntem introducerea la incepand, va fi de fapt un pointer la nodul ne-am creat. Să vizualiza acest lucru, pentru că eu cred că va ajuta. 

Deci, aici e lista noastra, este alcătuită din patru elemente, un nod care conține 15, ceea ce indică un nod conținând 9, care indică un nod conține 13, ceea ce indică un nod care conține 10, care are nulul pointer ca următoarea pointer astfel că la scos din lista. Deci, vrem să inserați un nod nou cu valoarea de 12 la începutul acestui Lista, ce facem? Ei bine, în primul rând ne-am malloc spațiu pentru nod, și apoi am pus 12 acolo. 

Deci, acum am ajuns la un ne- punctul de decizie, nu? Avem un cuplu de indicii care am putea muta, care ar trebui să ne mutăm mai întâi? Ar trebui să facem 12 puncte la noul șef al list-- sau scuză-mă, trebuie să facem 12 punctul la cap vechi listei? Sau ar trebui să spunem că Lista acum începe la 12. Există o distincție acolo, si ne vom uita la ce se întâmplă cu atât într-o secundă. 

Dar aceasta duce la o mare subiect de bara laterală, care este faptul că una dintre cele dificile lucruri cu liste legate este de a asigura indicii în ordinea corectă. Dacă mutați lucrurile de ordine, puteți ajunge accidental orphaning restul listei. Și aici este un exemplu de acest lucru. Deci, să mergem cu ideea de-- Ei bine, tocmai am creat 12. Știm 12 va fi noul șef al listei, și așa că de ce să nu ne-am muta Lista indicatorul la punctul acolo. 

OK, așa că e bine. Deci, acum cazul în care nu 12 Următorul punct? Adică, vizual putem vedea că va indica 15, ca oameni este foarte evident pentru noi. Cum știe computer? Noi nu avem nimic mai indică spre 15, nu? 

Am pierdut orice capacitate de a se referă la 15. Nu putem spune noi săgeata de lângă egali ceva, nu e nimic acolo. De fapt, ne-am orfani restul listei de a face acest lucru, ne-am rupt accidental lanțul. Și cu siguranță nu vreau să fac asta. 

Deci, să ne întoarcem și să încercați din nou. Poate că ceea ce trebuie să facă este de a stabili 12 de pe lângă indicatorul la vechiul cap al listei prima, atunci ne putem muta în lista de peste. Și, de fapt, că este ordinea corectă pe care le trebuie să urmați atunci când suntem de lucru cu lista individual legat. Noi mereu doriți să conectați element nou în listă, înainte vom lua acest tip de pas important de schimbare în cazul în care capul listei legat este. Din nou, asta e un lucru fundamental, nu vrem să-și piardă urmări de ea. 

Deci, vrem să ne asigurăm că totul este legat împreună, înainte de a ne muta ca pointer. Și așa ar fi ordinea corectă, care urmează să se conecteze 12 la lista, apoi spune că lista începe un 12. Dacă am declarat că lista incepe de la 12 si apoi a încercat să se conecteze 12 la lista, am văzut deja ce se întâmplă. Pierdem lista din greșeală. 

OK, cu atât mai mult un lucru pentru a vorbi despre. Ce se întâmplă dacă vrem să scăpăm de un întreg listă de legat la o dată? Din nou, suntem mallocing toate acest spațiu, și așa ne-am Trebuie să-l elibereze, atunci când am terminat. Deci, acum vrem să ștergeți întreaga listă legată. Ei bine, ce vrem sa facem? 

Dacă am ajuns la indicatorul nul, am vrea să se oprească, în caz contrar, ștergeți doar restul de listă și apoi mă eliberezi. Ștergeți restul listei, și apoi elibera nodul curent. Ce face asta suna ca, ce tehnica au am vorbit nu despre anterior ca suna ca? Șterge toată lumea, atunci întoarce și șterge-mă. 

Asta e recursivitate, am facut problemă un pic mai mic, ce spunem șterge toată lumea altceva, atunci poți să-mi șterge. Și mai departe pe drum, acel nod va spune, șterge toată lumea. Dar în cele din urmă vom ajunge la punct în care lista este nul, și asta e cazul nostru de bază. 

Deci, haideți să aruncăm o privire la acest lucru, și modul în care acest lucru ar putea să funcționeze. Deci, aici e lista noastra, e la fel lista vorbeam despre, și nu există trepte. Există o mulțime de text aici, dar sperăm vizualizarea va ajuta. 

Asa ca am have-- și, de asemenea, am tras up cadre stiva nostru ilustrare din videoclipul nostru pe stive de apel, și sperăm că toate acestea împreună vă va arăta ceea ce se întâmplă. Deci, aici e codul nostru pseudocod. Dacă vom ajunge la un nul pointer, opri, în caz contrar, șterge restul listei, apoi elibera nodul curent. Deci, chiar acum, list-- indicatorul care suntem trecând în a distruge puncte pentru a 12. 12 nu este un pointer nul, deci suntem merge pentru a șterge restul listei. 

Ce este ștergerea restul dintre noi implicat? Ei bine, aceasta înseamnă a face o apel pentru a distruge, spunând că 15 este începutul restul listei vrem să distrugă. Și astfel chemarea de a distruge 12 este un fel de în așteptare. E înghețat acolo, de așteptare pentru apel pentru a distruge 15, pentru a termina treaba. 

Ei bine, 15 nu este un pointer nul, și așa că o să spun, bine, bine, șterge restul listei. Restul listei începe la 9, si asa ca vom doar așteptați până când ștergeți toate că chestii, apoi te întorci și șterge-mă. Ei bine, 9 va spune, bine, Eu nu sunt un pointer nul, astfel încât să ștergeți restul lista de aici. Și așa că încercați și de a distruge 13. 13 spune, eu nu sunt pointer null, același lucru, trece dolar. 10 nu este pointer nul, 10 conține un pointer nul, dar 10 nu este un este null pointer chiar acum, și așa trece dolar prea. 

Și acum lista puncte acolo, ea într-adevăr ar indica some-- dacă am avut mai mult spațiu în imagine, ar indica un spațiu aleatoare care nu știm ce este. Este indicatorul nul, deși, lista este literalmente acum setat e valori nule. Este arătând chiar în interiorul cutie roșie. Am ajuns la un pointer nul, astfel încât putem opri, și am terminat. 

Și astfel încât cadru violet este now-- la Partea de sus a stack-- care este cadrul activ, dar se face. Dacă am ajuns un pointer nul, opri. Noi nu facem nimic, ne-am nu poate elibera un pointer nul, nu am nici o malloc spațiu, și așa am terminat. Astfel încât cadru funcție este distrus, iar noi resume-- ne ridica unde am plecat off cu următoarea cea mai mare cel care este acest cadru albastru închis aici. Așa că am ridica dreapta unde am rămas. Am eliminat restul Lista deja, asa ca acum suntem merge pentru a elibera nodurile curente. Deci, acum putem elibera acest nod, iar acum am ajuns la sfârșitul funcției. Și astfel încât cadru functie este distrus, si ne-am ridica la cel albastru deschis. 

Deci, says-- am deja done-- ștergerea restul listei, așa elibera nodul curent. Și acum cadrul galben este din nou pe partea de sus a stivei. Și așa după cum vedeți, suntem acum distruge lista de la dreapta la stânga. 

Ce s-ar fi întâmplat, însă, dacă am fi făcut lucruri în mod greșit? La fel ca atunci când am încercat adăugarea unui element. Dacă ne-am dat peste cap lanț, în cazul în care nu am conecta indicii în ordinea corectă, dacă doar eliberat primul element, dacă ne-am eliberat cap de listă, acum ne au nici o modalitate de a face referire la restul listei. Și așa ne-am fi totul orfani, am fi avut ce-i numit o scurgere de memorie. Dacă vă amintiți de la videoclipul nostru privind alocarea dinamică a memoriei, asta nu e lucru foarte bun. 

Deci, după cum am spus, nu sunt mai multe operațiuni de care avem nevoie pentru a utiliza pentru a lucra cu lista legate în mod eficient. Și este posibil să fi observat că omis unul, ștergerea un singur element dintr-o legătură Lista. Motivul pentru care am făcut asta este de fapt un fel de dificil să se gândească la cum să ștergeți un singur element dintr-o individual Lista legate. Trebuie să fim capabili să săriți peste ceva în listă, care înseamnă ajungem la o vom point-- doriți să ștergeți acest node-- dar în scopul de a face astfel încât să nu pierde nici o informație, avem nevoie pentru a conecta acest nod aici, aici. 

Deci, probabil, am făcut-o greșit din punct de vedere vizual. Deci suntem la începutul nostru Lista, suntem procedând prin, vrem să ștergeți acest nod. Dacă ne-am șterge, am rupt lanțul. Acest nod aici se referă la orice altceva, conține lanțul de acum înainte. 

Deci, ceea ce avem nevoie pentru a face de fapt după ce vom ajunge la acest punct, este că trebuie să pas înapoi, și conecta acest nod pe la acest nod, astfel încât să putem șterge apoi cel din mijloc. Dar listele individual legate nu ne oferă o modalitate de a merge înapoi. Așa că trebuie să fie păstrați două indicii, și a le muta un fel de pas off, una în spatele altul ca mergem, sau ajunge la un punct și apoi trimite un alt pointer prin. Și, după cum se poate vedea, poate obține un pic murdar. Din fericire, ne-am un alt mod de a rezolva asta, atunci când vorbim despre liste de două ori legate. 

Sunt Doug Lloyd, aceasta este CS50.