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: Tudo bem.

4
00:00:05,520 --> 00:00:07,860
Então, se você acabou de terminar que
vídeo em listas individualmente ligados pesaroso

5
00:00:07,860 --> 00:00:09,568
Eu deixei você fora em um
pouco de um cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Mas eu estou feliz que você está aqui para terminar
a história de listas duplamente ligadas.

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

8
00:00:15,250 --> 00:00:18,500
sobre como individualmente ligado
Listas de fazer participar a nossa capacidade

9
00:00:18,500 --> 00:00:22,090
para lidar com informações
em que o número de elementos

10
00:00:22,090 --> 00:00:24,442
ou o número de itens nas
uma lista pode aumentar ou diminuir.

11
00:00:24,442 --> 00:00:26,400
Agora podemos lidar com
algo como que, quando

12
00:00:26,400 --> 00:00:28,310
nós não poderíamos lidar com isso com matrizes.

13
00:00:28,310 --> 00:00:30,560
>> Mas eles sofrem de uma
limitação crítica quais

14
00:00:30,560 --> 00:00:33,790
é que, com um ligado isoladamente
lista, só podemos mover

15
00:00:33,790 --> 00:00:36,200
em uma única direção através da lista.

16
00:00:36,200 --> 00:00:39,010
E a única situação real
onde que pode tornar-se um problema

17
00:00:39,010 --> 00:00:41,250
foi quando nós estávamos tentando
excluir um único elemento.

18
00:00:41,250 --> 00:00:46,000
E nós nem sequer discutir como fazê-lo
em uma lista isoladamente ligada em pseudocódigo.

19
00:00:46,000 --> 00:00:48,797
É certamente factível, mas
ele pode ser um pouco de um aborrecimento.

20
00:00:48,797 --> 00:00:50,630
Então, se você encontrar-se
em uma situação onde

21
00:00:50,630 --> 00:00:53,175
você está tentando excluir
elementos únicos da lista

22
00:00:53,175 --> 00:00:55,430
ou ele vai ser exigido
que você vai ser a exclusão

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

24
00:00:57,970 --> 00:01:02,090
considerar o uso de um ligado duplamente
lista em vez de uma lista isoladamente ligado.

25
00:01:02,090 --> 00:01:06,320
Como as listas duplamente vinculadas permitem que você
para mover ambos frente e para trás

26
00:01:06,320 --> 00:01:09,340
através da lista em vez de
apenas para a frente através da lista--

27
00:01:09,340 --> 00:01:13,950
apenas adicionando um elemento extra
a nossa definição de estrutura

28
00:01:13,950 --> 00:01:16,690
para o nó de lista duplamente vinculada.

29
00:01:16,690 --> 00:01:19,770
>> Novamente, se você não está indo para
ser exclusão elementos únicos

30
00:01:19,770 --> 00:01:24,810
do lista-- porque estamos adicionando
um campo extra para a nossa estrutura

31
00:01:24,810 --> 00:01:28,340
definição, os próprios nós
para listas duplamente ligadas

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

33
00:01:29,550 --> 00:01:31,600
Eles vão levá
-se mais bytes de memória.

34
00:01:31,600 --> 00:01:34,160
E por isso, se isso não é algo
você vai precisar de fazer,

35
00:01:34,160 --> 00:01:36,300
você pode decidir que é
Não vale a pena o trade off

36
00:01:36,300 --> 00:01:39,360
ter que passar o extra
bytes de memória necessária

37
00:01:39,360 --> 00:01:43,940
Para obter uma lista duplamente vinculada se você não estiver
vai ser apagando elementos individuais.

38
00:01:43,940 --> 00:01:46,760
Mas também é legal
para outras coisas também.

39
00:01:46,760 --> 00:01:51,260
>> Então, como eu disse, nós apenas temos que adicionar
um único campo para a nossa estrutura

40
00:01:51,260 --> 00:01:55,360
definition-- esta noção
de um ponteiro anterior.

41
00:01:55,360 --> 00:01:58,620
Assim, com uma lista isoladamente ligado, nós
tem o valor eo ponteiro Em seguida,

42
00:01:58,620 --> 00:02:02,850
assim que a lista duplamente vinculada apenas tem
uma maneira de se mover para trás também.

43
00:02:02,850 --> 00:02:04,960
>> Agora, no individualmente ligado
lista de vídeos, nós falamos

