1
00:00:00,000 --> 00:00:03,381
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Va bene.

4
00:00:05,520 --> 00:00:07,860
Quindi, se avete appena finito che
video on-liste semplicemente collegate dispiace

5
00:00:07,860 --> 00:00:09,568
Ti ho lasciato fuori su un
po 'di un cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ma sono felice che tu sia qui per finire
la storia di liste doppiamente collegate.

7
00:00:12,790 --> 00:00:15,250
>> Quindi, se vi ricordate da
che il video, abbiamo parlato

8
00:00:15,250 --> 00:00:18,500
su come singolarmente-linked
liste fanno partecipare la nostra capacità

9
00:00:18,500 --> 00:00:22,090
a che fare con le informazioni
dove il numero di elementi

10
00:00:22,090 --> 00:00:24,442
o il numero di elementi in
un elenco può crescere o restringersi.

11
00:00:24,442 --> 00:00:26,400
Ora possiamo affrontare
qualcosa di simile, dove

12
00:00:26,400 --> 00:00:28,310
non abbiamo potuto trattare con esso con gli array.

13
00:00:28,310 --> 00:00:30,560
>> Ma essi soffrono di una
limitazione critica che

14
00:00:30,560 --> 00:00:33,790
è che con un singolarmente legata
lista, possiamo sempre e solo muoversi

15
00:00:33,790 --> 00:00:36,200
in una sola direzione attraverso la lista.

16
00:00:36,200 --> 00:00:39,010
E l'unica situazione reale
dove che può diventare un problema

17
00:00:39,010 --> 00:00:41,250
è stato quando stavamo cercando di
eliminare un singolo elemento.

18
00:00:41,250 --> 00:00:46,000
E non abbiamo nemmeno discusso come fare
in una lista semplicemente legata in pseudocodice.

19
00:00:46,000 --> 00:00:48,797
È certamente fattibile, ma
può essere un po 'di fastidio.

20
00:00:48,797 --> 00:00:50,630
Quindi, se vi trovate
in una situazione in cui

21
00:00:50,630 --> 00:00:53,175
si sta cercando di eliminare
singoli elementi della lista

22
00:00:53,175 --> 00:00:55,430
o che sta per essere richiesta
che sarete cancellando

23
00:00:55,430 --> 00:00:57,970
singoli elementi da
la lista, si potrebbe desiderare

24
00:00:57,970 --> 00:01:02,090
a considerare l'utilizzo di un doppiamente-linked
elencare invece di una lista singolarmente-linked.

25
00:01:02,090 --> 00:01:06,320
Poiché gli elenchi doppiamente collegate consentono
per spostare entrambi avanti e indietro

26
00:01:06,320 --> 00:01:09,340
l'elenco anziché
solo in avanti attraverso la list--

27
00:01:09,340 --> 00:01:13,950
solo con l'aggiunta di un elemento in più
alla nostra definizione della struttura

28
00:01:13,950 --> 00:01:16,690
per il nodo lista doppiamente collegata.

29
00:01:16,690 --> 00:01:19,770
>> Anche in questo caso, se non avete intenzione di
essere l'eliminazione di singoli elementi

30
00:01:19,770 --> 00:01:24,810
dal list-- perché stiamo aggiungendo
un campo in più per la nostra struttura

31
00:01:24,810 --> 00:01:28,340
definizione, i nodi stessi
per le liste doppiamente collegate

32
00:01:28,340 --> 00:01:29,550
stanno per essere più grande.

33
00:01:29,550 --> 00:01:31,600
Stanno andando a prendere
up più byte di memoria.

34
00:01:31,600 --> 00:01:34,160
E così, se questo non è qualcosa
si sta andando ad avere bisogno di fare,

35
00:01:34,160 --> 00:01:36,300
si potrebbe decidere che è
non vale il trade off

36
00:01:36,300 --> 00:01:39,360
di dover spendere più
byte di memoria necessari

37
00:01:39,360 --> 00:01:43,940
per una lista doppiamente legata se non siete
andando a essere cancellando singoli elementi.

