[RIPRODUZIONE DI BRANI MUSICALI] 

DOUG LLOYD: OK, così a questo punto nel corso, abbiamo coperto un sacco di basi di C. Sappiamo molto di variabili, gli array, puntatori, tutta quella roba buona. Questi sono tutti i tipi di costruito per vedere come i fondamentali, ma possiamo fare di più, giusto? Possiamo combinare le cose insieme in modi interessanti. 

E così facciamo che, cominciamo di espandersi di ciò che ci dà C, e iniziare a creare la nostra dati strutture con questi edifici blocchi insieme per fare qualcosa veramente prezioso, utile. Un modo in cui possiamo farlo è per parlare di collezioni. Così finora abbiamo avuto un tipo di dati struttura per rappresentare collezioni di come i valori, valori simili. Sarebbe un array. Abbiamo collezioni di numeri interi, o raccolte di caratteri e così via. 

Le strutture sono anche una sorta di dati Struttura per la raccolta di informazioni, ma non è per la raccolta come valori. Di solito mescola diversi tipi di dati insieme all'interno di un unico pacchetto. Ma non è per sé utilizzato per concatenare o collegare insieme simile elementi, come un array. Gli array sono grandi per elemento guardare in alto, ma il richiamo che è molto difficile inserire in un array, a meno che non ci stiamo inserendo in alla fine di tale matrice. 

E il miglior esempio ho per questo è insertion sort. Se vi ricordate il nostro video su insertion sort, c'era un sacco di spesa coinvolti nell'avere per raccogliere gli elementi, e li sposterà fuori strada per adattarsi qualcosa nel mezzo dell'array. Array soffrono anche di un altro problema, che è mancanza di flessibilità. Quando si dichiara un array, otteniamo un solo colpo a questo. Arriviamo a dire, voglio questo molti elementi. Potrebbe essere 100, potrebbe essere 1.000, potrebbe essere x dove x è un numero che l'utente ci ha dato al prompt o al comando Linea. 

Ma abbiamo solo un colpo a questo, abbiamo Non capisco per poi dire oh, in realtà io necessaria 101, o avevo bisogno di x più 20. Troppo tardi, abbiamo già dichiarato la matrice, e se vogliamo ottenere 101 o x più 20, dobbiamo dichiarare una serie completamente diversa, copiare tutti gli elementi della matrice sopra, e poi abbiamo abbastanza. E se siamo di nuovo sbagliato, cosa se abbiamo effettivamente bisogno 102, o x più 40, dobbiamo farlo di nuovo. Quindi sono molto poco flessibile per il ridimensionamento nostri dati, ma se uniamo insieme alcuni dei principi fondamentali che abbiamo già imparato a conoscere i puntatori e delle strutture, in particolare utilizzando la memoria dinamica assegnazione con malloc, ci può mettere insieme questi pezzi per creare nuovi dati structure-- un concatenata lista potremmo say-- che ci permette di crescere e compattare un insieme di valori e non avremo alcun spreco di spazio. 

Così ancora una volta, che noi chiamiamo questa idea, questa nozione, un elenco collegato. In particolare, in questo video siamo parlando di lista concatenata, e poi un altro video ne parleremo liste su doppiamente collegate, che è solo una variazione sul tema qui. Ma una lista concatenata è composto da nodi, nodi solo di essere un term-- astratto è solo una cosa che sto chiamando che è una sorta di struttura, in fondo, io sono? Basta andare a chiamare un node-- e questo nodo ha due membri, o due campi. Ha i dati, di solito un integer, float un personaggio, o potrebbe essere qualche altro tipo di dati che avete definito con un tipo def. E contiene un puntatore altro nodo dello stesso tipo. 

Quindi abbiamo due cose dentro di questo nodo, i dati e un puntatore ad un altro nodo. E se si inizia a visualizzare i questo, si può pensare a questo proposito come una catena di nodi che sono collegati tra loro. Abbiamo il primo nodo, contiene dati e un puntatore al secondo nodo, che contiene dati e un puntatore al terzo nodo. Ed è per questo che lo chiamiamo lista collegata, stanno collegati tra loro. 