44
00:02:04,960 --> 00:02:07,210
sobre estes são cinco dos
principais coisas que você precisa estar

45
00:02:07,210 --> 00:02:09,449
capaz de fazer para trabalhar com listas ligadas.

46
00:02:09,449 --> 00:02:12,880
E para a maioria destas, o facto
que é uma lista duplamente vinculada

47
00:02:12,880 --> 00:02:14,130
não é realmente um grande salto.

48
00:02:14,130 --> 00:02:17,936
Nós ainda pode pesquisar por apenas
em frente do início ao fim.

49
00:02:17,936 --> 00:02:20,810
Nós ainda podemos criar um nó de
ar, praticamente da mesma maneira.

50
00:02:20,810 --> 00:02:23,591
Podemos eliminar listas bonita
da mesma maneira também.

51
00:02:23,591 --> 00:02:25,340
As únicas coisas que
são sutilmente diferentes,

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

53
00:02:28,970 --> 00:02:33,722
e nós vamos finalmente falar sobre a exclusão
um único elemento da lista bem.

54
00:02:33,722 --> 00:02:35,430
Mais uma vez, muito bonito
os outros três, nós somos

55
00:02:35,430 --> 00:02:37,888
não vai falar sobre eles
agora, porque eles são apenas

56
00:02:37,888 --> 00:02:43,920
ajustes muito menores sobre as idéias discutidas
no vídeo lista isoladamente ligado.

57
00:02:43,920 --> 00:02:46,292
>> Então, vamos inserir um novo nó
em uma lista duplamente vinculada.

58
00:02:46,292 --> 00:02:48,750
Nós conversamos sobre como fazer isso para
listas isoladamente ligada, bem como,

59
00:02:48,750 --> 00:02:52,020
mas há um par de extras
pega com listas duplamente ligadas.

60
00:02:52,020 --> 00:02:55,280
Estavam [? passando?] na cabeça da
listar aqui e algum valor arbitrário,

61
00:02:55,280 --> 00:02:58,600
e nós queremos começar o novo chefe
fora da lista desta função.

62
00:02:58,600 --> 00:03:01,414
É por isso que ele retorna uma estrela dllnode.

63
00:03:01,414 --> 00:03:02,330
Então, quais são os passos?

64
00:03:02,330 --> 00:03:04,496
Eles são, de novo, muito semelhante
a listas ligadas individualmente-

65
00:03:04,496 --> 00:03:05,670
com uma adição adicional.

66
00:03:05,670 --> 00:03:08,900
Queremos aloca espaço para um novo
nó e de verificação para ter certeza que é válido.

67
00:03:08,900 --> 00:03:11,510
Queremos preencher esse nó up
com qualquer informação que

68
00:03:11,510 --> 00:03:12,564
quero colocar nele.

69
00:03:12,564 --> 00:03:15,480
A última coisa de que precisamos para o fazer--
extra coisa que precisamos fazer, rather--

70
00:03:15,480 --> 00:03:19,435
é para corrigir o ponteiro Anterior
do antigo chefe da lista.

71
00:03:19,435 --> 00:03:21,310
Lembre-se que, devido
listas de duplamente vinculadas,

72
00:03:21,310 --> 00:03:23,110
podemos avançar
e que backwards--

73
00:03:23,110 --> 00:03:27,080
significa que cada nó realmente aponta
a dois outros nós em vez de apenas um.

74
00:03:27,080 --> 00:03:29,110
E assim temos de corrigir
o antigo chefe da lista

75
00:03:29,110 --> 00:03:32,151
para apontar para trás, para o novo chefe da
a lista ligada, o que era algo

76
00:03:32,151 --> 00:03:33,990
nós não temos que fazer antes.

77
00:03:33,990 --> 00:03:37,420
E, como antes, nós apenas retornar um
Ponteiro para o novo cabeça da lista.

78
00:03:37,420 --> 00:03:38,220
>> Então aqui está uma lista.

79
00:03:38,220 --> 00:03:40,144
Queremos inserir 12 nesta lista.

80
00:03:40,144 --> 00:03:42,060
Observe que o diagrama
é um pouco diferente.

81
00:03:42,060 --> 00:03:47,710
Cada nó contém três fields--
de dados, e um ponteiro de seguida no vermelho,

82
00:03:47,710 --> 00:03:50,170
e um ponteiro anterior em azul.