38
00:01:43,940 --> 00:01:46,760
Ma sono anche fresco
per altre cose troppo.

39
00:01:46,760 --> 00:01:51,260
>> Così come ho detto, non ci resta che aggiungere
un unico campo per la nostra struttura

40
00:01:51,260 --> 00:01:55,360
definition-- questa nozione
di un puntatore precedente.

41
00:01:55,360 --> 00:01:58,620
Quindi, con una lista semplicemente collegata, abbiamo
avere il valore e il puntatore successivo,

42
00:01:58,620 --> 00:02:02,850
così la lista doppiamente collegata ha appena
un modo per tornare indietro pure.

43
00:02:02,850 --> 00:02:04,960
>> Ora, nel singolarmente-linked
elenco dei video, abbiamo parlato

44
00:02:04,960 --> 00:02:07,210
su questi sono cinque del
cose principali che dovete essere

45
00:02:07,210 --> 00:02:09,449
in grado di fare per lavorare con liste collegate.

46
00:02:09,449 --> 00:02:12,880
E per la maggior parte di questi, il fatto
che si tratta di una lista doppiamente legata

47
00:02:12,880 --> 00:02:14,130
Non è davvero un grande salto.

48
00:02:14,130 --> 00:02:17,936
Possiamo ancora la ricerca in da solo
andare avanti dall'inizio alla fine.

49
00:02:17,936 --> 00:02:20,810
Possiamo ancora creare un nodo di
aria sottile, più o meno allo stesso modo.

50
00:02:20,810 --> 00:02:23,591
Siamo in grado di eliminare gli elenchi piuttosto
più o meno allo stesso modo.

51
00:02:23,591 --> 00:02:25,340
Le uniche cose che
sono sottilmente diverso,

52
00:02:25,340 --> 00:02:28,970
davvero, sono l'inserimento
nuovi nodi nella lista,

53
00:02:28,970 --> 00:02:33,722
e saremo finalmente parla di eliminazione
un singolo elemento della lista pure.

54
00:02:33,722 --> 00:02:35,430
Ancora una volta, più o meno
gli altri tre, siamo

55
00:02:35,430 --> 00:02:37,888
non andare a parlare di loro
in questo momento perché sono appena

56
00:02:37,888 --> 00:02:43,920
tweaks molto minori sulle idee discusse
nel video lista semplicemente collegata.

57
00:02:43,920 --> 00:02:46,292
>> Quindi cerchiamo di inserire un nuovo nodo
in una lista doppiamente legata.

58
00:02:46,292 --> 00:02:48,750
Abbiamo parlato di fare questo per
liste semplicemente legata pure,

59
00:02:48,750 --> 00:02:52,020
ma ci sono un paio di in più
le catture con le liste doppiamente collegate.

60
00:02:52,020 --> 00:02:55,280
Siamo [? passando?] nella testa del
elencare qui e un po 'di valore arbitrario,

61
00:02:55,280 --> 00:02:58,600
e vogliamo ottenere il nuovo capo
dell'elenco da questa funzione.

62
00:02:58,600 --> 00:03:01,414
Ecco perché restituisce una stella dllnode.

63
00:03:01,414 --> 00:03:02,330
Ma quali sono i passaggi?

64
00:03:02,330 --> 00:03:04,496
Essi sono, di nuovo, molto simile
a liste semplicemente linked

65
00:03:04,496 --> 00:03:05,670
con un'aggiunta in più.

66
00:03:05,670 --> 00:03:08,900
Vogliamo alloca spazio per un nuovo
nodo e controllo per assicurarsi che sia valido.

67
00:03:08,900 --> 00:03:11,510
Vogliamo riempire quel nodo in su
con tutte le informazioni che

68
00:03:11,510 --> 00:03:12,564
vuole mettere in esso.

69
00:03:12,564 --> 00:03:15,480
L'ultima cosa di cui abbiamo bisogno per la fare--
cosa in più che dobbiamo fare, rather--

70
00:03:15,480 --> 00:03:19,435
è di fissare il puntatore precedente
del vecchio capo della lista.

