[RIPRODUZIONE DI BRANI MUSICALI] DOUG LLOYD: Va bene. Quindi, se avete appena finito che video on-liste semplicemente collegate dispiace Ti ho lasciato fuori su un po 'di un cliffhanger. Ma sono felice che tu sia qui per finire la storia di liste doppiamente collegate. 

Quindi, se vi ricordate da che il video, abbiamo parlato su come singolarmente-linked liste fanno partecipare la nostra capacità a che fare con le informazioni dove il numero di elementi o il numero di elementi in un elenco può crescere o restringersi. Ora possiamo affrontare qualcosa di simile, dove non abbiamo potuto trattare con esso con gli array. 

Ma essi soffrono di una limitazione critica che è che con un singolarmente legata lista, possiamo sempre e solo muoversi in una sola direzione attraverso la lista. E l'unica situazione reale dove che può diventare un problema è stato quando stavamo cercando di eliminare un singolo elemento. E non abbiamo nemmeno discusso come fare in una lista semplicemente legata in pseudocodice. È certamente fattibile, ma può essere un po 'di fastidio. Quindi, se vi trovate in una situazione in cui si sta cercando di eliminare singoli elementi della lista o che sta per essere richiesta che sarete cancellando singoli elementi da la lista, si potrebbe desiderare a considerare l'utilizzo di un doppiamente-linked elencare invece di una lista singolarmente-linked. Poiché gli elenchi doppiamente collegate consentono per spostare entrambi avanti e indietro l'elenco anziché solo in avanti attraverso la list-- solo con l'aggiunta di un elemento in più alla nostra definizione della struttura per il nodo lista doppiamente collegata. 

Anche in questo caso, se non avete intenzione di essere l'eliminazione di singoli elementi dal list-- perché stiamo aggiungendo un campo in più per la nostra struttura definizione, i nodi stessi per le liste doppiamente collegate stanno per essere più grande. Stanno andando a prendere up più byte di memoria. E così, se questo non è qualcosa si sta andando ad avere bisogno di fare, si potrebbe decidere che è non vale il trade off di dover spendere più byte di memoria necessari per una lista doppiamente legata se non siete andando a essere cancellando singoli elementi. Ma sono anche fresco per altre cose troppo. 

Così come ho detto, non ci resta che aggiungere un unico campo per la nostra struttura definition-- questa nozione di un puntatore precedente. Quindi, con una lista semplicemente collegata, abbiamo avere il valore e il puntatore successivo, così la lista doppiamente collegata ha appena un modo per tornare indietro pure. 

Ora, nel singolarmente-linked elenco dei video, abbiamo parlato su questi sono cinque del cose principali che dovete essere in grado di fare per lavorare con liste collegate. E per la maggior parte di questi, il fatto che si tratta di una lista doppiamente legata Non è davvero un grande salto. Possiamo ancora la ricerca in da solo andare avanti dall'inizio alla fine. Possiamo ancora creare un nodo di aria sottile, più o meno allo stesso modo. Siamo in grado di eliminare gli elenchi piuttosto più o meno allo stesso modo. Le uniche cose che sono sottilmente diverso, davvero, sono l'inserimento nuovi nodi nella lista, e saremo finalmente parla di eliminazione un singolo elemento della lista pure. Ancora una volta, più o meno gli altri tre, siamo non andare a parlare di loro in questo momento perché sono appena tweaks molto minori sulle idee discusse nel video lista semplicemente collegata. 

Quindi cerchiamo di inserire un nuovo nodo in una lista doppiamente legata. Abbiamo parlato di fare questo per liste semplicemente legata pure, ma ci sono un paio di in più le catture con le liste doppiamente collegate. Siamo [? passando?] nella testa del elencare qui e un po 'di valore arbitrario, e vogliamo ottenere il nuovo capo dell'elenco da questa funzione. Ecco perché restituisce una stella dllnode. Ma quali sono i passaggi? Essi sono, di nuovo, molto simile a liste semplicemente linked con un'aggiunta in più. Vogliamo alloca spazio per un nuovo nodo e controllo per assicurarsi che sia valido. Vogliamo riempire quel nodo in su con tutte le informazioni che vuole mettere in esso. L'ultima cosa di cui abbiamo bisogno per la fare-- cosa in più che dobbiamo fare, rather-- è di fissare il puntatore precedente del vecchio capo della lista. Ricorda che, poiché liste di doppiamente-linked, possiamo andare avanti e che backwards-- significa che ogni nodo punta effettivamente ad altri due nodi invece di uno solo. E così abbiamo bisogno di risolvere il problema il vecchio capo della lista per puntare indietro per il nuovo capo di la lista collegata, che era qualcosa Non abbiamo dovuto fare prima. E come prima, dobbiamo solo restituire un puntatore al nuovo capo della lista. 