83
00:03:50,170 --> 00:03:54,059
Nada vem antes do nó 15,
pelo que a sua anterior ponteiro é nulo.

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

85
00:03:55,350 --> 00:03:56,560
Não há nada antes dela.

86
00:03:56,560 --> 00:04:03,350
E nada vem depois do nó 10, e
por isso é ponteiro seguida é nula também.

87
00:04:03,350 --> 00:04:05,616
>> Então, vamos adicionar 12 a esta lista.

88
00:04:05,616 --> 00:04:08,070
Precisamos [inaudível] espaço para o nó.

89
00:04:08,070 --> 00:04:11,480
Nós colocamos 12 dentro do mesmo.

90
00:04:11,480 --> 00:04:14,840
E então, novamente, temos de ser realmente
cuidado para não quebrar a cadeia.

91
00:04:14,840 --> 00:04:17,144
Queremos reorganizar a
ponteiros na ordem correta.

92
00:04:17,144 --> 00:04:19,519
E às vezes isso pode dizer--
como veremos particularmente

93
00:04:19,519 --> 00:04:24,120
com delete-- que temos algum
ponteiros redundante, mas está tudo OK.

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

95
00:04:25,750 --> 00:04:28,290
Eu recomendaria o
Coisas que você deve, provavelmente,

96
00:04:28,290 --> 00:04:35,350
fazer são para preencher os ponteiros dos 12
nó antes de tocar em qualquer outra pessoa.

97
00:04:35,350 --> 00:04:38,640
Então, o que é 12 vai apontar para o próximo?

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

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

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

101
00:04:43,640 --> 00:04:46,280
Agora nós encheu o
informação extra em 12

102
00:04:46,280 --> 00:04:49,320
por isso tem Anterior, Próximo e valor.

103
00:04:49,320 --> 00:04:53,505
>> Agora podemos ter 15-- este adicional
passo nós estávamos falando about-- nós

104
00:04:53,505 --> 00:04:56,590
pode ter 15 pontos de volta para 12.

105
00:04:56,590 --> 00:04:59,634
E agora nós podemos mover a cabeça de
a lista encadeada também ser 12.

106
00:04:59,634 --> 00:05:02,550
Então é muito semelhante ao que
estavam fazendo com listas individualmente ligados,

107
00:05:02,550 --> 00:05:06,940
excepto para o passo adicional de
conectando o velho cabeça de lista

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

109
00:05:09,810 --> 00:05:12,170
>> Agora vamos finalmente apagar
um nó de uma lista ligada.

110
00:05:12,170 --> 00:05:14,350
Então, digamos que temos
alguma outra função que

111
00:05:14,350 --> 00:05:18,080
é encontrar um nó que deseja excluir
e nos deu um ponteiro para exatamente

112
00:05:18,080 --> 00:05:19,710
o nó que deseja excluir.

113
00:05:19,710 --> 00:05:22,360
Nós nem sequer dizer o need--
cabeça ainda está globalmente declarado.

114
00:05:22,360 --> 00:05:23,590
Nós não precisamos de cabeça aqui.

115
00:05:23,590 --> 00:05:26,830
Tudo esta função está a fazer é que nós temos
encontrado um ponteiro para exatamente o que nó

116
00:05:26,830 --> 00:05:28,090
quer se livrar de.

117
00:05:28,090 --> 00:05:28,940
Vamos livrar-se dele.

118
00:05:28,940 --> 00:05:31,859
É muito mais fácil com
listas duplamente vinculada.

119
00:05:31,859 --> 00:05:33,650
First-- é realmente
apenas um par de coisas.

120
00:05:33,650 --> 00:05:38,760
Nós só precisamos corrigir torno
ponteiros dos nós de modo que eles Pular

121
00:05:38,760 --> 00:05:40,240
o nó que deseja excluir.

122
00:05:40,240 --> 00:05:43,484
E então podemos excluir esse nó.

123
00:05:43,484 --> 00:05:45,150
Então, novamente, estamos apenas passando por aqui.

124
00:05:45,150 --> 00:05:49,625
Nós aparentemente decidiram que
queremos excluir o nó X.

125
00:05:49,625 --> 00:05:51,500
E, novamente, o que eu sou
fazendo aqui-- pelo maneira--

126
00:05:51,500 --> 00:05:54,580
é um processo geral para uma
nó que está no meio.

127
00:05:54,580 --> 00:05:56,547
Há um par de
caveats extras que você