71
00:03:19,435 --> 00:03:21,310
Ricorda che, poiché
liste di doppiamente-linked,

72
00:03:21,310 --> 00:03:23,110
possiamo andare avanti
e che backwards--

73
00:03:23,110 --> 00:03:27,080
significa che ogni nodo punta effettivamente
ad altri due nodi invece di uno solo.

74
00:03:27,080 --> 00:03:29,110
E così abbiamo bisogno di risolvere il problema
il vecchio capo della lista

75
00:03:29,110 --> 00:03:32,151
per puntare indietro per il nuovo capo di
la lista collegata, che era qualcosa

76
00:03:32,151 --> 00:03:33,990
Non abbiamo dovuto fare prima.

77
00:03:33,990 --> 00:03:37,420
E come prima, dobbiamo solo restituire un
puntatore al nuovo capo della lista.

78
00:03:37,420 --> 00:03:38,220
>> Quindi, ecco un elenco.

79
00:03:38,220 --> 00:03:40,144
Vogliamo inserire 12 in questo elenco.

80
00:03:40,144 --> 00:03:42,060
Si noti che il diagramma
è leggermente diverso.

81
00:03:42,060 --> 00:03:47,710
Ogni nodo contiene tre fields--
i dati, e un puntatore Next in rosso,

82
00:03:47,710 --> 00:03:50,170
e un puntatore precedente in blu.

83
00:03:50,170 --> 00:03:54,059
Niente viene prima del nodo 15,
così il suo puntatore precedente è nullo.

84
00:03:54,059 --> 00:03:55,350
E 'l'inizio della lista.

85
00:03:55,350 --> 00:03:56,560
Non c'è niente di prima.

86
00:03:56,560 --> 00:04:03,350
E nulla viene dopo il nodo 10 e
quindi è successivo puntatore è nullo pure.

87
00:04:03,350 --> 00:04:05,616
>> Quindi aggiungiamo 12 a questa lista.

88
00:04:05,616 --> 00:04:08,070
Dobbiamo [incomprensibile] spazio per il nodo.

89
00:04:08,070 --> 00:04:11,480
Abbiamo messo 12 all'interno di esso.

90
00:04:11,480 --> 00:04:14,840
E poi di nuovo, abbiamo bisogno di essere veramente
attenzione a non rompere la catena.

91
00:04:14,840 --> 00:04:17,144
Noi vogliamo riorganizzare la
puntatori nell'ordine corretto.

92
00:04:17,144 --> 00:04:19,519
E a volte questo potrebbe mean--
come vedremo in particolare

93
00:04:19,519 --> 00:04:24,120
con delete-- che noi abbiamo un po '
puntatori ridondanti, ma va bene così.

94
00:04:24,120 --> 00:04:25,750
>> Così che cosa vogliamo fare prima?

95
00:04:25,750 --> 00:04:28,290
Consiglierei il
cose che si dovrebbe probabilmente

96
00:04:28,290 --> 00:04:35,350
fare sono per riempire i puntatori del 12
nodo prima di toccare chiunque altro.

97
00:04:35,350 --> 00:04:38,640
Così che cosa sta andando a 12 punti al prossimo?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
Che cosa viene prima del 12?

100
00:04:42,430 --> 00:04:43,640
Niente.

101
00:04:43,640 --> 00:04:46,280
Ora abbiamo riempito il
informazioni aggiuntive di 12

102
00:04:46,280 --> 00:04:49,320
quindi ha Precedente, Successivo e valore.

103
00:04:49,320 --> 00:04:53,505
>> Ora possiamo avere 15-- questo extra
passo parlavamo about-- noi

104
00:04:53,505 --> 00:04:56,590
può avere 15 punti indietro a 12.

105
00:04:56,590 --> 00:04:59,634
E ora siamo in grado di spostare la testa di
la lista collegata di essere anche 12.

106
00:04:59,634 --> 00:05:02,550
Quindi è abbastanza simile a quello che abbiamo
stavano facendo con le liste singolarmente-linked,