Che cosa significa questo speciale struttura del nodo assomigliare? Beh, se vi ricordate dal nostro video definire tipi personalizzati, con il tipo di definizione, possiamo definire un structure-- e digitare definire una struttura come questa. tyepdef struct sllist, e poi io sono utilizzando il valore parola qui arbitrariamente per indicare qualsiasi tipo di dati davvero. Si potrebbe passare un intero o float, si potrebbe avere quello che vuoi. Non è limitato al solo interi, o qualcosa di simile. Quindi il valore è solo un arbitrario il tipo di dati, e quindi un puntatore ad un altro nodo dello stesso tipo. 

Ora, c'è un po 'di cattura qui con definenti una struttura quando si tratta di una struttura auto referenziale. Devo avere una temporanea nome per la mia struttura. Alla fine della giornata ho vuole chiaramente chiamarlo nodo SLL, che è in ultima analisi, il nuovo nome parte della mia definizione del tipo, ma non posso usare il nodo sll nel mezzo di questo. Il motivo è, non ho creato un tipo chiamato nodo sll fino a quando mi ha colpito questo ultimo punto qui. Fino a quel punto, devo avere un altro modo per fare riferimento a questo tipo di dati. 

E questo è un auto tipo di dati di riferimento. It; s un tipo di dati di un struttura che contiene un dato, e un puntatore a un'altra struttura dello stesso tipo. Così ho bisogno di essere in grado di fare riferimento a questo tipo di dati almeno temporaneamente, così dando una temporanea nome di struct sllist mi permette di dire che voglio poi un puntatore ad un'altra sllist struct, una stella struct sllist, e poi dopo che ho completato la definizione, Ora posso chiamare questo tipo un nodo sll. 

Ecco, questo è il motivo per cui si vede non c'è un nome temporaneo qui, ma un nome permanente qui. A volte si potrebbe vedere definizioni di struttura, per esempio, che non sono autoreferenziale, che non hanno un nome identificatore qui. Sarebbe solo dire typedef struct, aprire parentesi graffa e quindi definirlo. Ma se siete struct è auto referenziale, come questo è, è necessario specificare un Nome tipo temporaneo. Ma alla fine, ora che abbiamo fatto questo, possiamo solo fare riferimento al questi nodi, queste unità, come nodi SLL a fini del resto di questo video. 

Va bene, quindi sappiamo come creare un nodo lista collegata. Sappiamo come definire un nodo lista collegata. Ora, se stiamo per iniziare che li utilizzano per raccogliere informazioni, ci sono un paio di operazioni che bisogno di capire e lavorare con. Abbiamo bisogno di sapere come creare una lista collegata dal nulla. Se non c'è la lista già, vogliamo iniziare uno. Quindi abbiamo bisogno di essere in grado per creare una lista collegata, abbiamo bisogno di cercare probabilmente attraverso l'elenco di link per trovare un elemento che stiamo cercando. Dobbiamo poter inserire cose nuove nella lista, vogliamo che la nostra lista per essere in grado di crescere. E allo stesso modo, noi vogliamo essere in grado per cancellare le cose dalla nostra lista, vogliamo che la nostra lista per essere in grado di ridursi. E alla fine della nostra programmi, in particolare se vi ricordate che siamo allocare dinamicamente la memoria per costruire queste liste tipicamente, vogliamo liberare tutta questa memoria quando avremo finito a lavorare con esso. E così abbiamo bisogno di essere in grado di eliminare un tutta la lista collegata a un sicuro colpo solo. Quindi cerchiamo di passare attraverso alcune di queste operazioni e come possiamo visualizzarli, a parlare in codice pseudocodice in particolare. Quindi, vogliamo creare un lista collegata, così forse noi voler definire una funzione con questo prototipo. SLL nodo stella, creare, e sto passando in un solo argomento, alcuni dati arbitrari digitare nuovamente, di un certo tipo di dati arbitrari. Ma sto returning-- questa funzione dovrebbe tornare a me un puntatore, per un singolarmente nodo lista collegata. Anche in questo caso, stiamo cercando di creare una lista collegata dal nulla, quindi ho bisogno di un puntatore a quella lista quando ho finito. 

