1
00:00:00,000 --> 00:00:03,381
>> [Música tocando]

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

3
00:00:04,604 --> 00:00:05,520
Doug LLOYD: Todo ben.

4
00:00:05,520 --> 00:00:07,860
Entón, se acaba de rematar que
vídeo en listas individualmente ligados pesaroso

5
00:00:07,860 --> 00:00:09,568
Eu deixei vostede fóra nun
pouco dun cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Pero eu estou feliz que está aquí para rematar
a historia de listas dobremente ligadas.

7
00:00:12,790 --> 00:00:15,250
>> Entón, se lembrar de
que o vídeo, falamos

8
00:00:15,250 --> 00:00:18,500
sobre como individualmente conectado
Listas de facer participar a nosa capacidade

9
00:00:18,500 --> 00:00:22,090
para xestionar información
en que o número de elementos

10
00:00:22,090 --> 00:00:24,442
ou o número de elementos nas
unha lista pode aumentar ou diminuír.

11
00:00:24,442 --> 00:00:26,400
Agora podemos xestionar
algo así como que, cando

12
00:00:26,400 --> 00:00:28,310
non poderiamos tratar con isto con matrices.

13
00:00:28,310 --> 00:00:30,560
>> Pero padecen unha
limitación crítica que

14
00:00:30,560 --> 00:00:33,790
é que, cun conectado illadamente
lista, só podemos mover

15
00:00:33,790 --> 00:00:36,200
nunha única dirección a través da lista.

16
00:00:36,200 --> 00:00:39,010
E a única situación real
onde que pode chegar a ser un problema

17
00:00:39,010 --> 00:00:41,250
foi cando estabamos intentando
eliminar un único elemento.

18
00:00:41,250 --> 00:00:46,000
E nós nin sequera discutir como facelo
nunha lista illadamente ligada en pseudocódigo.

19
00:00:46,000 --> 00:00:48,797
É certamente factible, pero
pode ser un pouco de un problema.

20
00:00:48,797 --> 00:00:50,630
Entón, se atopa-se
nunha situación onde

21
00:00:50,630 --> 00:00:53,175
estás eliminar
elementos únicos da lista

22
00:00:53,175 --> 00:00:55,430
ou que vai ser esixido
que vai ser a exclusión

23
00:00:55,430 --> 00:00:57,970
elementos únicos de
a lista, pode querer

24
00:00:57,970 --> 00:01:02,090
considerar o uso dun conectado dobremente
lista en lugar dunha lista illadamente conectado.

25
00:01:02,090 --> 00:01:06,320
Como as listas dobremente vinculadas permiten que
para mover ambos adiante e cara atrás

26
00:01:06,320 --> 00:01:09,340
a través da lista no canto de
só para adiante a través da lista--

27
00:01:09,340 --> 00:01:13,950
só engadindo un elemento extra
a nosa definición de estrutura

28
00:01:13,950 --> 00:01:16,690
ao nó de lista dobremente vinculada.

29
00:01:16,690 --> 00:01:19,770
>> De novo, se non está indo a
ser exclusión elementos únicos

30
00:01:19,770 --> 00:01:24,810
do lista-- porque estamos engadindo
un campo extra para a nosa estrutura

31
00:01:24,810 --> 00:01:28,340
definición, os propios nós
para listas dobremente ligadas

32
00:01:28,340 --> 00:01:29,550
será maior.

33
00:01:29,550 --> 00:01:31,600
Eles van leva
Se máis bytes de memoria.

34
00:01:31,600 --> 00:01:34,160
E por iso, se iso non é algo
vai ter facer,

35
00:01:34,160 --> 00:01:36,300
pode decidir que é
Non paga a pena o trade off

36
00:01:36,300 --> 00:01:39,360
ter que pasar o extra
bytes de memoria

37
00:01:39,360 --> 00:01:43,940
Para obter unha lista dobremente vinculada se non está
será apagando elementos individuais.

38
00:01:43,940 --> 00:01:46,760
Pero tamén é legal
para outras cousas tamén.

39
00:01:46,760 --> 00:01:51,260
>> Entón, como dixen, nós só temos que engadir
un único campo para a nosa estrutura

40
00:01:51,260 --> 00:01:55,360
definition-- esta noción
dun punteiro anterior.

41
00:01:55,360 --> 00:01:58,620
Así, con unha lista illadamente conectado, nós
ten o valor eo punteiro Logo

42
00:01:58,620 --> 00:02:02,850
así que a lista dobremente vinculada só ten
un xeito de moverse cara atrás tamén.