107
00:05:02,550 --> 00:05:06,940
tranne per il passaggio aggiuntivo di
che collega il vecchio capo della lista

108
00:05:06,940 --> 00:05:09,810
tornare al nuovo capo della lista.

109
00:05:09,810 --> 00:05:12,170
>> Ora diamo finalmente cancellare
un nodo da una lista collegata.

110
00:05:12,170 --> 00:05:14,350
Quindi cerchiamo di dire che abbiamo
qualche altra funzione che

111
00:05:14,350 --> 00:05:18,080
è trovare un nodo che vogliamo eliminare
e ci ha dato un puntatore esattamente

112
00:05:18,080 --> 00:05:19,710
il nodo che vogliamo eliminare.

113
00:05:19,710 --> 00:05:22,360
Non abbiamo nemmeno need-- dire la
testa è ancora dichiarata a livello globale.

114
00:05:22,360 --> 00:05:23,590
Non abbiamo bisogno di testa qui.

115
00:05:23,590 --> 00:05:26,830
Tutto questa funzione sta facendo è che abbiamo
trovato un puntatore esattamente abbiamo nodo

116
00:05:26,830 --> 00:05:28,090
vogliono sbarazzarsi di.

117
00:05:28,090 --> 00:05:28,940
Andiamo liberarsi di esso.

118
00:05:28,940 --> 00:05:31,859
E 'molto più facile con
liste doppiamente-linked.

119
00:05:31,859 --> 00:05:33,650
First-- in realtà
solo un paio di cose.

120
00:05:33,650 --> 00:05:38,760
Abbiamo solo bisogno di fissare la circonda
puntatori nodi 'in modo da saltare

121
00:05:38,760 --> 00:05:40,240
il nodo che vogliamo eliminare.

122
00:05:40,240 --> 00:05:43,484
E allora possiamo cancellare quel nodo.

123
00:05:43,484 --> 00:05:45,150
Così ancora una volta, stiamo solo attraversando qui.

124
00:05:45,150 --> 00:05:49,625
Abbiamo deciso che a quanto pare
vogliamo eliminare il nodo X.

125
00:05:49,625 --> 00:05:51,500
E ancora, quello che sto
facendo qui-- dal way--

126
00:05:51,500 --> 00:05:54,580
è un caso generale di
nodo che è al centro.

127
00:05:54,580 --> 00:05:56,547
Ci sono un paio di
caveat in più che

128
00:05:56,547 --> 00:05:59,380
necessario prendere in considerazione quando si sta cancellando
Fin dall'inizio della lista

129
00:05:59,380 --> 00:06:01,040
o alla fine della lista.

130
00:06:01,040 --> 00:06:03,730
Ci sono un paio di speciale
casi d'angolo per affrontare lì.

131
00:06:03,730 --> 00:06:07,960
>> Quindi, questo funziona per l'eliminazione di qualsiasi nodo
nel mezzo di quello che list--

132
00:06:07,960 --> 00:06:11,550
ha un puntatore legittima avanti
e un puntatore legittima all'indietro,

133
00:06:11,550 --> 00:06:14,460
legittimo puntatore Indietro e Avanti.

134
00:06:14,460 --> 00:06:16,530
Anche in questo caso, se si sta lavorando
con le estremità, si

135
00:06:16,530 --> 00:06:18,500
necessità di gestire quelli
in modo leggermente diverso,

136
00:06:18,500 --> 00:06:19,570
e non stiamo andando a
parlarne adesso.

137
00:06:19,570 --> 00:06:21,319
Ma si può probabilmente
capire cosa ha bisogno

138
00:06:21,319 --> 00:06:24,610
deve essere fatto solo guardando questo video.

139
00:06:24,610 --> 00:06:28,910
>> Così abbiamo isolato X. X è il nodo
vogliamo eliminare dalla lista.

140
00:06:28,910 --> 00:06:30,140
Cosa facciamo?

141
00:06:30,140 --> 00:06:32,800
In primo luogo, abbiamo bisogno di riorganizzare
i puntatori esterni.