Ma quali sono i passi necessari qui? Beh, prima cosa di cui sono intenzione di fare è dinamicamente allocare spazio per un nuovo nodo. Ancora una volta, stiamo creando fuori sottile aria, quindi abbiamo bisogno di spazio malloc per essa. E, naturalmente, subito dopo che malloc, abbiamo sempre controlliamo a fare in modo che il nostro pointer-- non abbiamo ottenuto indietro nulla. Perché se cerchiamo di deferenza un puntatore nullo, stiamo andando a subire un segfault e non vogliamo questo. 

Poi vogliamo compilare il campo, vogliamo inizializzare il campo del valore e inizializzare il campo successivo. E poi vogliamo a-- alla fine come il prototipo di funzione indicates-- vogliamo per restituire un puntatore ad un nodo sll. Quindi, ciò che rende questo aspetto visivo? Beh, prima che andremo a dinamicamente allocare spazio per un nuovo nodo sll, così abbiamo malloc-- che è una rappresentazione visiva del nodo che abbiamo appena creato. E noi verifichiamo non è null-- in questo caso, l'immagine non avrebbe mostrato su se fosse nullo, avremmo esaurito la memoria, così stiamo bene di andare lì. Così ora siamo alla fase C, inizializzare il campo del valore nodi. Ebbene, sulla base di questa funzione Chiamo sto usando qui, sembra che io voglio passare a 6, Così io 6 nel campo del valore. Ora, inizializzare il campo successivo. Beh, quello che sto andando a fare lì, non vi è nulla accanto, a destra, questa è l'unica cosa nella lista. Allora, qual è la prossima cosa nella lista? 

Non dovrebbe puntare a qualsiasi cosa, a destra. Non c'è niente altro là, così che cosa è il concetto che sappiamo di che è nothing-- puntatori a nulla? Dovrebbe essere forse vogliamo di mettere un puntatore nullo lì, e io rappresento il nulla puntatore come solo una scatola rossa, non possiamo andare oltre. Come vedremo un po 'più tardi, avremo infine catene di frecce di collegamento questi nodi insieme, ma quando si colpisce la scatola rossa, che è nullo, non possiamo andare oltre, questa è la fine della lista. 

E, infine, vogliamo solo restituire un puntatore a questo nodo. Così che chiameremo nuovo, e tornerà nuovo in modo che possa essere utilizzato in qualsiasi funzione creata. Così ci si va, Abbiamo creato un singolarmente nodo lista collegata dal nulla, e ora abbiamo una lista possiamo lavorare con. 

Ora, diciamo che già avere una grande catena, e vogliamo trovare qualcosa. E noi vogliamo una funzione che sta andando a restituire true o false, a seconda se esiste un valore in quella lista. Un prototipo di funzione, o dichiarazione per quella funzione, potrebbe apparire come questo-- Bool trovare, e poi vogliamo passare due argomenti. 

Il primo, è un puntatore al primo elemento della lista collegata. Questo è in realtà qualcosa che ti sempre voglia di tenere traccia di, e in realtà potrebbe essere qualcosa che ancora messo in una variabile globale. Una volta creata una lista, sempre, sempre vuole tenere traccia del molto primo elemento della lista. In questo modo è possibile fare riferimento a tutti gli altri gli elementi da solo seguendo la catena, senza dover tenere puntatori intatto per ogni singolo elemento. Hai solo bisogno di tenere traccia del primo uno se sono tutti collegati tra loro. 

E poi la seconda cosa stiamo passando di nuovo è some-- arbitrariamente qualunque sia il tipo di dati che siamo cercando c'è dentro di speriamo che uno dei nodi della lista. Ma quali sono i passaggi? Beh, la prima cosa che facciamo è creiamo un puntatore trasversale che punta alla testa liste. Beh, perché lo facciamo, abbiamo già un puntatore alla testa liste, perché non solo che muoviamo un giro? Beh, come ho appena detto, è davvero importante per noi tenere sempre traccia del primo elemento della lista. E così in realtà è meglio creare un duplicato di questo, e l'uso che per muoversi quindi non abbiamo mai spostare accidentalmente via, o sempre avere un puntatore ad un certo punto che è proprio sul primo elemento della lista. Quindi è meglio creare un secondo quella che usiamo per muoversi. 