128
00:05:56,547 --> 00:05:59,380
precisa considerar quando você está excluindo
o início da lista

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

130
00:06:01,040 --> 00:06:03,730
Há um par de especial
casos de canto ao lidar com lá.

131
00:06:03,730 --> 00:06:07,960
>> Então, isso funciona para excluir qualquer nó
no meio do que um lista--

132
00:06:07,960 --> 00:06:11,550
tem um ponteiro legítimo para a frente
e um ponteiro legítimo para trás,

133
00:06:11,550 --> 00:06:14,460
legítima ponteiro anterior e próxima.

134
00:06:14,460 --> 00:06:16,530
Novamente, se você está trabalhando
com as extremidades, você

135
00:06:16,530 --> 00:06:18,500
precisa para lidar com os
ligeiramente diferente,

136
00:06:18,500 --> 00:06:19,570
e nós não estamos indo para
falar sobre isso agora.

137
00:06:19,570 --> 00:06:21,319
Mas você pode, provavelmente,
descobrir o que precisa

138
00:06:21,319 --> 00:06:24,610
a ser feito apenas por assistir este vídeo.

139
00:06:24,610 --> 00:06:28,910
>> Então, nós temos isolado X. X é o nó
que deseja excluir da lista.

140
00:06:28,910 --> 00:06:30,140
O que nós fazemos?

141
00:06:30,140 --> 00:06:32,800
Em primeiro lugar, precisamos reorganizar
os ponteiros fora.

142
00:06:32,800 --> 00:06:35,815
Precisamos reorganizar
9 do próximo para saltar mais de 13

143
00:06:35,815 --> 00:06:38,030
e apontam para 10-- que
é o que acabamos de fazer.

144
00:06:38,030 --> 00:06:41,180
E também precisamos
reorganizar 10 Anterior

145
00:06:41,180 --> 00:06:44,610
para apontar para 9 em vez de apontar para 13.

146
00:06:44,610 --> 00:06:46,490
>> Então, novamente, este foi o
diagrama para começar.

147
00:06:46,490 --> 00:06:47,730
Esta foi a nossa cadeia.

148
00:06:47,730 --> 00:06:51,027
Precisamos saltar mais de 13,
mas precisamos também preservar

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

150
00:06:52,110 --> 00:06:54,680
Não quer perder nenhum
informação em ambas as direcções.

151
00:06:54,680 --> 00:06:59,620
Então, precisamos reorganizar
os ponteiros cuidadosamente

152
00:06:59,620 --> 00:07:02,240
assim que nós não quebrar a cadeia em tudo.

153
00:07:02,240 --> 00:07:05,710
>> Assim, podemos dizer 9 Próximo ponteiro
aponta para o mesmo lugar

154
00:07:05,710 --> 00:07:08,040
que treze Próximo
ponteiro aponta agora.

155
00:07:08,040 --> 00:07:10,331
Porque nós somos, eventualmente,
vai querer saltar mais de 13.

156
00:07:10,331 --> 00:07:13,750
Assim, onde quer 13 pontos seguinte, você
quer nove para apontar lá em vez disso.

157
00:07:13,750 --> 00:07:15,200
Então é isso.

158
00:07:15,200 --> 00:07:20,370
E então onde quer que 13 pontos de volta
para, o que vem antes de 13,

159
00:07:20,370 --> 00:07:24,800
queremos 10 para apontar
para que, em vez de 13.

160
00:07:24,800 --> 00:07:29,290
Agora note, se você seguir
as setas, podemos cair 13

161
00:07:29,290 --> 00:07:32,380
sem realmente perder qualquer informação.

162
00:07:32,380 --> 00:07:36,002
Nós mantivemos a integridade da lista,
movendo-se para a frente e para trás.

163
00:07:36,002 --> 00:07:38,210
E então nós podemos apenas sorte
de limpá-lo um pouco

164
00:07:38,210 --> 00:07:40,930
puxando a lista juntos.

165
00:07:40,930 --> 00:07:43,270
Então, nós rearranjado o
ponteiros em ambos os lados.

166
00:07:43,270 --> 00:07:46,231
E então nós libertou o X
nó que continha 13,

167
00:07:46,231 --> 00:07:47,480
e nós não quebrar a cadeia.

168
00:07:47,480 --> 00:07:50,980
Por isso, fizemos boa.