43
00:02:02,850 --> 00:02:04,960
>> Agora, no individualmente conectado
lista de vídeos, falamos

44
00:02:04,960 --> 00:02:07,210
sobre estes son cinco dos
principais cousas que ten que estar

45
00:02:07,210 --> 00:02:09,449
capaz de facer para traballar con listas ligadas.

46
00:02:09,449 --> 00:02:12,880
E para a maioría destas, o feito
que é unha lista dobremente vinculada

47
00:02:12,880 --> 00:02:14,130
non é realmente un gran salto.

48
00:02:14,130 --> 00:02:17,936
Aínda pode buscar por só
fronte do principio ao final.

49
00:02:17,936 --> 00:02:20,810
Aínda os podemos crear un nodo
aire, practicamente do mesmo xeito.

50
00:02:20,810 --> 00:02:23,591
Podemos eliminar listas fermosa
do mesmo xeito tamén.

51
00:02:23,591 --> 00:02:25,340
As únicas cousas que
son sutilmente diferentes,

52
00:02:25,340 --> 00:02:28,970
realmente, está introducindo
novos nós na lista,

53
00:02:28,970 --> 00:02:33,722
e nós imos rematar falar da exclusión
un único elemento da lista ben.

54
00:02:33,722 --> 00:02:35,430
Unha vez máis, moi bonito
os outros tres, somos

55
00:02:35,430 --> 00:02:37,888
non vai falar sobre eles
agora, porque son só

56
00:02:37,888 --> 00:02:43,920
axustes moito menores sobre as ideas discutidas
no video lista illadamente conectado.

57
00:02:43,920 --> 00:02:46,292
>> Entón, imos introducir un novo nodo
nunha lista dobremente vinculada.

58
00:02:46,292 --> 00:02:48,750
Nós falamos sobre como facelo para
listas illadamente ligada, así como,

59
00:02:48,750 --> 00:02:52,020
pero hai un par de extras
colle con listas dobremente ligadas.

60
00:02:52,020 --> 00:02:55,280
Estamos [? pasando?] na cabeza da
listar aquí e algún valor arbitrario,

61
00:02:55,280 --> 00:02:58,600
e queremos comezar o novo xefe
fóra da lista desta función.

62
00:02:58,600 --> 00:03:01,414
É por iso que amosa unha estrela dllnode.

63
00:03:01,414 --> 00:03:02,330
Entón, cales son os pasos?

64
00:03:02,330 --> 00:03:04,496
Son, de novo, moi semellante
a listas ligadas individualmente-

65
00:03:04,496 --> 00:03:05,670
con un engadido adicional.

66
00:03:05,670 --> 00:03:08,900
Queremos aloca espazo para un novo
nó e de verificación para que seguro que é válido.

67
00:03:08,900 --> 00:03:11,510
Queremos encher ese nó up
con toda a información que

68
00:03:11,510 --> 00:03:12,564
quero poñer nel.

69
00:03:12,564 --> 00:03:15,480
A última cousa que necesitamos para o fazer--
extra que necesitamos facer, rather--

70
00:03:15,480 --> 00:03:19,435
é para corrixir o punteiro Anterior
do antigo xefe da lista.

71
00:03:19,435 --> 00:03:21,310
Lembre que, debido
listas de dobremente vinculadas,

72
00:03:21,310 --> 00:03:23,110
podemos avanzar
e que backwards--

73
00:03:23,110 --> 00:03:27,080
significa que cada nodo realmente apunta
a dous outros nós no canto de só un.

74
00:03:27,080 --> 00:03:29,110
E así temos que corrixir
o antigo xefe da lista

75
00:03:29,110 --> 00:03:32,151
para apuntar cara atrás, para o novo xefe da
a lista ligada, o que era algo

76
00:03:32,151 --> 00:03:33,990
nós non temos que facer antes.

77
00:03:33,990 --> 00:03:37,420
E, como antes, nós só voltar un
Punteiro do novo cabeza da lista.

78
00:03:37,420 --> 00:03:38,220
>> Entón aquí está a lista.

79
00:03:38,220 --> 00:03:40,144
Queremos introducir 12 desta lista.

80
00:03:40,144 --> 00:03:42,060
Teña en conta que o diagrama
é un pouco diferente.

81
00:03:42,060 --> 00:03:47,710
Cada nodo contén tres fields--
de datos, e un punteiro de continuación no vermello,

82
00:03:47,710 --> 00:03:50,170
e un punteiro anterior en azul.

83
00:03:50,170 --> 00:03:54,059
Nada vén antes do nodo 15,
polo que a súa anterior punteiro é nulo.

