1 00:00:00,000 --> 00:00:02,832 >> [Música tocando] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, então a Neste ponto do curso, 4 00:00:08,560 --> 00:00:15,300 nós cobrimos um monte de os conceitos básicos de C. Sabemos muito sobre variáveis, arrays, 5 00:00:15,300 --> 00:00:17,610 ponteiros, todas essas coisas boas. 6 00:00:17,610 --> 00:00:21,610 Aqueles são todos os tipos de construção para ver como os fundamentos, 7 00:00:21,610 --> 00:00:23,880 mas podemos fazer mais, certo? 8 00:00:23,880 --> 00:00:27,930 Podemos combinar as coisas em conjunto de maneiras interessantes. 9 00:00:27,930 --> 00:00:31,010 >> E assim vamos fazer isso, vamos começar a ramificar-se do que C nos dá, 10 00:00:31,010 --> 00:00:35,270 e começar a criar nossos próprios dados Usando estas estruturas edifício 11 00:00:35,270 --> 00:00:40,590 blocos juntos para fazer algo realmente valioso, útil. 12 00:00:40,590 --> 00:00:43,420 Uma maneira de fazer isso é para falar sobre coleções. 13 00:00:43,420 --> 00:00:48,360 Então, até agora nós tivemos um tipo de dados estrutura para representar as coleções 14 00:00:48,360 --> 00:00:51,030 gostaria de valores, valores semelhantes. 15 00:00:51,030 --> 00:00:52,350 Isso seria uma matriz. 16 00:00:52,350 --> 00:00:57,020 Temos coleções de inteiros, ou coleções de personagens e assim por diante. 17 00:00:57,020 --> 00:01:00,890 >> Estruturas também são um tipo de dados estrutura para a coleta de informações, 18 00:01:00,890 --> 00:01:03,220 mas não é para coletar como valores. 19 00:01:03,220 --> 00:01:08,090 Geralmente mistura diferentes tipos de dados juntos dentro de uma única caixa. 20 00:01:08,090 --> 00:01:10,750 Mas não é em si usado para encadear 21 00:01:10,750 --> 00:01:16,920 ou ligar juntos semelhante itens, como uma matriz. 22 00:01:16,920 --> 00:01:20,960 Arrays são grandes para elemento de olhar para cima, mas recordação 23 00:01:20,960 --> 00:01:24,262 que é muito difícil para inserir uma matriz, 24 00:01:24,262 --> 00:01:26,470 a menos que nós estamos inserindo no o final dessa matriz. 25 00:01:26,470 --> 00:01:29,730 >> E o melhor exemplo que eu tenho para isso é a ordenação por inserção. 26 00:01:29,730 --> 00:01:31,650 Se bem se lembram o nosso vídeo na ordenação por inserção, 27 00:01:31,650 --> 00:01:34,110 havia um monte de despesa envolvida em ter 28 00:01:34,110 --> 00:01:37,970 para pegar elementos, e transferi-los para fora do caminho para caber algo 29 00:01:37,970 --> 00:01:41,290 no meio de sua matriz. 30 00:01:41,290 --> 00:01:44,690 Arrays também sofrem de outro problema, que é a inflexibilidade. 31 00:01:44,690 --> 00:01:47,150 Quando declaramos uma matriz, obtemos um tiro nele. 32 00:01:47,150 --> 00:01:49,790 Nós começamos a dizer, eu quero este muitos elementos. 33 00:01:49,790 --> 00:01:51,940 Pode ser de 100, ele pode ser 1000, pode 34 00:01:51,940 --> 00:01:55,930 ser X, onde X é um número que o utilizador deu-nos em um prompt de comando ou no 35 00:01:55,930 --> 00:01:56,630 line. 36 00:01:56,630 --> 00:01:59,905 >> Mas nós só temos uma chance para ele, nós não consegue, então, dizer oh, na verdade eu 37 00:01:59,905 --> 00:02:04,360 precisava de 101, ou eu precisava x mais 20. 38 00:02:04,360 --> 00:02:07,910 Tarde demais, que já declarou o array, e se quisermos obter 101 ou x 39 00:02:07,910 --> 00:02:12,050 acrescido de 20, temos a declarar uma matriz totalmente diferente, 40 00:02:12,050 --> 00:02:15,540 copiar todos os elementos da matriz sobre, e então nós temos o suficiente. 41 00:02:15,540 --> 00:02:19,880 E se estamos errados novamente, o que se nós realmente precisamos 102, ou x mais 40, 42 00:02:19,880 --> 00:02:21,970 nós temos que fazer isso de novo. 43 00:02:21,970 --> 00:02:26,250 Então, eles estão muito inflexível para redimensionar os nossos dados, 44 00:02:26,250 --> 00:02:29,360 mas se combinam alguns dos princípios básicos que nós já 45 00:02:29,360 --> 00:02:33,230 Aprendi sobre ponteiros e estruturas, em especial através de memória dinâmica 46 00:02:33,230 --> 00:02:36,180 alocação com malloc, nós pode colocar esses pedaços juntos 47 00:02:36,180 --> 00:02:40,960 para criar um novo dado um structure-- isoladamente lista poderíamos dizer-- ligado 48 00:02:40,960 --> 00:02:45,400 que nos permite crescer e encolher uma coleção de valores 49 00:02:45,400 --> 00:02:48,800 e não teremos qualquer espaço desperdiçado. 50 00:02:48,800 --> 00:02:53,320 >> Então, novamente, nós chamamos essa idéia, essa noção, uma lista ligada. 51 00:02:53,320 --> 00:02:56,320 Em particular, neste vídeo que estamos falando lista vinculada isoladamente, 52 00:02:56,320 --> 00:02:59,185 e, em seguida, um outro vídeo vamos falar listas sobre duplamente ligadas, que 53 00:02:59,185 --> 00:03:01,560 é apenas uma variação sobre um tema aqui. 54 00:03:01,560 --> 00:03:05,200 Mas uma lista vinculada isoladamente é composto por nós, 55 00:03:05,200 --> 00:03:08,559 nós apenas ser um term-- abstrato é apenas algo que eu estou chamando 56 00:03:08,559 --> 00:03:10,350 que é uma espécie de estrutura, basicamente, eu sou? 57 00:03:10,350 --> 00:03:16,190 Basta ir a chamá-lo de um node-- e este nó tem dois membros, ou dois campos. 58 00:03:16,190 --> 00:03:20,300 Tem de dados, geralmente um inteiro, um personagem float, 59 00:03:20,300 --> 00:03:23,790 ou poderia ser algum outro tipo de dados que você tenha definido com um tipo def. 60 00:03:23,790 --> 00:03:29,290 E que contém um apontador para outro nó do mesmo tipo. 61 00:03:29,290 --> 00:03:34,710 >> Portanto, temos duas coisas dentro de esse nó, de dados e um ponteiro 62 00:03:34,710 --> 00:03:36,380 para outro nó. 63 00:03:36,380 --> 00:03:39,370 E se você começar a visualizar isso, você pode pensar sobre isso 64 00:03:39,370 --> 00:03:42,280 como uma cadeia de nós que estão ligados entre si. 65 00:03:42,280 --> 00:03:45,070 Temos o primeiro nó, ele contém os dados, e um ponteiro 66 00:03:45,070 --> 00:03:49,110 para o segundo nó, a qual contém de dados, e um ponteiro para o terceiro nó. 67 00:03:49,110 --> 00:03:52,940 E é por isso que chamamos de lista ligada, eles estão ligados entre si. 68 00:03:52,940 --> 00:03:56,070 >> O que faz este especial estrutura de nó parece? 69 00:03:56,070 --> 00:04:01,120 Bem, se você se lembra do nosso vídeo sobre definir tipos personalizados, com o tipo de definição, 70 00:04:01,120 --> 00:04:05,400 podemos definir uma structure-- e digite definir uma estrutura como esta. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, e então eu sou usando a palavra valor arbitrariamente aqui 72 00:04:11,240 --> 00:04:13,891 para indicar qualquer tipo de dados realmente. 73 00:04:13,891 --> 00:04:16,890 Você poderia passar um inteiro ou float, você pode ter o que quiser. 74 00:04:16,890 --> 00:04:19,389 Não está restrito a apenas inteiros, ou qualquer coisa assim. 75 00:04:19,389 --> 00:04:22,790 Assim, o valor é apenas uma arbitrária Tipo de dados e, em seguida, um ponteiro 76 00:04:22,790 --> 00:04:26,310 para outro nó do mesmo tipo. 77 00:04:26,310 --> 00:04:29,690 >> Agora, há um pouco de captura aqui com uma estrutura que define 78 00:04:29,690 --> 00:04:33,030 quando é uma estrutura auto referencial. 79 00:04:33,030 --> 00:04:35,340 Eu tenho que ter um temporário nomear para minha estrutura. 80 00:04:35,340 --> 00:04:37,640 No final do dia, claramente querem chamá-lo 81 00:04:37,640 --> 00:04:43,030 sll nó, que é em última análise, o novo nomear parte da minha definição de tipo, 82 00:04:43,030 --> 00:04:47,450 mas eu não posso usar nó sll no meio deste. 83 00:04:47,450 --> 00:04:51,430 A razão de ser, eu não tenho criou um tipo chamado nó sll 84 00:04:51,430 --> 00:04:55,200 até que eu bati esse ponto final aqui. 85 00:04:55,200 --> 00:04:59,720 Até aquele momento, eu tenho que ter uma outra maneira de se referir a este tipo de dados. 86 00:04:59,720 --> 00:05:02,440 >> E esta é uma auto- tipo de dados referencial. 87 00:05:02,440 --> 00:05:06,314 ; S um tipo de dados que contém uma estrutura de dados, 88 00:05:06,314 --> 00:05:08,480 e um ponteiro para uma outra estrutura do mesmo tipo. 89 00:05:08,480 --> 00:05:11,750 Então eu preciso ser capaz de se referir a este tipo de dados, pelo menos temporariamente, 90 00:05:11,750 --> 00:05:14,910 assim dando-lhe um temporária nome de struct sllist 91 00:05:14,910 --> 00:05:18,540 permite-me, em seguida, dizer que eu quero um ponteiro para outro sllist struct, 92 00:05:18,540 --> 00:05:24,690 uma estrela struct sllist, e, em seguida, depois que eu tiver concluído a definição, 93 00:05:24,690 --> 00:05:27,220 Agora eu posso chamar este tipo de um nó de SLL. 94 00:05:27,220 --> 00:05:30,520 >> É por isso que você vê que há um nome temporário aqui, 95 00:05:30,520 --> 00:05:31,879 mas um nome permanente aqui. 96 00:05:31,879 --> 00:05:33,920 Às vezes você pode ver definições de estrutura, 97 00:05:33,920 --> 00:05:36,570 por exemplo, que não são auto referencial, que 98 00:05:36,570 --> 00:05:39,390 não tem um nome especificador aqui. 99 00:05:39,390 --> 00:05:43,040 Ele apenas diria typedef struct, abrir chaveta e, em seguida, defini-lo. 100 00:05:43,040 --> 00:05:45,620 Mas se você é struct é auto- referencial, como este é, 101 00:05:45,620 --> 00:05:49,010 você precisa especificar um nome do tipo temporário. 102 00:05:49,010 --> 00:05:51,310 Mas, afinal, agora que fizemos isso, 103 00:05:51,310 --> 00:05:53,620 podemos apenas referir-se a esses nós, estas unidades, 104 00:05:53,620 --> 00:05:57,900 como nodos SLL para fins do resto deste vídeo. 105 00:05:57,900 --> 00:06:00,900 >> Tudo bem, então sabemos como criar um nó lista ligada. 106 00:06:00,900 --> 00:06:03,240 Nós sabemos como definir um nó de lista ligada. 107 00:06:03,240 --> 00:06:06,670 Agora, se nós estamos indo para começar usando-os para coletar informações, 108 00:06:06,670 --> 00:06:10,360 há um par de operações que precisam entender e trabalhar com ele. 109 00:06:10,360 --> 00:06:12,860 Precisamos saber como criar uma lista ligada fora do ar. 110 00:06:12,860 --> 00:06:14,901 Se não há nenhuma lista já, queremos começar um. 111 00:06:14,901 --> 00:06:16,960 Então, precisamos ser capazes para criar uma lista ligada, 112 00:06:16,960 --> 00:06:19,130 precisamos provavelmente procurar através da lista de links 113 00:06:19,130 --> 00:06:21,830 para encontrar um elemento que estamos procurando. 114 00:06:21,830 --> 00:06:24,430 Precisamos ser capazes de inserir coisas novas para a lista, 115 00:06:24,430 --> 00:06:25,930 queremos que a nossa lista para ser capaz de crescer. 116 00:06:25,930 --> 00:06:28,638 E da mesma forma, queremos ser capazes para apagar as coisas da nossa lista, 117 00:06:28,638 --> 00:06:30,250 queremos que a nossa lista para ser capaz de encolher. 118 00:06:30,250 --> 00:06:32,160 E no final da nossa programas, especialmente 119 00:06:32,160 --> 00:06:34,550 se você se lembra que nós somos alocar dinamicamente a memória 120 00:06:34,550 --> 00:06:38,337 para construir estas listas normalmente, queremos libertar toda a memória que 121 00:06:38,337 --> 00:06:39,670 quando terminarmos de trabalhar com ele. 122 00:06:39,670 --> 00:06:44,627 E por isso temos de ser capazes de apagar um Toda lista ligada em uma rusga falhar. 123 00:06:44,627 --> 00:06:46,460 Então, vamos passar por Algumas destas operações 124 00:06:46,460 --> 00:06:51,192 e como podemos visualizá-los, falando em código pseudocódigo especificamente. 125 00:06:51,192 --> 00:06:53,150 Por isso, queremos criar uma lista ligada, então talvez nós 126 00:06:53,150 --> 00:06:56,480 quer definir uma função com este protótipo. 127 00:06:56,480 --> 00:07:01,690 sll estrela nó, criar, e eu estou passando em um argumento, alguns dados arbitrários 128 00:07:01,690 --> 00:07:05,530 digite novamente, de algum tipo de dados arbitrário. 129 00:07:05,530 --> 00:07:10,482 Mas eu estou returning-- esta função deve voltar para mim um ponteiro, a um isoladamente 130 00:07:10,482 --> 00:07:11,190 nó lista ligada. 131 00:07:11,190 --> 00:07:14,050 Mais uma vez, estamos tentando criar uma lista ligada fora do ar, 132 00:07:14,050 --> 00:07:17,900 então eu preciso de um ponteiro para essa lista quando eu terminar. 133 00:07:17,900 --> 00:07:19,420 >> Então, quais são as etapas envolvidas aqui? 134 00:07:19,420 --> 00:07:20,960 Bem, a primeira coisa que eu sou vai fazer é dinamicamente 135 00:07:20,960 --> 00:07:22,550 alocar espaço para um novo nó. 136 00:07:22,550 --> 00:07:26,689 Mais uma vez, estamos criando-o para fora da fina ar, por isso precisamos de espaço malloc para ele. 137 00:07:26,689 --> 00:07:28,480 E, claro, imediatamente depois que malloc, 138 00:07:28,480 --> 00:07:31,692 sempre certifique-se de que o nosso pointer-- nós não voltar nulo. 139 00:07:31,692 --> 00:07:33,650 Porque se nós tentamos e deferência um ponteiro nulo, 140 00:07:33,650 --> 00:07:36,190 vamos sofrer um segfault e nós não queremos isso. 141 00:07:36,190 --> 00:07:39,510 >> Então, nós queremos preencher o campo, queremos inicializar o campo de valor 142 00:07:39,510 --> 00:07:41,690 e inicializar o próximo campo. 143 00:07:41,690 --> 00:07:45,450 E então nós queremos a--, eventualmente, como o função protótipo indicates-- queremos 144 00:07:45,450 --> 00:07:49,940 para retornar um ponteiro para um nó SLL. 145 00:07:49,940 --> 00:07:51,710 Então, o que fazer este olhar como visualmente? 146 00:07:51,710 --> 00:07:55,230 Bem, primeiro vamos dinamicamente alocar espaço para um novo nó SLL, 147 00:07:55,230 --> 00:07:58,320 por isso, que é malloc-- uma representação visual 148 00:07:58,320 --> 00:08:00,020 do nó de que acabamos de criar. 149 00:08:00,020 --> 00:08:02,757 E nós certifique-se não é null-- neste caso, 150 00:08:02,757 --> 00:08:04,840 a imagem não teria aparecido se era nulo, 151 00:08:04,840 --> 00:08:07,298 teríamos ficar sem memória, por isso, é bom para ir lá. 152 00:08:07,298 --> 00:08:10,200 Então, agora nós estamos para o passo C, inicializar o campo nodos valor. 153 00:08:10,200 --> 00:08:12,280 Bem, com base nessa função chamar que estou usando aqui, 154 00:08:12,280 --> 00:08:16,700 parece que eu quero passar em 6, então eu vou 6 no campo de valor. 155 00:08:16,700 --> 00:08:18,865 Agora, inicializar o próximo campo. 156 00:08:18,865 --> 00:08:21,640 Bem, o que eu vou fazer lá, não há nada ao lado, à direita, 157 00:08:21,640 --> 00:08:23,600 esta é a única coisa na lista. 158 00:08:23,600 --> 00:08:27,206 Então, qual é a próxima coisa na lista? 159 00:08:27,206 --> 00:08:29,660 >> Não deve apontar para qualquer coisa, certo. 160 00:08:29,660 --> 00:08:33,600 Não há mais nada lá, então o que é o conceito sabemos de que é nothing-- 161 00:08:33,600 --> 00:08:35,638 ponteiros para nada? 162 00:08:35,638 --> 00:08:37,929 Deve ser talvez nós queremos para colocar um ponteiro nulo lá, 163 00:08:37,929 --> 00:08:40,178 e eu vou representar o nulo ponteiro como apenas uma caixa vermelha, 164 00:08:40,178 --> 00:08:41,559 não podemos ir mais longe. 165 00:08:41,559 --> 00:08:44,430 Como veremos um pouco mais tarde, vamos ter eventualmente cadeias 166 00:08:44,430 --> 00:08:46,330 de setas que ligam destes nós, em conjunto 167 00:08:46,330 --> 00:08:48,480 mas quando você bate a caixa vermelha, que é nula, 168 00:08:48,480 --> 00:08:51,150 não podemos ir mais longe, esse é o fim da lista. 169 00:08:51,150 --> 00:08:53,960 >> E, finalmente, nós só queremos retornar um ponteiro para esse nó. 170 00:08:53,960 --> 00:08:56,160 Então, vamos chamá-lo de novo, e voltará novo 171 00:08:56,160 --> 00:08:59,370 de modo que pode ser utilizado em qualquer função criou. 172 00:08:59,370 --> 00:09:03,100 Então lá vamos nós, Nós criamos um isoladamente nó lista ligada fora do ar, 173 00:09:03,100 --> 00:09:05,920 e agora temos uma lista podemos trabalhar com. 174 00:09:05,920 --> 00:09:08,260 >> Agora, vamos dizer que já tem uma grande cadeia, 175 00:09:08,260 --> 00:09:09,800 e nós queremos encontrar algo nele. 176 00:09:09,800 --> 00:09:12,716 E queremos uma função que está acontecendo para retornar verdadeiro ou falso, dependendo 177 00:09:12,716 --> 00:09:15,840 sobre se existe um valor na lista. 178 00:09:15,840 --> 00:09:18,160 Um protótipo de função, ou declaração para essa função, 179 00:09:18,160 --> 00:09:23,320 pode parecer isto-- bool encontrar, e então queremos passar em dois argumentos. 180 00:09:23,320 --> 00:09:26,996 >> O primeiro, é um ponteiro para o primeiro elemento da lista ligada. 181 00:09:26,996 --> 00:09:29,620 Isso é realmente algo que você vai sempre quer acompanhar, 182 00:09:29,620 --> 00:09:33,110 e, na verdade, pode ser algo que você mesmo colocar em uma variável global. 183 00:09:33,110 --> 00:09:35,360 Depois de criar uma lista, você sempre, sempre 184 00:09:35,360 --> 00:09:38,990 quer manter o controle do próprio primeiro elemento da lista. 185 00:09:38,990 --> 00:09:43,690 Dessa forma, você pode se referir a todos os outros elementos por apenas seguindo a cadeia, 186 00:09:43,690 --> 00:09:47,300 sem ter que manter ponteiros intacta para cada elemento. 187 00:09:47,300 --> 00:09:50,920 Você só precisa manter o controle do primeiro um, se eles estão todos acorrentados. 188 00:09:50,920 --> 00:09:52,460 >> E, em seguida, a segunda coisa estamos passando novamente 189 00:09:52,460 --> 00:09:54,376 é arbitrariamente some-- seja qual for o tipo de dados que estamos 190 00:09:54,376 --> 00:09:59,640 procurando existe dentro de espero que um dos nós da lista. 191 00:09:59,640 --> 00:10:00,980 Então, quais são os passos? 192 00:10:00,980 --> 00:10:04,250 Bem, a primeira coisa que fazemos é criamos um ponteiro transversal 193 00:10:04,250 --> 00:10:06,015 apontando para a cabeça listas. 194 00:10:06,015 --> 00:10:08,890 Bem, por que fazemos isso, nós já ter um ponteiro na cabeça listas, 195 00:10:08,890 --> 00:10:10,974 por que não vamos apenas mover que um em torno de? 196 00:10:10,974 --> 00:10:13,140 Bem, como eu disse, que é realmente importante para nós 197 00:10:13,140 --> 00:10:17,580 manter sempre o controle do primeiro elemento da lista. 198 00:10:17,580 --> 00:10:21,270 E por isso é realmente melhor para criar uma duplicata de que, 199 00:10:21,270 --> 00:10:25,350 e usar isso para se movimentar, pelo que nunca acidentalmente se afastar, ou nós sempre 200 00:10:25,350 --> 00:10:30,430 ter um ponteiro em algum ponto que é direito sobre o primeiro elemento da lista. 201 00:10:30,430 --> 00:10:33,290 Portanto, é melhor criar um um segundo que usamos para mover. 202 00:10:33,290 --> 00:10:35,877 >> Em seguida, basta comparar se o campo de valor em que nó 203 00:10:35,877 --> 00:10:38,960 é o que estamos procurando, e se é Não, nós apenas passar para o próximo nó. 204 00:10:38,960 --> 00:10:41,040 E nós continuar fazendo isso mais, e mais, e mais, 205 00:10:41,040 --> 00:10:44,811 até que nós quer encontrar o elemento, ou nós batemos 206 00:10:44,811 --> 00:10:47,310 null-- chegamos à final da lista e ele não está lá. 207 00:10:47,310 --> 00:10:50,540 Este deve esperamos tocar um sino para você como apenas busca linear, 208 00:10:50,540 --> 00:10:54,430 nós estamos apenas replicá-lo em uma estrutura de lista vinculada isoladamente 209 00:10:54,430 --> 00:10:56,280 em vez de usar uma matriz para fazê-lo. 210 00:10:56,280 --> 00:10:58,210 >> Então aqui está um exemplo de uma lista vinculada isoladamente. 211 00:10:58,210 --> 00:11:00,043 Este consiste de cinco nós, e temos 212 00:11:00,043 --> 00:11:04,330 um ponteiro para a cabeça do lista, que é chamado de lista. 213 00:11:04,330 --> 00:11:07,385 A primeira coisa que quero fazer é novamente, criar esse ponteiro travessia. 214 00:11:07,385 --> 00:11:09,760 Portanto, temos agora dois ponteiros que apontam para a mesma coisa. 215 00:11:09,760 --> 00:11:15,025 >> Agora, observe aqui também, eu não fiz tem que malloc qualquer espaço para Trav. 216 00:11:15,025 --> 00:11:18,970 Eu não disse trav igual malloc algo, esse nó já existe, 217 00:11:18,970 --> 00:11:21,160 esse espaço na memória já existe. 218 00:11:21,160 --> 00:11:24,290 Então, tudo que eu estou fazendo realmente é criando um outro ponteiro para ele. 219 00:11:24,290 --> 00:11:28,210 Eu não estou mallocing um adicional espaço, apenas tem agora dois ponteiros 220 00:11:28,210 --> 00:11:31,370 apontando para a mesma coisa. 221 00:11:31,370 --> 00:11:33,710 >> Então é 2 o que estou procurando? 222 00:11:33,710 --> 00:11:37,220 Bem, não, então ao invés eu sou vai passar para a próxima. 223 00:11:37,220 --> 00:11:41,740 Então, basicamente, eu diria, trav igual trav seguinte. 224 00:11:41,740 --> 00:11:43,630 3 é o que eu estou procurando, não. 225 00:11:43,630 --> 00:11:45,780 Então eu continuar a ir através, até que finalmente 226 00:11:45,780 --> 00:11:48,690 chegar a 6, que é o que estou procurando para com base na chamada de função 227 00:11:48,690 --> 00:11:51,600 Eu tenho no topo lá, e assim que eu sou feito. 228 00:11:51,600 --> 00:11:54,150 >> Agora, e se o elemento que eu sou procurando não está na lista, 229 00:11:54,150 --> 00:11:55,510 é que ainda vai funcionar? 230 00:11:55,510 --> 00:11:57,120 Bem, observe que a lista aqui é sutilmente diferente, 231 00:11:57,120 --> 00:11:59,410 e esta é uma outra coisa que é importante com listas ligadas, 232 00:11:59,410 --> 00:12:01,780 você não tem que preservar los em qualquer ordem particular. 233 00:12:01,780 --> 00:12:05,390 Você pode, se quiser, mas você já deve ter notado 234 00:12:05,390 --> 00:12:09,310 que não estamos mantendo o controle de o elemento de número estamos. 235 00:12:09,310 --> 00:12:13,150 >> E isso é um tipo de comércio que tem com lista ligada versos arrays, 236 00:12:13,150 --> 00:12:15,300 é que não temos acesso aleatório mais. 237 00:12:15,300 --> 00:12:18,150 Não podemos apenas dizer, eu quero para ir para o elemento 0, 238 00:12:18,150 --> 00:12:21,410 ou o elemento sexto da minha matriz, que eu posso fazer em uma matriz. 239 00:12:21,410 --> 00:12:25,080 Eu não posso dizer que eu quero ir para o Elemento 0, ou o elemento 6, 240 00:12:25,080 --> 00:12:30,360 ou o elemento 25 da minha lista ligada, não há nenhum índice associado com eles. 241 00:12:30,360 --> 00:12:33,660 E por isso realmente não importa se preservar nossa lista em ordem. 242 00:12:33,660 --> 00:12:36,080 Se você quiser você certamente podem, mas há 243 00:12:36,080 --> 00:12:38,567 nenhuma razão para que eles precisam ser preservados em qualquer ordem. 244 00:12:38,567 --> 00:12:40,400 Então, novamente, vamos tentar 6 encontrar nesta lista. 245 00:12:40,400 --> 00:12:43,200 Bem, vamos começar no começando, não encontramos 6, 246 00:12:43,200 --> 00:12:47,690 e então nós não continuar a encontrar 6, até que, eventualmente, chegar a aqui. 247 00:12:47,690 --> 00:12:52,790 Tão certo pontos agora trav para o nó contendo 8, e seis não está lá. 248 00:12:52,790 --> 00:12:55,250 >> Assim, o próximo passo seria para ir para o próximo ponteiro, 249 00:12:55,250 --> 00:12:57,440 assim dizem trav igual trav seguinte. 250 00:12:57,440 --> 00:13:00,750 Bem, Trav seguinte, indicada pela a caixa vermelha lá, é nulo. 251 00:13:00,750 --> 00:13:03,020 Portanto, não há nenhum outro lugar para ir, e por isso neste momento 252 00:13:03,020 --> 00:13:06,120 podemos concluir que chegamos o fim da lista ligada, 253 00:13:06,120 --> 00:13:07,190 e 6 não está lá. 254 00:13:07,190 --> 00:13:10,980 E isso seria devolvido false neste caso. 255 00:13:10,980 --> 00:13:14,540 >> OK, como é que vamos inserir uma nova nó na lista vinculada? 256 00:13:14,540 --> 00:13:17,310 Então, nós temos sido capazes de criar uma lista vinculada do nada, 257 00:13:17,310 --> 00:13:19,370 mas nós provavelmente quer construir uma cadeia e não 258 00:13:19,370 --> 00:13:22,620 criar um grupo de listas distintas. 259 00:13:22,620 --> 00:13:25,700 Queremos ter uma lista que tem um monte de nós na mesma, 260 00:13:25,700 --> 00:13:28,040 não um monte de listas com um único nó. 261 00:13:28,040 --> 00:13:31,260 Portanto, não podemos apenas continuar usando o Criar função que definimos anteriormente, agora nós 262 00:13:31,260 --> 00:13:33,860 deseja inserir um lista que já existe. 263 00:13:33,860 --> 00:13:36,499 >> Então, neste caso, nós vamos para passar em dois argumentos, 264 00:13:36,499 --> 00:13:39,290 o ponteiro para a cabeça do que lista que deseja adicionar à ligados. 265 00:13:39,290 --> 00:13:40,910 Novamente, é por isso que é tão importante que nós sempre 266 00:13:40,910 --> 00:13:43,400 acompanhar, porque é a única maneira de realmente 267 00:13:43,400 --> 00:13:46,690 tem que se referir a toda a lista é apenas por um ponteiro para o primeiro elemento. 268 00:13:46,690 --> 00:13:49,360 Por isso, queremos passar em um ponteiro para esse primeiro elemento, 269 00:13:49,360 --> 00:13:52,226 e qualquer valor que deseja adicionar à lista. 270 00:13:52,226 --> 00:13:54,600 E, eventualmente, esta função vai retornar um ponteiro 271 00:13:54,600 --> 00:13:57,980 para o novo chefe de uma lista ligada. 272 00:13:57,980 --> 00:13:59,700 >> Quais são as etapas envolvidas aqui? 273 00:13:59,700 --> 00:14:02,249 Bem, assim como com a criar, precisamos alocar dinamicamente 274 00:14:02,249 --> 00:14:05,540 espaço para um novo nó, e certifique- garantir que não fique sem memória, outra vez, 275 00:14:05,540 --> 00:14:07,150 porque nós estamos usando malloc. 276 00:14:07,150 --> 00:14:09,080 Então, nós queremos preencher e inserir o nó, 277 00:14:09,080 --> 00:14:12,730 de modo que o número, o que quer val é, para o nó. 278 00:14:12,730 --> 00:14:17,310 Queremos inserir o nó em o início da lista encadeada. 279 00:14:17,310 --> 00:14:19,619 >> Há uma razão para que eu quero fazer isso, e 280 00:14:19,619 --> 00:14:21,910 pode valer a pena tomar um segundo para pausar o vídeo aqui, 281 00:14:21,910 --> 00:14:25,860 e pensar por que eu iria querer inserir no início de um ligado 282 00:14:25,860 --> 00:14:26,589 Lista. 283 00:14:26,589 --> 00:14:28,630 Mais uma vez, eu mencionei anteriormente que ele realmente não 284 00:14:28,630 --> 00:14:33,020 importa se nós preservá-lo em qualquer ordem, portanto, talvez seja uma pista. 285 00:14:33,020 --> 00:14:36,040 E você viu o que aconteceria se nós queria a-- ou de apenas um segundo 286 00:14:36,040 --> 00:14:37,360 atrás, quando estávamos indo através de pesquisa você 287 00:14:37,360 --> 00:14:39,235 podia ver o que pode acontecer se nós estávamos tentando 288 00:14:39,235 --> 00:14:41,330 para inserir no fim da lista. 289 00:14:41,330 --> 00:14:44,750 Porque não temos um ponteiro para o fim da lista. 290 00:14:44,750 --> 00:14:47,490 >> Portanto, a razão que eu gostaria para inserir no início, 291 00:14:47,490 --> 00:14:49,380 é porque eu posso fazê-lo imediatamente. 292 00:14:49,380 --> 00:14:52,730 Eu tenho um ponteiro no início, e vamos ver isso em um visual em um segundo. 293 00:14:52,730 --> 00:14:55,605 Mas se eu quiser inserir no final, Eu tenho que começar do início, 294 00:14:55,605 --> 00:14:58,760 percorrer todo o caminho para a final, e depois pregá-la por diante. 295 00:14:58,760 --> 00:15:01,420 Então, isso significaria que inserir no fim da lista 296 00:15:01,420 --> 00:15:04,140 se tornaria um o de n operação, voltando 297 00:15:04,140 --> 00:15:06,720 para a nossa discussão de complexidade computacional. 298 00:15:06,720 --> 00:15:10,140 Ele tinha se tornado um o de n operação, onde como a lista ficou maior e maior, 299 00:15:10,140 --> 00:15:13,310 e maior, ele vai se tornar mais e mais difícil para alinhavar algo 300 00:15:13,310 --> 00:15:14,661 em no final. 301 00:15:14,661 --> 00:15:17,410 Mas é sempre muito fácil alinhavar algo em no início, 302 00:15:17,410 --> 00:15:19,060 você está sempre no início. 303 00:15:19,060 --> 00:15:21,620 >> E nós vamos ver um visual desta novamente. 304 00:15:21,620 --> 00:15:24,100 E, em seguida, uma vez que estamos a fazer, uma vez temos inserido o novo nó, 305 00:15:24,100 --> 00:15:26,880 queremos voltar nosso ponteiro para o novo chefe de uma lista ligada, o que 306 00:15:26,880 --> 00:15:29,213 já que estamos inserindo no começando, vai ser realmente 307 00:15:29,213 --> 00:15:31,060 um ponteiro para o nó que acabamos de criar. 308 00:15:31,060 --> 00:15:33,280 Vamos visualizar esta, porque eu acho que ele vai ajudar. 309 00:15:33,280 --> 00:15:36,661 >> Então aqui está a nossa lista, que consiste em quatro elementos, contendo um nó 15, 310 00:15:36,661 --> 00:15:38,410 o que aponta para um nó contendo 9, que 311 00:15:38,410 --> 00:15:41,370 aponta para um nó que contém 13, o que aponta para um nó que contenha 312 00:15:41,370 --> 00:15:44,840 10, que tem o nulo ponteiro como seu próximo ponteiro 313 00:15:44,840 --> 00:15:47,010 de modo que é o fim da lista. 314 00:15:47,010 --> 00:15:50,200 Por isso, queremos inserir um novo nó com o valor 12 315 00:15:50,200 --> 00:15:52,720 no início do presente lista, o que vamos fazer? 316 00:15:52,720 --> 00:15:58,770 Bem, primeiro nós malloc espaço para a nó, e, em seguida, vamos colocar 12 em lá. 317 00:15:58,770 --> 00:16:02,211 >> Então, agora chegamos a um ponto de decisão, certo? 318 00:16:02,211 --> 00:16:03,960 Nós temos um par de ponteiros que pudéssemos 319 00:16:03,960 --> 00:16:06,770 mover, qual devemos avançar em primeiro lugar? 320 00:16:06,770 --> 00:16:09,250 Devemos fazer 12 pontos para o novo chefe da lista-- 321 00:16:09,250 --> 00:16:13,020 ou me desculpar, devemos fazer 12 apontar para o antigo chefe da lista? 322 00:16:13,020 --> 00:16:15,319 Ou deveríamos dizer que o lista agora começa a 12. 323 00:16:15,319 --> 00:16:17,110 Há uma distinção lá, e nós olharemos 324 00:16:17,110 --> 00:16:19,870 o que acontece com ambos em um segundo. 325 00:16:19,870 --> 00:16:23,350 >> Mas isto conduz a um grande tema para a barra lateral, 326 00:16:23,350 --> 00:16:26,280 que é um dos que o as coisas mais complicadas com listas ligadas 327 00:16:26,280 --> 00:16:30,980 é organizar os ponteiros na ordem correta. 328 00:16:30,980 --> 00:16:34,520 Se você mover as coisas fora de ordem, você pode acabar acidentalmente 329 00:16:34,520 --> 00:16:36,050 orphaning o resto da lista. 330 00:16:36,050 --> 00:16:37,300 E aqui está um exemplo disso. 331 00:16:37,300 --> 00:16:40,540 Então, vamos ir com a idéia de-- bem, que acabamos de criar 12. 332 00:16:40,540 --> 00:16:43,180 Sabemos 12 vai ser o novo chefe da lista, 333 00:16:43,180 --> 00:16:47,660 e assim por que não vamos apenas mover o ponteiro lista para apontar lá. 334 00:16:47,660 --> 00:16:49,070 >> OK, então isso é bom. 335 00:16:49,070 --> 00:16:51,560 Então, agora onde é que 12 próximo ponto? 336 00:16:51,560 --> 00:16:54,580 Quero dizer, visualmente podemos ver que irá apontar para 15, 337 00:16:54,580 --> 00:16:57,250 como seres humanos é muito óbvio para nós. 338 00:16:57,250 --> 00:17:00,300 Como o computador sabe? 339 00:17:00,300 --> 00:17:02,720 Não temos nada apontando para mais 15, certo? 340 00:17:02,720 --> 00:17:05,869 >> Perdemos qualquer capacidade de referir-se a 15. 341 00:17:05,869 --> 00:17:11,460 Não podemos dizer nova seta ao lado equals alguma coisa, não há nada lá. 342 00:17:11,460 --> 00:17:13,510 Na verdade, temos órfãos o resto da lista 343 00:17:13,510 --> 00:17:16,465 ao fazê-lo, nós temos acidentalmente quebrou a cadeia. 344 00:17:16,465 --> 00:17:18,089 E nós certamente não queremos fazer isso. 345 00:17:18,089 --> 00:17:20,000 >> Então, vamos voltar e tentar novamente. 346 00:17:20,000 --> 00:17:24,060 Talvez a coisa certa a fazer é situado ao lado do ponteiro 12 347 00:17:24,060 --> 00:17:28,290 para o antigo chefe da primeira lista, então podemos mover a lista mais. 348 00:17:28,290 --> 00:17:30,420 E, de fato, que é o ordem correta que nós 349 00:17:30,420 --> 00:17:32,836 precisamos seguir quando estamos Trabalhando com uma lista vinculada isoladamente. 350 00:17:32,836 --> 00:17:36,460 Nós sempre queremos conectar o novo elemento na lista, 351 00:17:36,460 --> 00:17:41,010 antes de tomar esse tipo de importante passo de alteração 352 00:17:41,010 --> 00:17:43,360 onde a cabeça da lista ligada é. 353 00:17:43,360 --> 00:17:46,740 Novamente, isso é uma coisa tão fundamental, nós não queremos perder o controle dela. 354 00:17:46,740 --> 00:17:49,310 >> Então, nós queremos ter certeza de que tudo é encadeados, 355 00:17:49,310 --> 00:17:52,040 antes de passar esse ponteiro. 356 00:17:52,040 --> 00:17:55,300 E assim esta seria a ordem correta, o qual é para ligar para a lista 12, 357 00:17:55,300 --> 00:17:57,630 em seguida, dizer que a lista começa a 12. 358 00:17:57,630 --> 00:18:00,860 Se disse que a lista começa em 12 e em seguida, tentou se conectar 12 da lista, 359 00:18:00,860 --> 00:18:02,193 já vimos o que acontece. 360 00:18:02,193 --> 00:18:04,920 Perdemos a lista por engano. 361 00:18:04,920 --> 00:18:06,740 >> OK, então mais uma coisa para falar. 362 00:18:06,740 --> 00:18:09,750 E se a gente quiser se livrar de toda uma lista ligada de uma vez? 363 00:18:09,750 --> 00:18:11,750 Mais uma vez, estamos mallocing todo este espaço, e por isso, 364 00:18:11,750 --> 00:18:13,351 preciso libertá-la quando estamos a fazer. 365 00:18:13,351 --> 00:18:15,350 Então, agora queremos excluir toda a lista ligada. 366 00:18:15,350 --> 00:18:16,850 Bem, o que nós queremos fazer? 367 00:18:16,850 --> 00:18:20,460 >> Se nós alcançamos o ponteiro nulo, nós quer parar, caso contrário, basta apagar 368 00:18:20,460 --> 00:18:23,420 o resto da lista e, em seguida, me libertar. 369 00:18:23,420 --> 00:18:28,890 Excluir o resto da lista, e, em seguida, liberar o nó atual. 370 00:18:28,890 --> 00:18:32,850 O que significa que o som como, qual técnica tem falamos 371 00:18:32,850 --> 00:18:35,440 sobre anteriormente é que o som como? 372 00:18:35,440 --> 00:18:39,560 Excluir todos os outros, em seguida, voltar e me excluir. 373 00:18:39,560 --> 00:18:42,380 >> Isso é recursão, fizemos o problema um pouco menor, 374 00:18:42,380 --> 00:18:46,910 nós estamos dizendo excluir todos mais, então você pode me excluir. 375 00:18:46,910 --> 00:18:50,940 E mais abaixo na estrada, esse nó vai dizer, excluir todos os outros. 376 00:18:50,940 --> 00:18:53,940 Mas eventualmente nós vamos chegar ao ponto em que a lista é nulo, 377 00:18:53,940 --> 00:18:55,310 e esse é o nosso caso base. 378 00:18:55,310 --> 00:18:57,010 >> Então, vamos dar uma olhada nisso, e como isso pode funcionar. 379 00:18:57,010 --> 00:18:59,759 Então aqui está a nossa lista, é o mesmo listar nós estávamos falando sobre, 380 00:18:59,759 --> 00:19:00,980 e há os passos. 381 00:19:00,980 --> 00:19:04,200 Há um monte de texto aqui, mas espero que a visualização vai ajudar. 382 00:19:04,200 --> 00:19:08,557 >> Então, nós have-- e eu também puxou a nossa pilha de quadros ilustração 383 00:19:08,557 --> 00:19:10,890 do nosso vídeo sobre pilhas de chamadas, e espero que tudo isso 384 00:19:10,890 --> 00:19:13,260 juntos irá mostrar-lhe o que está acontecendo. 385 00:19:13,260 --> 00:19:14,510 Então aqui está o nosso código pseudocódigo. 386 00:19:14,510 --> 00:19:17,830 Se chegarmos a um valor nulo ponteiro, parar, caso contrário, 387 00:19:17,830 --> 00:19:21,320 excluir o resto da lista, em seguida, liberar o nó atual. 388 00:19:21,320 --> 00:19:25,700 Então, agora, lista-- o ponteiro do que nós somos 389 00:19:25,700 --> 00:19:28,410 passando para destruir a 12 pontos. 390 00:19:28,410 --> 00:19:33,340 12 não é um ponteiro nulo, por isso estamos indo para eliminar o resto da lista. 391 00:19:33,340 --> 00:19:35,450 >> O que é a exclusão do resto de nós envolvidos? 392 00:19:35,450 --> 00:19:37,950 Bem, isso significa fazer uma chamar para destruir, dizendo 393 00:19:37,950 --> 00:19:42,060 15 é que o início do resto da lista queremos destruir. 394 00:19:42,060 --> 00:19:47,480 E assim a chamada para destruir 12 é uma espécie de em espera. 395 00:19:47,480 --> 00:19:52,690 Ele está congelado lá, esperando o chamar para destruir 15, para terminar o seu trabalho. 396 00:19:52,690 --> 00:19:56,280 >> Bem, 15 não é um ponteiro nulo, e por isso vai dizer, tudo bem, 397 00:19:56,280 --> 00:19:58,450 bem, exclua o resto da lista. 398 00:19:58,450 --> 00:20:00,760 O resto da lista começa às 9, e por isso vamos apenas 399 00:20:00,760 --> 00:20:04,514 espere até que você exclua tudo o que material, em seguida, voltar e apagar mim. 400 00:20:04,514 --> 00:20:06,680 Bem 9 vai dizer, bem, Eu não sou um ponteiro nulo, 401 00:20:06,680 --> 00:20:09,020 assim eliminar o resto da lista a partir daqui. 402 00:20:09,020 --> 00:20:11,805 E assim tentar destruir 13. 403 00:20:11,805 --> 00:20:15,550 13 diz: Eu não sou ponteiro nulo, mesma coisa, ele passa o buck. 404 00:20:15,550 --> 00:20:17,930 10 não é ponteiro nulo, 10 contém um ponteiro nulo, 405 00:20:17,930 --> 00:20:20,200 10, mas não é ela própria uma Ponteiro Nulo agora, 406 00:20:20,200 --> 00:20:22,470 e assim que passa a bola também. 407 00:20:22,470 --> 00:20:25,560 >> E agora listar pontos lá, realmente chama a atenção para some-- 408 00:20:25,560 --> 00:20:28,710 se eu tivesse mais espaço na imagem, ele chama a atenção para algum espaço aleatório 409 00:20:28,710 --> 00:20:29,960 que nós não sabemos o que é. 410 00:20:29,960 --> 00:20:34,680 É o ponteiro nulo, porém, a lista é, literalmente, agora é definido valores nulos. 411 00:20:34,680 --> 00:20:36,820 Ele está apontando para a direita dentro daquela caixa vermelha. 412 00:20:36,820 --> 00:20:39,960 Chegamos a um ponteiro nulo, de modo podemos parar, e estamos a fazer. 413 00:20:39,960 --> 00:20:46,230 >> E assim que quadro roxo é agora-- no topo da stack-- esse é o quadro ativo, 414 00:20:46,230 --> 00:20:47,017 mas ele é feito. 415 00:20:47,017 --> 00:20:48,600 Se chegamos a um ponteiro nulo, pare. 416 00:20:48,600 --> 00:20:51,290 Nós não fazemos qualquer coisa, nós não pode liberar um ponteiro nulo, 417 00:20:51,290 --> 00:20:55,070 nós não malloc qualquer espaço, e por isso estamos a fazer. 418 00:20:55,070 --> 00:20:57,590 Então, esse quadro função é destruído, e nós 419 00:20:57,590 --> 00:21:00,930 resume-- nós pegar onde paramos fora com o mais elevado seguinte, que 420 00:21:00,930 --> 00:21:02,807 é este quadro azul escuro aqui. 421 00:21:02,807 --> 00:21:04,390 Então, nós pegar exatamente onde paramos. 422 00:21:04,390 --> 00:21:06,598 Nós excluído o resto do lista já, então agora estamos 423 00:21:06,598 --> 00:21:08,000 vai liberar os nós atuais. 424 00:21:08,000 --> 00:21:12,920 Então agora podemos libertar este nó, e agora chegamos ao fim da função. 425 00:21:12,920 --> 00:21:16,810 E assim que o quadro função é destruído, e nós pegar na uma luz azul. 426 00:21:16,810 --> 00:21:20,650 >> Por isso, says-- Eu já done-- a exclusão do resto da lista, de modo 427 00:21:20,650 --> 00:21:23,140 libertar o nó atual. 428 00:21:23,140 --> 00:21:26,520 E agora a moldura amarela é de volta ao topo da pilha. 429 00:21:26,520 --> 00:21:29,655 E assim como você pode ver, estamos agora destruindo a lista da direita para a esquerda. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> O que teria acontecido, porém, se tivéssemos feito as coisas de forma errada? 432 00:21:37,280 --> 00:21:39,410 Assim como quando tentámos adicionar um elemento. 433 00:21:39,410 --> 00:21:41,909 Se errei a cadeia, se nós não ligar os ponteiros 434 00:21:41,909 --> 00:21:44,690 na ordem correta, se nós apenas liberado o primeiro elemento, 435 00:21:44,690 --> 00:21:47,420 se nós só libertou o cabeça da lista, agora nós 436 00:21:47,420 --> 00:21:49,642 não têm nenhuma maneira para se referir a o resto da lista. 437 00:21:49,642 --> 00:21:51,350 E por isso, teria órfãs tudo, 438 00:21:51,350 --> 00:21:53,880 teríamos o que é chamado de fuga de memória. 439 00:21:53,880 --> 00:21:56,800 Se você se lembrar do nosso vídeo na alocação dinâmica de memória, 440 00:21:56,800 --> 00:21:58,650 isso não é coisa muito boa. 441 00:21:58,650 --> 00:22:00,810 >> Então, como eu disse, há várias operações 442 00:22:00,810 --> 00:22:04,010 que precisamos usar para trabalhar com lista ligada de forma eficaz. 443 00:22:04,010 --> 00:22:08,430 E você pode ter notado que eu omitido um, excluindo um único elemento a partir de um ligado 444 00:22:08,430 --> 00:22:09,064 Lista. 445 00:22:09,064 --> 00:22:10,980 A razão pela qual eu fiz isso é que é realmente tipo de 446 00:22:10,980 --> 00:22:14,360 complicado para pensar sobre como excluir um único elemento de uma isoladamente 447 00:22:14,360 --> 00:22:15,600 lista ligada. 448 00:22:15,600 --> 00:22:19,950 Precisamos ser capazes de passar por cima algo na lista, que 449 00:22:19,950 --> 00:22:22,975 Significa chegarmos a um que ponto-- quer apagar este node-- 450 00:22:22,975 --> 00:22:25,350 mas, a fim de torná-lo assim que nós não perca nenhuma informação, 451 00:22:25,350 --> 00:22:30,530 precisamos conectar este nó aqui, aqui. 452 00:22:30,530 --> 00:22:33,390 >> Então eu provavelmente fiz isso errado a partir de uma perspectiva visual. 453 00:22:33,390 --> 00:22:36,830 Então, estamos no início da nossa lista, estamos a proceder por meio de, 454 00:22:36,830 --> 00:22:40,510 que deseja excluir este nó. 455 00:22:40,510 --> 00:22:43,440 Se nós apenas excluí-lo, nós quebramos a corrente. 456 00:22:43,440 --> 00:22:45,950 Este nó aqui refere-se a tudo o resto, 457 00:22:45,950 --> 00:22:48,260 ele contém a cadeia de agora em diante. 458 00:22:48,260 --> 00:22:51,190 >> Então, o que precisamos fazer, na verdade, depois de chegarmos a este ponto, 459 00:22:51,190 --> 00:22:56,670 é que precisamos dar um passo atrás um, e conectar esse nó durante a esse nó, 460 00:22:56,670 --> 00:22:58,590 para que possamos, em seguida, apagar o um no meio. 461 00:22:58,590 --> 00:23:02,120 Mas as listas vinculada isoladamente não fazer nos fornecer uma maneira de ir para trás. 462 00:23:02,120 --> 00:23:05,160 Então, precisamos quer manter dois ponteiros, e movê-los 463 00:23:05,160 --> 00:23:09,527 espécie de off passo, um atrás do outros como nós vamos, ou chegar a um ponto 464 00:23:09,527 --> 00:23:11,110 e, em seguida, enviar um outro ponteiro completamente. 465 00:23:11,110 --> 00:23:13,150 E como você pode ver, pode ficar um pouco confuso. 466 00:23:13,150 --> 00:23:15,360 Felizmente, temos outra maneira de resolver isso, 467 00:23:15,360 --> 00:23:17,810 quando falamos de listas duplamente ligadas. 468 00:23:17,810 --> 00:23:20,720 >> Eu sou Doug Lloyd, este é CS50. 469 00:23:20,720 --> 00:23:22,298