Poi abbiamo appena confrontare se il campo di valore a quel nodo è quello che stiamo cercando, e se è Non ci basta spostare al nodo successivo. E continuiamo a farlo oltre, e oltre, e oltre, fino a quando non sia trovato l'elemento, o ci ha colpito null-- abbiamo raggiunto la fine della lista e non è lì. Questo dovrebbe auspicabilmente suonare un campanello a voi come appena ricerca lineare, stiamo solo replicando in una struttura della lista concatenata invece di utilizzare una vasta gamma di farlo. 

Quindi, ecco un esempio di una lista concatenata. Questo consiste cinque nodi, e abbiamo un puntatore alla testa della lista, che si chiama lista. La prima cosa che vogliamo fare è ancora una volta, creare tale puntatore attraversamento. Così abbiamo ora due puntatori che scegliere la stessa cosa. 

Ora, si noti anche qui, non l'ho fatto devono malloc qualsiasi spazio per trav. Non ho detto trav uguale malloc qualcosa, quel nodo esiste già, che lo spazio nella memoria esiste già. Quindi tutto quello che sto facendo è in realtà la creazione di un altro puntatore a esso. Non sto mallocing un ulteriore spazio, basta avere ora due puntatori indicando la stessa cosa. 

Così è 2 quello che sto cercando? Beh, no, così invece sono andando a passare al successivo. Quindi, fondamentalmente direi, trav uguale trav prossimo. È 3 quello che sto cercando, no. Così continuo a andare attraverso, fino alla fine arrivare a 6, che è quello che sto cercando in base a una chiamata di funzione Ho in cima lì, e così ho finito. 

Ora, che cosa se l'elemento sono cercando non è presente nella lista, sta ancora andare a lavorare? Beh, si noti che la lista qui è sottilmente diverso, e questa è un'altra cosa che è importante con liste collegate, non c'è bisogno di conservare li in un ordine particolare. Si può se si vuole, ma avrete già notato che non stiamo tenendo traccia di che numero elemento siamo al. 

E questo è una sorta di un commercio che noi avere con lista collegata versi array, è vero non abbiamo accesso casuale più. Non possiamo solo dire, voglio per andare all'elemento 0, o il 6 ° elemento della mia matrice, che posso fare in un array. Non posso dire che voglio andare al Elemento 0i, o il sesto elemento, o l'elemento 25 della mia lista collegata, non c'è alcun indice ad essi associati. E così non ha molta importanza se conserviamo la nostra lista in ordine. Se vuoi te certamente possibile, ma c'è alcun motivo per cui hanno bisogno di conservati in qualsiasi ordine. Così ancora una volta, proviamo e trovare 6 in questa lista. Bene, iniziamo a inizio, non troviamo 6, e allora non continuiamo a trovare 6, fino a quando alla fine abbiamo arrivare a qui. Così giusti punti ora trav al nodo contenenti 8, e sei non è lì. 

Quindi il passo successivo sarebbe per andare al puntatore prossimo, così dicono trav uguale trav prossimo. Ebbene, trav successiva, indicata da la scatola rossa c'è, è nullo. Quindi non c'è nessun altro posto dove andare, e quindi a questo punto possiamo concludere che abbiamo raggiunto alla fine della lista collegata, e 6 non è in là. E sarebbe restituito falso in questo caso. 

OK, come possiamo inserire un nuovo nodo alla lista linkata? Così siamo stati in grado di creare una lista collegata dal nulla, ma probabilmente vogliamo costruire una catena e non creare un gruppo di liste distinte. Vogliamo avere una lista che ha un sacco di nodi in esso, non un gruppo di liste con un singolo nodo. Così non possiamo continuare ad usare la Creazione Funzione abbiamo definito in precedenza, ora siamo vuole inserire in un lista che già esiste. 