84
00:03:54,059 --> 00:03:55,350
É o inicio da lista.

85
00:03:55,350 --> 00:03:56,560
Non hai nada antes dela.

86
00:03:56,560 --> 00:04:03,350
E nada vén despois do nodo 10, e
polo que é punteiro continuación é nula tamén.

87
00:04:03,350 --> 00:04:05,616
>> Entón, imos engadir 12 a esta lista.

88
00:04:05,616 --> 00:04:08,070
Necesitamos [inaudível] espazo para o no.

89
00:04:08,070 --> 00:04:11,480
Poñemos 12 dentro do mesmo.

90
00:04:11,480 --> 00:04:14,840
E entón, de novo, hai que ser realmente
coidado de non romper a cadea.

91
00:04:14,840 --> 00:04:17,144
Queremos reorganizar a
punteiros na orde correcta.

92
00:04:17,144 --> 00:04:19,519
E ás veces iso pode dizer--
como veremos particularmente

93
00:04:19,519 --> 00:04:24,120
con delete-- que temos algún
punteiros redundante, pero está todo OK.

94
00:04:24,120 --> 00:04:25,750
>> Entón, o que queremos facer primeiro?

95
00:04:25,750 --> 00:04:28,290
Eu recomenda o
Cousas que ten que, probablemente,

96
00:04:28,290 --> 00:04:35,350
facer son para cubrir os punteiros dos 12
nó antes de tocar en calquera outra persoa.

97
00:04:35,350 --> 00:04:38,640
Entón, o que é 12 vai apuntar ao seguinte?

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

99
00:04:39,860 --> 00:04:42,430
O que vén antes de 12?

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

101
00:04:43,640 --> 00:04:46,280
Agora nós encheu o
información extra en 12

102
00:04:46,280 --> 00:04:49,320
polo que ten Anterior, Seguinte e valor.

103
00:04:49,320 --> 00:04:53,505
>> Agora podemos ter 15-- este adicional
paso que estaban falando about-- nós

104
00:04:53,505 --> 00:04:56,590
pode ter 15 puntos ao 12.

105
00:04:56,590 --> 00:04:59,634
E agora podemos mover a cabeza de
a lista encadeada ser 12.

106
00:04:59,634 --> 00:05:02,550
Entón é moi semellante ao que
estaban facendo listas individualmente ligados,

107
00:05:02,550 --> 00:05:06,940
agás para o paso adicional de
conectando o vello cabeza de lista

108
00:05:06,940 --> 00:05:09,810
volta para a nova cabeza da lista.

109
00:05:09,810 --> 00:05:12,170
>> Agora imos finalmente borrar
un nó dunha lista ligada.

110
00:05:12,170 --> 00:05:14,350
Entón, digamos que temos
algunha outra función que

111
00:05:14,350 --> 00:05:18,080
é atopar un nó que quere eliminar
e nos deu un punteiro para exactamente

112
00:05:18,080 --> 00:05:19,710
o no que desexa eliminar.

113
00:05:19,710 --> 00:05:22,360
Nós nin sequera dicir o need--
cabeza aínda está globalmente declarado.

114
00:05:22,360 --> 00:05:23,590
Non necesitamos cabeza aquí.

115
00:05:23,590 --> 00:05:26,830
Todo esta función está a facer é que temos
atopar un punteiro para o que nó

116
00:05:26,830 --> 00:05:28,090
quere se librar de.

117
00:05:28,090 --> 00:05:28,940
Imos librar-se del.

118
00:05:28,940 --> 00:05:31,859
É moito máis doado con
listas dobremente vinculada.

119
00:05:31,859 --> 00:05:33,650
First-- é realmente
só un par de cousas.

120
00:05:33,650 --> 00:05:38,760
Nós só necesitamos corrixir torno
punteiros dos nós de xeito que xa Saltar

121
00:05:38,760 --> 00:05:40,240
o no que desexa eliminar.

122
00:05:40,240 --> 00:05:43,484
E entón podemos eliminar este nodo.

123
00:05:43,484 --> 00:05:45,150
Entón, de novo, estamos só pasando por aquí.

124
00:05:45,150 --> 00:05:49,625
Nós aparentemente decidiron que
queremos eliminar o nodo X.

125
00:05:49,625 --> 00:05:51,500
E, de novo, o que eu son
facendo aqui-- polo maneira--

126
00:05:51,500 --> 00:05:54,580
é un proceso xeral para unha
nó que está no medio.

127
00:05:54,580 --> 00:05:56,547
Hai un par de
caveats extras que

128
00:05:56,547 --> 00:05:59,380
cómpre considerar cando está excluíndo
o inicio da lista