Quindi, ecco un elenco. Vogliamo inserire 12 in questo elenco. Si noti che il diagramma è leggermente diverso. Ogni nodo contiene tre fields-- i dati, e un puntatore Next in rosso, e un puntatore precedente in blu. Niente viene prima del nodo 15, così il suo puntatore precedente è nullo. E 'l'inizio della lista. Non c'è niente di prima. E nulla viene dopo il nodo 10 e quindi è successivo puntatore è nullo pure. 

Quindi aggiungiamo 12 a questa lista. Dobbiamo [incomprensibile] spazio per il nodo. Abbiamo messo 12 all'interno di esso. E poi di nuovo, abbiamo bisogno di essere veramente attenzione a non rompere la catena. Noi vogliamo riorganizzare la puntatori nell'ordine corretto. E a volte questo potrebbe mean-- come vedremo in particolare con delete-- che noi abbiamo un po ' puntatori ridondanti, ma va bene così. 

Così che cosa vogliamo fare prima? Consiglierei il cose che si dovrebbe probabilmente fare sono per riempire i puntatori del 12 nodo prima di toccare chiunque altro. Così che cosa sta andando a 12 punti al prossimo? 15. Che cosa viene prima del 12? Niente. Ora abbiamo riempito il informazioni aggiuntive di 12 quindi ha Precedente, Successivo e valore. 

Ora possiamo avere 15-- questo extra passo parlavamo about-- noi può avere 15 punti indietro a 12. E ora siamo in grado di spostare la testa di la lista collegata di essere anche 12. Quindi è abbastanza simile a quello che abbiamo stavano facendo con le liste singolarmente-linked, tranne per il passaggio aggiuntivo di che collega il vecchio capo della lista tornare al nuovo capo della lista. 

Ora diamo finalmente cancellare un nodo da una lista collegata. Quindi cerchiamo di dire che abbiamo qualche altra funzione che è trovare un nodo che vogliamo eliminare e ci ha dato un puntatore esattamente il nodo che vogliamo eliminare. Non abbiamo nemmeno need-- dire la testa è ancora dichiarata a livello globale. Non abbiamo bisogno di testa qui. Tutto questa funzione sta facendo è che abbiamo trovato un puntatore esattamente abbiamo nodo vogliono sbarazzarsi di. Andiamo liberarsi di esso. E 'molto più facile con liste doppiamente-linked. First-- in realtà solo un paio di cose. Abbiamo solo bisogno di fissare la circonda puntatori nodi 'in modo da saltare il nodo che vogliamo eliminare. E allora possiamo cancellare quel nodo. Così ancora una volta, stiamo solo attraversando qui. Abbiamo deciso che a quanto pare vogliamo eliminare il nodo X. E ancora, quello che sto facendo qui-- dal way-- è un caso generale di nodo che è al centro. Ci sono un paio di caveat in più che necessario prendere in considerazione quando si sta cancellando Fin dall'inizio della lista o alla fine della lista. Ci sono un paio di speciale casi d'angolo per affrontare lì. 

Quindi, questo funziona per l'eliminazione di qualsiasi nodo nel mezzo di quello che list-- ha un puntatore legittima avanti e un puntatore legittima all'indietro, legittimo puntatore Indietro e Avanti. Anche in questo caso, se si sta lavorando con le estremità, si necessità di gestire quelli in modo leggermente diverso, e non stiamo andando a parlarne adesso. Ma si può probabilmente capire cosa ha bisogno deve essere fatto solo guardando questo video. 