169
00:07:50,980 --> 00:07:53,000
>> Nota final aqui em listas ligadas.

170
00:07:53,000 --> 00:07:55,990
Assim, ambos singly- e duplamente ligada
listas, como vimos,

171
00:07:55,990 --> 00:07:58,959
suporte inserção realmente eficiente
e eliminação de elementos.

172
00:07:58,959 --> 00:08:00,750
Você pode muito bem fazer
lo em tempo constante.

173
00:08:00,750 --> 00:08:03,333
O que temos que fazer para eliminar
um elemento apenas um segundo atrás?

174
00:08:03,333 --> 00:08:04,440
Nós mudamos um ponteiro.

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

176
00:08:05,920 --> 00:08:07,915
Nós libertado x-- levou três operações.

177
00:08:07,915 --> 00:08:14,500
Sempre leva três operações para
excluir que node-- para libertar um nó.

178
00:08:14,500 --> 00:08:15,280
>> Como é que vamos inserir?

179
00:08:15,280 --> 00:08:17,280
Bem, nós somos apenas sempre
aderência no início

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

181
00:08:19,400 --> 00:08:21,964
Então, precisamos rearrange--
dependendo se é

182
00:08:21,964 --> 00:08:24,380
um singly- ou duplamente ligada
lista, nós pode precisar fazer três

183
00:08:24,380 --> 00:08:26,824
ou no máximo quatro operações.

184
00:08:26,824 --> 00:08:28,365
Mas, novamente, é sempre três ou quatro.

185
00:08:28,365 --> 00:08:30,531
Não importa quantas
elementos estão em nossa lista,

186
00:08:30,531 --> 00:08:33,549
é sempre três ou quatro operations--
assim como a eliminação é sempre

187
00:08:33,549 --> 00:08:35,320
três ou quatro operações.

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

189
00:08:36,919 --> 00:08:38,169
Então, isso é realmente grande.

190
00:08:38,169 --> 00:08:40,620
>> Com matrizes, nós estávamos fazendo
algo como ordenação por inserção.

191
00:08:40,620 --> 00:08:44,739
Você provavelmente recordar que a inserção
tipo não é um algoritmo de tempo constante.

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

193
00:08:46,030 --> 00:08:48,840
Então, isso é muito melhor para a inserção.

194
00:08:48,840 --> 00:08:51,840
Mas como eu mencionei no
isoladamente ligado lista de vídeos,

195
00:08:51,840 --> 00:08:54,030
nós temos uma desvantagem aqui também, certo?

196
00:08:54,030 --> 00:08:57,580
Perdemos a capacidade de
acessar aleatoriamente elementos.

197
00:08:57,580 --> 00:09:02,310
Nós não podemos dizer, eu quero elemento número quatro
ou o número do elemento 10 de uma lista ligada

198
00:09:02,310 --> 00:09:04,990
Da mesma forma que pudermos
fazer isso com uma matriz

199
00:09:04,990 --> 00:09:08,630
ou podemos apenas diretamente índice
em elemento de nossa matriz.

200
00:09:08,630 --> 00:09:10,930
>> E assim tentar encontrar um
um elemento em lista-- ligada

201
00:09:10,930 --> 00:09:15,880
se a pesquisa é importante--
pode agora ter tempo linear.

202
00:09:15,880 --> 00:09:18,330
Como a lista fica mais tempo,
pode dar um passo adicional

203
00:09:18,330 --> 00:09:22,644
para cada elemento na lista do
a fim de encontrar o que estamos procurando.

204
00:09:22,644 --> 00:09:23,560
Portanto, há trade-offs.

205
00:09:23,560 --> 00:09:25,780
Há um pouco de um pro
e con elemento aqui.

206
00:09:25,780 --> 00:09:29,110
>> E listas duplamente vinculadas não o são
último tipo de combinação de estrutura de dados

207
00:09:29,110 --> 00:09:32,840
que nós vamos falar sobre,
levando todo o edifício básico

208
00:09:32,840 --> 00:09:34,865
blocos de montar um C.

209
00:09:34,865 --> 00:09:37,900
Porque, na verdade, nós podemos
até mesmo fazer melhor do que isso

210
00:09:37,900 --> 00:09:41,970
para criar uma estrutura de dados que
você pode ser capaz de pesquisar

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

212
00:09:43,360 --> 00:09:46,080
Mas mais sobre isso em outro vídeo.

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

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

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