129
00:05:59,380 --> 00:06:01,040
ou o fin da lista.

130
00:06:01,040 --> 00:06:03,730
Hai un par de especial
casos de canto ao manexar alí.

131
00:06:03,730 --> 00:06:07,960
>> Entón, iso funciona para eliminar calquera nodo
no medio do que un lista--

132
00:06:07,960 --> 00:06:11,550
ten un punteiro lexítimo para adiante
e un punteiro lexítimo para atrás,

133
00:06:11,550 --> 00:06:14,460
lexítima punteiro anterior e seguinte.

134
00:06:14,460 --> 00:06:16,530
De novo, se está a traballar
coas extremidades, vostede

135
00:06:16,530 --> 00:06:18,500
precisa para xestionar os
lixeiramente diferente,

136
00:06:18,500 --> 00:06:19,570
e nós non estamos indo a
falar sobre iso agora.

137
00:06:19,570 --> 00:06:21,319
Pero pode, probabelmente,
descubrir o que precisa

138
00:06:21,319 --> 00:06:24,610
por facer só por ver este vídeo.

139
00:06:24,610 --> 00:06:28,910
>> Entón, nós temos illado X. X é o nó
que quere eliminar da lista.

140
00:06:28,910 --> 00:06:30,140
O que imos facer?

141
00:06:30,140 --> 00:06:32,800
En primeiro lugar, necesitamos reorganizar
os punteiros fóra.

142
00:06:32,800 --> 00:06:35,815
Necesitamos reorganizar
9 do próximo para ir máis de 13

143
00:06:35,815 --> 00:06:38,030
e apuntan 10-- que
é o que acabamos de facer.

144
00:06:38,030 --> 00:06:41,180
E tamén necesitamos
reorganizar 10 Anterior

145
00:06:41,180 --> 00:06:44,610
para ligar a 9 en vez de apuntar 13.

146
00:06:44,610 --> 00:06:46,490
>> Entón, de novo, este foi o
diagrama para comezar.

147
00:06:46,490 --> 00:06:47,730
Esta foi a nosa cadea.

148
00:06:47,730 --> 00:06:51,027
Necesitamos ir máis de 13,
pero precisamos tamén preservar

149
00:06:51,027 --> 00:06:52,110
a integridade da lista.

150
00:06:52,110 --> 00:06:54,680
Non quere perder ningún
información en ambas as direccións.

151
00:06:54,680 --> 00:06:59,620
Entón, necesitamos reorganizar
os punteiros coidadosamente

152
00:06:59,620 --> 00:07:02,240
así que non romper a cadea en todo.

153
00:07:02,240 --> 00:07:05,710
>> Así, podemos dicir 9 Seguinte punteiro
apunta para o mesmo lugar

154
00:07:05,710 --> 00:07:08,040
que trece Seguinte
punteiro apunta agora.

155
00:07:08,040 --> 00:07:10,331
Porque somos eventualmente
Vai querer ir máis de 13.

156
00:07:10,331 --> 00:07:13,750
Así, onde queira 13 puntos seguinte,
quere nove para apuntar alí no seu lugar.

157
00:07:13,750 --> 00:07:15,200
Entón é iso.

158
00:07:15,200 --> 00:07:20,370
E entón onde queira que 13 puntos de volta
para o que vén antes de 13,

159
00:07:20,370 --> 00:07:24,800
queremos 10 para apuntar
para que, no canto de 13.

160
00:07:24,800 --> 00:07:29,290
Agora conta, se seguir
as frechas, podemos caer 13

161
00:07:29,290 --> 00:07:32,380
sen realmente perder calquera información.

162
00:07:32,380 --> 00:07:36,002
Nós mantivemos a integridade da lista,
movéndose para a adiante e cara atrás.

163
00:07:36,002 --> 00:07:38,210
E entón podemos só sorte
de limpa-lo un pouco

164
00:07:38,210 --> 00:07:40,930
tirando a lista xuntos.

165
00:07:40,930 --> 00:07:43,270
Entón, nós rearranjado o
punteiros en ambos os dous lados.

166
00:07:43,270 --> 00:07:46,231
E entón nós liberou o X
nó que contiña 13,

167
00:07:46,231 --> 00:07:47,480
e non romper a cadea.

168
00:07:47,480 --> 00:07:50,980
Por iso, fixemos boa.

169
00:07:50,980 --> 00:07:53,000
>> Nota final aquí en listas ligadas.

170
00:07:53,000 --> 00:07:55,990
Así, ambos singly- e dobremente ligada
listas, como vimos,