Quindi questo caso, stiamo andando per passare a due argomenti, il puntatore alla testa di tale lista che vogliamo aggiungere alla collegata. Anche in questo caso, è per questo che è così importante che abbiamo sempre tenere traccia di esso, perché è l'unico modo per davvero devono riferirsi alla completa lista è semplicemente un puntatore al primo elemento. Quindi vogliamo passare a una puntatore a quel primo elemento, e qualunque valore che vuole aggiungere alla lista. E alla fine di questa funzione sta per restituire un puntatore per il nuovo capo di una lista collegata. 

Quali sono i passi necessari qui? Beh, proprio come con creare, abbiamo bisogno di allocare dinamicamente lo spazio per un nuovo nodo, e controllare per sicuri di non esaurire la memoria, ancora una volta, perché stiamo usando malloc. Poi vogliamo popolare e inserire il nodo, così si può mettere il numero, qualunque val è, nel nodo. Vogliamo inserire il nodo All'inizio della lista collegata. 

C'è una ragione che io vuole fare questo, ed è potrebbe essere la pena di prendere un secondo per mettere in pausa il video qui, e riflettere sul perché dovrei voler inserire all'inizio di una collegata lista. Ancora una volta, ho detto in precedenza che in realtà non importa se conserviamo in alcun ordine, quindi forse questo è un indizio. E avete visto che cosa accadrebbe se noi voluto a-- o da solo un secondo fa, quando stavamo andando attraverso ricerca si poteva vedere quello che potrebbe succederebbe se stavamo cercando inserire alla fine della lista. Perché noi non abbiamo un puntatore alla fine della lista. 

Quindi la ragione che vorrei inserire all'inizio, è perché posso farlo subito. Ho un puntatore all'inizio, e vedremo questo in un visivo in un secondo. Ma se voglio inserire alla fine, Devo cominciare dall'inizio, attraversare fino al fine, e poi virare su. Quindi ciò significherebbe che inserendo alla fine della lista sarebbe diventato un o di n operazione, andando indietro alla nostra discussione di complessità computazionale. Sarebbe diventato un o di un'operazione n, dove come la lista ha ottenuto più grande, e più grande, e più grande, che diventerà sempre più difficile da virare qualcosa on alla fine. Ma è sempre molto facile virare qualcosa all'inizio, sei sempre all'inizio. 

E vedremo di nuovo una visuale di questo. E poi una volta che abbiamo finito, una volta abbiamo inserito il nuovo nodo, vogliamo tornare il nostro puntatore il nuovo capo di una lista collegata, che dal momento che stiamo inserendo in inizio, sarà effettivamente un puntatore al nodo appena creato. Cerchiamo di visualizzare questo, perché penso che ti aiuto. 

Quindi, ecco la nostra lista, si compone di quattro elementi, un nodo contenente 15, che punta a un nodo contenente 9, che punta a un nodo contenente 13, che punti a un nodo che contiene 10, che ha il nullo puntatore come sua prossima puntatore di modo che è la fine della lista. Quindi vogliamo inserire un nuovo nodo con il valore 12 all'inizio di questo lista, cosa facciamo? Beh, per prima cosa malloc spazio per il nodo, e poi abbiamo messo 12 in là. 

Così ora abbiamo raggiunto un punto di decisione, giusto? Abbiamo un paio di puntatori che potremmo muoviamo, quale dobbiamo passare prima? Dobbiamo fare 12 punti per il nuovo capo del list-- o mi scusi, dobbiamo fare 12 puntare alla vecchia testa della lista? O dovremmo dire che la lista ora inizia alle 12. C'è una distinzione lì, e vedremo a ciò che accade con entrambi in un secondo. 

Ma questo porta ad un grande tema per la barra laterale, che è quello della le cose più delicate con liste collegate è quello di organizzare i puntatori nell'ordine corretto. Se si sposta le cose in ordine, si può finire accidentalmente orfano il resto della lista. Ed ecco un esempio di questo. Quindi cerchiamo di andare con l'idea di-- bene, abbiamo appena creato 12. Sappiamo che 12 sta per essere il nuovo capo della lista, e allora perché non ci muoviamo solo il puntatore lista a punto lì. 