Così abbiamo isolato X. X è il nodo vogliamo eliminare dalla lista. Cosa facciamo? In primo luogo, abbiamo bisogno di riorganizzare i puntatori esterni. Abbiamo bisogno di riorganizzare 9 della prossima per saltare oltre 13 e punto di 10-- che è quello che abbiamo appena fatto. E abbiamo anche bisogno di riorganizzare 10 Precedente per puntare a 9 invece di indicare 13. 

Quindi, di nuovo, questo è stato il Schema per iniziare. Questa era la nostra catena. Abbiamo bisogno di saltare 13, ma abbiamo bisogno di preservare anche l'integrità della lista. Non vogliamo perdere nessuno informazioni in entrambe le direzioni. Quindi abbiamo bisogno di riorganizzare i puntatori con attenzione in modo da non rompere la catena a tutti. 

Quindi possiamo dire 9 Next puntatore punti nello stesso posto che tredici Next puntatore indica adesso. Perché siamo alla fine andando a voler saltare 13. Quindi, ovunque 13 punti successiva, vogliono nove per puntare invece c'è. Ecco, questo è quello. E poi ovunque 13 punti indietro a, ciò che viene prima del 13, vogliamo 10 al punto a che invece di 13. Ora notate, se si seguono le frecce, che possono cadere 13 senza realmente perdere alcuna informazione. Abbiamo mantenuto l'integrità della lista, in movimento sia in avanti che all'indietro. E poi possiamo appena sorta di ripulire un po ' tirando l'elenco insieme. Così abbiamo riorganizzato il indicazioni su entrambi i lati. E poi abbiamo liberato il X nodo che conteneva 13, e noi non spezziamo la catena. Così abbiamo fatto bene. 

Nota finale qui su liste concatenate. Così sia singly- e doppiamente concatenata liste, come abbiamo visto, sostegno all'inserimento davvero efficiente e l'eliminazione degli elementi. Si può tranquillamente fare in tempo costante. Quello che abbiamo dovuto fare per eliminare un elemento appena un secondo fa? Ci siamo mossi un puntatore. Ci siamo spostati un altro puntatore. Abbiamo liberato X-- preso tre operazioni. Ci vuole sempre tre operazioni a eliminare tale node-- per liberare un nodo. 

Come possiamo inseriamo? Beh, siamo solo sempre virata sull'inizio se stiamo inserendo in modo efficiente. Quindi abbiamo bisogno di rearrange-- a seconda se si tratta di un singly- o doppiamente legata lista, potremmo aver bisogno di fare tre o quattro operazioni max. Ma ancora una volta, è sempre tre o quattro. Non importa quanti elementi sono nella nostra lista, è sempre tre o quattro operations-- proprio come la cancellazione è sempre tre o quattro operazioni. E 'tempo costante. Ecco, questo è davvero grande. 

Con gli array, stavamo facendo qualcosa come insertion sort. Probabilmente ricorderete che l'inserimento tipo non è un algoritmo di tempo costante. In realtà è piuttosto costoso. Quindi questo è molto meglio per l'inserimento. Ma, come ho detto nel singolarmente-linked elenco dei video, abbiamo un aspetto negativo anche qui, giusto? Abbiamo perso la capacità di accedere in modo casuale elementi. Non si può dire, voglio numero di elemento quattro o elemento numero 10 di una lista collegata allo stesso modo che possiamo farlo con una matrice o possiamo semplicemente direttamente indice in elemento del nostro array. 

E così cercando di trovare una elemento in una list-- collegato se la ricerca è importante-- può ora prendere tempo lineare. Poiché l'elenco si allunga, si potrebbe fare un ulteriore passo per ogni singolo elemento nell'elenco al fine di trovare quello che stiamo cercando. Quindi c'è compromessi. C'è un po 'di un professionista e l'elemento con qui. 

E le liste doppiamente collegate non sono ultimo tipo di combinazione di struttura dati che parleremo, prendendo tutto l'edificio di base blocchi di C un mettere insieme. Perché in realtà, possiamo anche fare meglio di questo per creare una struttura di dati che si potrebbe essere in grado di cercare attraverso in tempo costante anche. Ma più su che in un altro video. 

Sono Doug Lloyd. Questo è CS50.