142
00:06:32,800 --> 00:06:35,815
Abbiamo bisogno di riorganizzare
9 della prossima per saltare oltre 13

143
00:06:35,815 --> 00:06:38,030
e punto di 10-- che
è quello che abbiamo appena fatto.

144
00:06:38,030 --> 00:06:41,180
E abbiamo anche bisogno di
riorganizzare 10 Precedente

145
00:06:41,180 --> 00:06:44,610
per puntare a 9 invece di indicare 13.

146
00:06:44,610 --> 00:06:46,490
>> Quindi, di nuovo, questo è stato il
Schema per iniziare.

147
00:06:46,490 --> 00:06:47,730
Questa era la nostra catena.

148
00:06:47,730 --> 00:06:51,027
Abbiamo bisogno di saltare 13,
ma abbiamo bisogno di preservare anche

149
00:06:51,027 --> 00:06:52,110
l'integrità della lista.

150
00:06:52,110 --> 00:06:54,680
Non vogliamo perdere nessuno
informazioni in entrambe le direzioni.

151
00:06:54,680 --> 00:06:59,620
Quindi abbiamo bisogno di riorganizzare
i puntatori con attenzione

152
00:06:59,620 --> 00:07:02,240
in modo da non rompere la catena a tutti.

153
00:07:02,240 --> 00:07:05,710
>> Quindi possiamo dire 9 Next puntatore
punti nello stesso posto

154
00:07:05,710 --> 00:07:08,040
che tredici Next
puntatore indica adesso.

155
00:07:08,040 --> 00:07:10,331
Perché siamo alla fine
andando a voler saltare 13.

156
00:07:10,331 --> 00:07:13,750
Quindi, ovunque 13 punti successiva,
vogliono nove per puntare invece c'è.

157
00:07:13,750 --> 00:07:15,200
Ecco, questo è quello.

158
00:07:15,200 --> 00:07:20,370
E poi ovunque 13 punti indietro
a, ciò che viene prima del 13,

159
00:07:20,370 --> 00:07:24,800
vogliamo 10 al punto
a che invece di 13.

160
00:07:24,800 --> 00:07:29,290
Ora notate, se si seguono
le frecce, che possono cadere 13

161
00:07:29,290 --> 00:07:32,380
senza realmente perdere alcuna informazione.

162
00:07:32,380 --> 00:07:36,002
Abbiamo mantenuto l'integrità della lista,
in movimento sia in avanti che all'indietro.

163
00:07:36,002 --> 00:07:38,210
E poi possiamo appena sorta
di ripulire un po '

164
00:07:38,210 --> 00:07:40,930
tirando l'elenco insieme.

165
00:07:40,930 --> 00:07:43,270
Così abbiamo riorganizzato il
indicazioni su entrambi i lati.

166
00:07:43,270 --> 00:07:46,231
E poi abbiamo liberato il X
nodo che conteneva 13,

167
00:07:46,231 --> 00:07:47,480
e noi non spezziamo la catena.

168
00:07:47,480 --> 00:07:50,980
Così abbiamo fatto bene.

169
00:07:50,980 --> 00:07:53,000
>> Nota finale qui su liste concatenate.

170
00:07:53,000 --> 00:07:55,990
Così sia singly- e doppiamente concatenata
liste, come abbiamo visto,

171
00:07:55,990 --> 00:07:58,959
sostegno all'inserimento davvero efficiente
e l'eliminazione degli elementi.

172
00:07:58,959 --> 00:08:00,750
Si può tranquillamente fare
in tempo costante.

173
00:08:00,750 --> 00:08:03,333
Quello che abbiamo dovuto fare per eliminare
un elemento appena un secondo fa?

174
00:08:03,333 --> 00:08:04,440
Ci siamo mossi un puntatore.

175
00:08:04,440 --> 00:08:05,920
Ci siamo spostati un altro puntatore.

176
00:08:05,920 --> 00:08:07,915
Abbiamo liberato X-- preso tre operazioni.

177
00:08:07,915 --> 00:08:14,500
Ci vuole sempre tre operazioni a
eliminare tale node-- per liberare un nodo.