Ok, va bene. Così ora da dove viene il 12 prossimo punto? Voglio dire, visivamente possiamo vedere che punterà a 15, come gli esseri umani è davvero ovvio per noi. Come fa sapere il computer? Noi non abbiamo nulla che punta a 15 più, giusto? 

Abbiamo perso ogni capacità di fare riferimento a 15. Non possiamo dire nuova freccia accanto eguali qualcosa, non c'è niente lì. In realtà, abbiamo orfani il resto della lista così facendo, abbiamo accidentalmente rotto la catena. E noi certamente non vogliamo farlo. 

Quindi cerchiamo di tornare indietro e provare di nuovo. Forse la cosa giusta da fare è quello di impostare 12 del prossimo puntatore alla vecchia testa del primo elenco, allora possiamo spostare la lista sopra. Ed infatti, che è il ordine corretto che noi devono seguire quando siamo lavorare con la lista concatenata. Vogliamo sempre di collegare il nuovo elemento nella lista, prima di prendere questo tipo di passo importante di cambiamento dove la testa della lista collegata è. Ancora una volta, questa è una cosa fondamentale, noi non vogliamo perdere la traccia di esso. 

Quindi vogliamo fare in modo che tutto è incatenato insieme, prima di passare tale puntatore. E quindi questo sarebbe l'ordine corretto, che è di collegare 12 alla lista, poi dire che l'elenco inizia una 12. Se abbiamo detto che la lista inizia alle 12 e poi ha cercato di connettersi 12 alla lista, abbiamo già visto cosa succede. Perdiamo la lista per errore. 

OK, una cosa di cui parlare. Che cosa succede se si vuole sbarazzarsi di un intero collegata lista in una sola volta? Ancora una volta, stiamo mallocing tutto questo spazio, e quindi abbiamo bisogno di liberarlo quando abbiamo finito. Così ora vogliamo eliminare l'intera lista collegata. Ebbene, che cosa vogliamo fare? 

Se abbiamo raggiunto il puntatore nullo, abbiamo vuole fermare, altrimenti, basta eliminare il resto della lista e poi liberami. Eliminare il resto della lista, e quindi liberare il nodo corrente. Che cosa significa che suonano come, quale tecnica abbiamo abbiamo parlato circa in precedenza fa quel suono come? Eliminare tutti gli altri, quindi tornare e mi cancellare. 

Che è la ricorsione, che abbiamo fatto la problema un po 'più piccolo, stiamo dicendo cancellare tutti altro, allora è possibile eliminare me. E a valle della strada, tale nodo dirà, eliminare tutti gli altri. Ma alla fine ci arriveremo al punto in cui la lista è nullo, e questo è il nostro caso base. 

Quindi, diamo uno sguardo a questo, e come questo potrebbe funzionare. Quindi, ecco la nostra lista, è la stessa Elenchiamo stavamo parlando, e ci sono i gradini. C'è un sacco di testo qui, ma speriamo che la visualizzazione sarà di aiuto. 

Così abbiamo have-- e ho anche tirato il nostro stack frame illustrazione dal nostro video su stack di chiamate, e speriamo che tutto questo insieme vi mostrerà ciò che sta succedendo. Quindi, ecco il nostro codice pseudocodice. Se raggiungiamo un nullo puntatore, stop, altrimenti, eliminare il resto della lista, quindi liberare il nodo corrente. Così adesso, list-- il puntatore che siamo passando per distruggere punti a 12. 12 non è un puntatore nullo, quindi siamo andando a cancellare il resto della lista. 

Che cosa è l'eliminazione del resto di noi ha coinvolto? Beh, significa fare un chiamata a distruggere, dicendo 15 che è l'inizio della resto della lista che vogliamo distruggere. E così la chiamata a distruggere 12 è di tipo in attesa. E 'congelato lì, in attesa del chiamare per distruggere 15, per completare il suo lavoro. 