171
00:07:55,990 --> 00:07:58,959
soporte inserción realmente eficiente
e eliminación de elementos.

172
00:07:58,959 --> 00:08:00,750
Pode moi ben facer
lo en tempo constante.

173
00:08:00,750 --> 00:08:03,333
O que temos que facer para eliminar
un elemento só un segundo atrás?

174
00:08:03,333 --> 00:08:04,440
Nós cambiamos un punteiro.

175
00:08:04,440 --> 00:08:05,920
Nós nos cambiamos outro punteiro.

176
00:08:05,920 --> 00:08:07,915
Nós liberado x-- levou tres operacións.

177
00:08:07,915 --> 00:08:14,500
Sempre leva tres operacións para
eliminar que node-- para liberar un nó.

178
00:08:14,500 --> 00:08:15,280
>> Como é que imos introducir?

179
00:08:15,280 --> 00:08:17,280
Ben, nós somos só sempre
adherencia a principios

180
00:08:17,280 --> 00:08:19,400
se estamos introducindo de forma eficiente.

181
00:08:19,400 --> 00:08:21,964
Entón, necesitamos rearrange--
dependendo se é

182
00:08:21,964 --> 00:08:24,380
un singly- ou dobremente ligada
lista, nós pode ter facer tres

183
00:08:24,380 --> 00:08:26,824
ou como máximo catro operacións.

184
00:08:26,824 --> 00:08:28,365
Pero, de novo, sempre tres ou catro.

185
00:08:28,365 --> 00:08:30,531
Non importa cantas
elementos están na nosa lista,

186
00:08:30,531 --> 00:08:33,549
sempre tres ou catro operations--
así como a eliminación sempre

187
00:08:33,549 --> 00:08:35,320
tres ou catro operacións.

188
00:08:35,320 --> 00:08:36,919
É tempo constante.

189
00:08:36,919 --> 00:08:38,169
Entón, iso é realmente grande.

190
00:08:38,169 --> 00:08:40,620
>> Con matrices, que estaban facendo
algo así como ordenación por inserción.

191
00:08:40,620 --> 00:08:44,739
Probablemente recordar que a inserción
tipo non é un algoritmo de tempo constante.

192
00:08:44,739 --> 00:08:46,030
É realmente moi caro.

193
00:08:46,030 --> 00:08:48,840
Entón, iso é moito mellor para a inserción.

194
00:08:48,840 --> 00:08:51,840
Pero como eu mencionen no
illadamente conectado lista de vídeos,

195
00:08:51,840 --> 00:08:54,030
temos unha desvantaxe aquí tamén, non?

196
00:08:54,030 --> 00:08:57,580
Perdemos a capacidade de
acceder ao azar elementos.

197
00:08:57,580 --> 00:09:02,310
Non podemos dicir, quero elemento número catro
ou o número do elemento 10 dunha lista ligada

198
00:09:02,310 --> 00:09:04,990
Do mesmo xeito que podemos
facelo con unha matriz

199
00:09:04,990 --> 00:09:08,630
ou podemos só directamente índice
en elemento da nosa matriz.

200
00:09:08,630 --> 00:09:10,930
>> E así tentar atopar un
un elemento en lista-- ligada

201
00:09:10,930 --> 00:09:15,880
a investigación é importante--
pode agora ter tempo lineal.

202
00:09:15,880 --> 00:09:18,330
Como a lista está máis tempo,
pode dar un paso adicional

203
00:09:18,330 --> 00:09:22,644
para cada elemento da lista do
a fin de atopar o que estamos buscando.

204
00:09:22,644 --> 00:09:23,560
Polo tanto, hai trade-offs.

205
00:09:23,560 --> 00:09:25,780
Hai un pouco de un pro
e con elemento aquí.

206
00:09:25,780 --> 00:09:29,110
>> E listas dobremente vinculadas non o son
último tipo de combinación de estrutura de datos

207
00:09:29,110 --> 00:09:32,840
que nós imos falar sobre,
levando todo o edificio básico

208
00:09:32,840 --> 00:09:34,865
bloques de montar un C.

209
00:09:34,865 --> 00:09:37,900
Porque, en realidade, podemos
incluso facer mellor que iso

210
00:09:37,900 --> 00:09:41,970
para crear unha estrutura de datos que
pode ser capaz de buscar

211
00:09:41,970 --> 00:09:43,360
na constante de tempo demasiado.

212
00:09:43,360 --> 00:09:46,080
Pero máis sobre iso noutro vídeo.

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

214
00:09:47,150 --> 00:09:49,050
Este é CS50.

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