178
00:08:14,500 --> 00:08:15,280
>> Come possiamo inseriamo?

179
00:08:15,280 --> 00:08:17,280
Beh, siamo solo sempre
virata sull'inizio

180
00:08:17,280 --> 00:08:19,400
se stiamo inserendo in modo efficiente.

181
00:08:19,400 --> 00:08:21,964
Quindi abbiamo bisogno di rearrange--
a seconda se si tratta di

182
00:08:21,964 --> 00:08:24,380
un singly- o doppiamente legata
lista, potremmo aver bisogno di fare tre

183
00:08:24,380 --> 00:08:26,824
o quattro operazioni max.

184
00:08:26,824 --> 00:08:28,365
Ma ancora una volta, è sempre tre o quattro.

185
00:08:28,365 --> 00:08:30,531
Non importa quanti
elementi sono nella nostra lista,

186
00:08:30,531 --> 00:08:33,549
è sempre tre o quattro operations--
proprio come la cancellazione è sempre

187
00:08:33,549 --> 00:08:35,320
tre o quattro operazioni.

188
00:08:35,320 --> 00:08:36,919
E 'tempo costante.

189
00:08:36,919 --> 00:08:38,169
Ecco, questo è davvero grande.

190
00:08:38,169 --> 00:08:40,620
>> Con gli array, stavamo facendo
qualcosa come insertion sort.

191
00:08:40,620 --> 00:08:44,739
Probabilmente ricorderete che l'inserimento
tipo non è un algoritmo di tempo costante.

192
00:08:44,739 --> 00:08:46,030
In realtà è piuttosto costoso.

193
00:08:46,030 --> 00:08:48,840
Quindi questo è molto meglio per l'inserimento.

194
00:08:48,840 --> 00:08:51,840
Ma, come ho detto nel
singolarmente-linked elenco dei video,

195
00:08:51,840 --> 00:08:54,030
abbiamo un aspetto negativo anche qui, giusto?

196
00:08:54,030 --> 00:08:57,580
Abbiamo perso la capacità di
accedere in modo casuale elementi.

197
00:08:57,580 --> 00:09:02,310
Non si può dire, voglio numero di elemento quattro
o elemento numero 10 di una lista collegata

198
00:09:02,310 --> 00:09:04,990
allo stesso modo che possiamo
farlo con una matrice

199
00:09:04,990 --> 00:09:08,630
o possiamo semplicemente direttamente indice
in elemento del nostro array.

200
00:09:08,630 --> 00:09:10,930
>> E così cercando di trovare una
elemento in una list-- collegato

201
00:09:10,930 --> 00:09:15,880
se la ricerca è importante--
può ora prendere tempo lineare.

202
00:09:15,880 --> 00:09:18,330
Poiché l'elenco si allunga, si
potrebbe fare un ulteriore passo

203
00:09:18,330 --> 00:09:22,644
per ogni singolo elemento nell'elenco
al fine di trovare quello che stiamo cercando.

204
00:09:22,644 --> 00:09:23,560
Quindi c'è compromessi.

205
00:09:23,560 --> 00:09:25,780
C'è un po 'di un professionista
e l'elemento con qui.

206
00:09:25,780 --> 00:09:29,110
>> E le liste doppiamente collegate non sono
ultimo tipo di combinazione di struttura dati

207
00:09:29,110 --> 00:09:32,840
che parleremo,
prendendo tutto l'edificio di base

208
00:09:32,840 --> 00:09:34,865
blocchi di C un mettere insieme.

209
00:09:34,865 --> 00:09:37,900
Perché in realtà, possiamo
anche fare meglio di questo

210
00:09:37,900 --> 00:09:41,970
per creare una struttura di dati che
si potrebbe essere in grado di cercare attraverso

211
00:09:41,970 --> 00:09:43,360
in tempo costante anche.

212
00:09:43,360 --> 00:09:46,080
Ma più su che in un altro video.

213
00:09:46,080 --> 00:09:47,150
>> Sono Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Questo è CS50.

215
00:09:49,050 --> 00:09:50,877