Beh, 15 non è un puntatore nullo, e così sta andando a dire, va bene, bene, cancellare il resto della lista. Il resto della lista inizia a 9, e quindi dobbiamo solo attendere che si elimina tutto ciò che roba, poi tornare e mi cancellare. Ben 9 sta per dire, beh, Io non sono un puntatore nullo, così cancellare il resto della lista da qui. E così cercare di distruggere 13. 13 dice, io non sono puntatore nullo, stessa cosa, passa la patata bollente. 10 non è puntatore nullo, 10 contiene un puntatore nullo, ma 10 non è di per sé un Null Pointer in questo momento, e così passa il dollaro troppo. 

E ora elencare punti lì, sarebbe davvero puntare a some-- se avessi più spazio nell'immagine, sarebbe puntare a qualche spazio casuale che non sappiamo di cosa si tratta. E 'il puntatore nullo, però, la lista è letteralmente ora impostato è valori nulli. Si punta a destra dentro quella scatola rossa. Abbiamo raggiunto un puntatore nullo, così possiamo fermarci, e abbiamo finito. 

E così quella cornice viola è now-- al cima stack-- che è il frame attivo, ma è fatto. Se abbiamo raggiunto un puntatore nullo, stop. Noi non facciamo nulla, non può liberare un puntatore nullo, non abbiamo alcun malloc spazio, e così abbiamo finito. In modo che la funzione telaio è distrutta, e noi resume-- prendiamo dove abbiamo lasciato off con immediatamente superiore, che è questa cornice blu scuro qui. Quindi prendiamo a destra dove abbiamo lasciato. Abbiamo cancellato il resto del lista già, quindi ora siamo andando a liberare i nodi attuali. Così ora possiamo liberare questo nodo, e ora abbiamo raggiunto la fine della funzione. E così quella cornice funzione è distrutta, e prendiamo la luce blu. 

Così says-- ho già done-- eliminando il resto della lista, così liberare il nodo corrente. E ora la cornice gialla è torna in cima alla pila. E così come vedete, siamo ora distruggendo la lista da destra a sinistra. 

Cosa sarebbe successo, però, se avessimo fatto le cose nel modo sbagliato? Proprio come quando abbiamo provato aggiungere un elemento. Se abbiamo incasinato la catena, se noi non colleghiamo i puntatori nell'ordine corretto, se appena liberato il primo elemento, se abbiamo appena liberato il capo della lista, ora siamo hanno modo di consultare il resto della lista. E così avremmo orfano tutto, avremmo avuto ciò che è chiamato una perdita di memoria. Se vi ricordate dal nostro video sulla allocazione dinamica della memoria, che non è cosa molto buona. 

Così come ho detto, ci sono diverse operazioni che abbiamo bisogno di usare per lavorare con lista concatenata in modo efficace. E avrete notato ho omesso uno, l'eliminazione di un singolo elemento da una collegata lista. La ragione per cui l'ho fatto è che è in realtà una specie di difficile pensare a come eliminare un singolo elemento da una singolarmente lista collegata. Dobbiamo essere in grado di saltare qualcosa nella lista, che mezzi si arriva a un noi Point-- di voler eliminare questo node-- ma per fare in modo che non perdere alcuna informazione, abbiamo bisogno di collegare questo nodo qui, qui. 

Quindi probabilmente ho fatto male da un punto di vista visivo. Quindi siamo all'inizio del nostro lista, stiamo procedendo attraverso, vogliamo eliminare questo nodo. Se è sufficiente eliminarlo, abbiamo rotto la catena. Questo nodo qui si riferisce a tutto il resto, contiene la catena da qui in avanti. 

Allora cosa dobbiamo fare in realtà dopo siamo arrivati ​​a questo punto, è dobbiamo fare un passo indietro di un, e collegare questo nodo verso questo nodo, in modo che possiamo eliminare quella nel mezzo. Ma le liste concatenate semplici non lo fanno noi fornire un modo per tornare indietro. Quindi abbiamo bisogno di mantenere o due puntatori, e spostarli sorta di passo off, uno dietro l' altro come andiamo, o arrivare a un punto e poi inviare un altro puntatore attraverso. E come potete vedere, può ottenere un po 'disordinato. Per fortuna, abbiamo un altro modo per risolvere questo, quando si parla di liste doppiamente collegate. 

Sono Doug Lloyd, questo è CS50.