[Música tocando] 

DOUG LLOYD: OK, então a Neste ponto do curso, nós cobrimos um monte de os conceitos básicos de C. Sabemos muito sobre variáveis, arrays, ponteiros, todas essas coisas boas. Aqueles são todos os tipos de construção para ver como os fundamentos, mas podemos fazer mais, certo? Podemos combinar as coisas em conjunto de maneiras interessantes. 

E assim vamos fazer isso, vamos começar a ramificar-se do que C nos dá, e começar a criar nossos próprios dados Usando estas estruturas edifício blocos juntos para fazer algo realmente valioso, útil. Uma maneira de fazer isso é para falar sobre coleções. Então, até agora nós tivemos um tipo de dados estrutura para representar as coleções gostaria de valores, valores semelhantes. Isso seria uma matriz. Temos coleções de inteiros, ou coleções de personagens e assim por diante. 

Estruturas também são um tipo de dados estrutura para a coleta de informações, mas não é para coletar como valores. Geralmente mistura diferentes tipos de dados juntos dentro de uma única caixa. Mas não é em si usado para encadear ou ligar juntos semelhante itens, como uma matriz. Arrays são grandes para elemento de olhar para cima, mas recordação que é muito difícil para inserir uma matriz, a menos que nós estamos inserindo no o final dessa matriz. 

E o melhor exemplo que eu tenho para isso é a ordenação por inserção. Se bem se lembram o nosso vídeo na ordenação por inserção, havia um monte de despesa envolvida em ter para pegar elementos, e transferi-los para fora do caminho para caber algo no meio de sua matriz. Arrays também sofrem de outro problema, que é a inflexibilidade. Quando declaramos uma matriz, obtemos um tiro nele. Nós começamos a dizer, eu quero este muitos elementos. Pode ser de 100, ele pode ser 1000, pode ser X, onde X é um número que o utilizador deu-nos em um prompt de comando ou no line. 

Mas nós só temos uma chance para ele, nós não consegue, então, dizer oh, na verdade eu precisava de 101, ou eu precisava x mais 20. Tarde demais, que já declarou o array, e se quisermos obter 101 ou x acrescido de 20, temos a declarar uma matriz totalmente diferente, copiar todos os elementos da matriz sobre, e então nós temos o suficiente. E se estamos errados novamente, o que se nós realmente precisamos 102, ou x mais 40, nós temos que fazer isso de novo. Então, eles estão muito inflexível para redimensionar os nossos dados, mas se combinam alguns dos princípios básicos que nós já Aprendi sobre ponteiros e estruturas, em especial através de memória dinâmica alocação com malloc, nós pode colocar esses pedaços juntos para criar um novo dado um structure-- isoladamente lista poderíamos dizer-- ligado que nos permite crescer e encolher uma coleção de valores e não teremos qualquer espaço desperdiçado. 

Então, novamente, nós chamamos essa idéia, essa noção, uma lista ligada. Em particular, neste vídeo que estamos falando lista vinculada isoladamente, e, em seguida, um outro vídeo vamos falar listas sobre duplamente ligadas, que é apenas uma variação sobre um tema aqui. Mas uma lista vinculada isoladamente é composto por nós, nós apenas ser um term-- abstrato é apenas algo que eu estou chamando que é uma espécie de estrutura, basicamente, eu sou? Basta ir a chamá-lo de um node-- e este nó tem dois membros, ou dois campos. Tem de dados, geralmente um inteiro, um personagem float, ou poderia ser algum outro tipo de dados que você tenha definido com um tipo def. E que contém um apontador para outro nó do mesmo tipo. 

Portanto, temos duas coisas dentro de esse nó, de dados e um ponteiro para outro nó. E se você começar a visualizar isso, você pode pensar sobre isso como uma cadeia de nós que estão ligados entre si. Temos o primeiro nó, ele contém os dados, e um ponteiro para o segundo nó, a qual contém de dados, e um ponteiro para o terceiro nó. E é por isso que chamamos de lista ligada, eles estão ligados entre si. 

O que faz este especial estrutura de nó parece? Bem, se você se lembra do nosso vídeo sobre definir tipos personalizados, com o tipo de definição, podemos definir uma structure-- e digite definir uma estrutura como esta. tyepdef struct sllist, e então eu sou usando a palavra valor arbitrariamente aqui para indicar qualquer tipo de dados realmente. Você poderia passar um inteiro ou float, você pode ter o que quiser. Não está restrito a apenas inteiros, ou qualquer coisa assim. Assim, o valor é apenas uma arbitrária Tipo de dados e, em seguida, um ponteiro para outro nó do mesmo tipo. 

Agora, há um pouco de captura aqui com uma estrutura que define quando é uma estrutura auto referencial. Eu tenho que ter um temporário nomear para minha estrutura. No final do dia, claramente querem chamá-lo sll nó, que é em última análise, o novo nomear parte da minha definição de tipo, mas eu não posso usar nó sll no meio deste. A razão de ser, eu não tenho criou um tipo chamado nó sll até que eu bati esse ponto final aqui. Até aquele momento, eu tenho que ter uma outra maneira de se referir a este tipo de dados. 

E esta é uma auto- tipo de dados referencial. ; S um tipo de dados que contém uma estrutura de dados, e um ponteiro para uma outra estrutura do mesmo tipo. Então eu preciso ser capaz de se referir a este tipo de dados, pelo menos temporariamente, assim dando-lhe um temporária nome de struct sllist permite-me, em seguida, dizer que eu quero um ponteiro para outro sllist struct, uma estrela struct sllist, e, em seguida, depois que eu tiver concluído a definição, Agora eu posso chamar este tipo de um nó de SLL. 

É por isso que você vê que há um nome temporário aqui, mas um nome permanente aqui. Às vezes você pode ver definições de estrutura, por exemplo, que não são auto referencial, que não tem um nome especificador aqui. Ele apenas diria typedef struct, abrir chaveta e, em seguida, defini-lo. Mas se você é struct é auto- referencial, como este é, você precisa especificar um nome do tipo temporário. Mas, afinal, agora que fizemos isso, podemos apenas referir-se a esses nós, estas unidades, como nodos SLL para fins do resto deste vídeo. 

Tudo bem, então sabemos como criar um nó lista ligada. Nós sabemos como definir um nó de lista ligada. Agora, se nós estamos indo para começar usando-os para coletar informações, há um par de operações que precisam entender e trabalhar com ele. Precisamos saber como criar uma lista ligada fora do ar. Se não há nenhuma lista já, queremos começar um. Então, precisamos ser capazes para criar uma lista ligada, precisamos provavelmente procurar através da lista de links para encontrar um elemento que estamos procurando. Precisamos ser capazes de inserir coisas novas para a lista, queremos que a nossa lista para ser capaz de crescer. E da mesma forma, queremos ser capazes para apagar as coisas da nossa lista, queremos que a nossa lista para ser capaz de encolher. E no final da nossa programas, especialmente se você se lembra que nós somos alocar dinamicamente a memória para construir estas listas normalmente, queremos libertar toda a memória que quando terminarmos de trabalhar com ele. E por isso temos de ser capazes de apagar um Toda lista ligada em uma rusga falhar. Então, vamos passar por Algumas destas operações e como podemos visualizá-los, falando em código pseudocódigo especificamente. Por isso, queremos criar uma lista ligada, então talvez nós quer definir uma função com este protótipo. sll estrela nó, criar, e eu estou passando em um argumento, alguns dados arbitrários digite novamente, de algum tipo de dados arbitrário. Mas eu estou returning-- esta função deve voltar para mim um ponteiro, a um isoladamente nó lista ligada. Mais uma vez, estamos tentando criar uma lista ligada fora do ar, então eu preciso de um ponteiro para essa lista quando eu terminar. 

Então, quais são as etapas envolvidas aqui? Bem, a primeira coisa que eu sou vai fazer é dinamicamente alocar espaço para um novo nó. Mais uma vez, estamos criando-o para fora da fina ar, por isso precisamos de espaço malloc para ele. E, claro, imediatamente depois que malloc, sempre certifique-se de que o nosso pointer-- nós não voltar nulo. Porque se nós tentamos e deferência um ponteiro nulo, vamos sofrer um segfault e nós não queremos isso. 

Então, nós queremos preencher o campo, queremos inicializar o campo de valor e inicializar o próximo campo. E então nós queremos a--, eventualmente, como o função protótipo indicates-- queremos para retornar um ponteiro para um nó SLL. Então, o que fazer este olhar como visualmente? Bem, primeiro vamos dinamicamente alocar espaço para um novo nó SLL, por isso, que é malloc-- uma representação visual do nó de que acabamos de criar. E nós certifique-se não é null-- neste caso, a imagem não teria aparecido se era nulo, teríamos ficar sem memória, por isso, é bom para ir lá. Então, agora nós estamos para o passo C, inicializar o campo nodos valor. Bem, com base nessa função chamar que estou usando aqui, parece que eu quero passar em 6, então eu vou 6 no campo de valor. Agora, inicializar o próximo campo. Bem, o que eu vou fazer lá, não há nada ao lado, à direita, esta é a única coisa na lista. Então, qual é a próxima coisa na lista? 

Não deve apontar para qualquer coisa, certo. Não há mais nada lá, então o que é o conceito sabemos de que é nothing-- ponteiros para nada? Deve ser talvez nós queremos para colocar um ponteiro nulo lá, e eu vou representar o nulo ponteiro como apenas uma caixa vermelha, não podemos ir mais longe. Como veremos um pouco mais tarde, vamos ter eventualmente cadeias de setas que ligam destes nós, em conjunto mas quando você bate a caixa vermelha, que é nula, não podemos ir mais longe, esse é o fim da lista. 

E, finalmente, nós só queremos retornar um ponteiro para esse nó. Então, vamos chamá-lo de novo, e voltará novo de modo que pode ser utilizado em qualquer função criou. Então lá vamos nós, Nós criamos um isoladamente nó lista ligada fora do ar, e agora temos uma lista podemos trabalhar com. 

Agora, vamos dizer que já tem uma grande cadeia, e nós queremos encontrar algo nele. E queremos uma função que está acontecendo para retornar verdadeiro ou falso, dependendo sobre se existe um valor na lista. Um protótipo de função, ou declaração para essa função, pode parecer isto-- bool encontrar, e então queremos passar em dois argumentos. 

O primeiro, é um ponteiro para o primeiro elemento da lista ligada. Isso é realmente algo que você vai sempre quer acompanhar, e, na verdade, pode ser algo que você mesmo colocar em uma variável global. Depois de criar uma lista, você sempre, sempre quer manter o controle do próprio primeiro elemento da lista. Dessa forma, você pode se referir a todos os outros elementos por apenas seguindo a cadeia, sem ter que manter ponteiros intacta para cada elemento. Você só precisa manter o controle do primeiro um, se eles estão todos acorrentados. 

E, em seguida, a segunda coisa estamos passando novamente é arbitrariamente some-- seja qual for o tipo de dados que estamos procurando existe dentro de espero que um dos nós da lista. Então, quais são os passos? Bem, a primeira coisa que fazemos é criamos um ponteiro transversal apontando para a cabeça listas. Bem, por que fazemos isso, nós já ter um ponteiro na cabeça listas, por que não vamos apenas mover que um em torno de? Bem, como eu disse, que é realmente importante para nós manter sempre o controle do primeiro elemento da lista. E por isso é realmente melhor para criar uma duplicata de que, e usar isso para se movimentar, pelo que nunca acidentalmente se afastar, ou nós sempre ter um ponteiro em algum ponto que é direito sobre o primeiro elemento da lista. Portanto, é melhor criar um um segundo que usamos para mover. 

Em seguida, basta comparar se o campo de valor em que nó é o que estamos procurando, e se é Não, nós apenas passar para o próximo nó. E nós continuar fazendo isso mais, e mais, e mais, até que nós quer encontrar o elemento, ou nós batemos null-- chegamos à final da lista e ele não está lá. Este deve esperamos tocar um sino para você como apenas busca linear, nós estamos apenas replicá-lo em uma estrutura de lista vinculada isoladamente em vez de usar uma matriz para fazê-lo. 

Então aqui está um exemplo de uma lista vinculada isoladamente. Este consiste de cinco nós, e temos um ponteiro para a cabeça do lista, que é chamado de lista. A primeira coisa que quero fazer é novamente, criar esse ponteiro travessia. Portanto, temos agora dois ponteiros que apontam para a mesma coisa. 

Agora, observe aqui também, eu não fiz tem que malloc qualquer espaço para Trav. Eu não disse trav igual malloc algo, esse nó já existe, esse espaço na memória já existe. Então, tudo que eu estou fazendo realmente é criando um outro ponteiro para ele. Eu não estou mallocing um adicional espaço, apenas tem agora dois ponteiros apontando para a mesma coisa. 

Então é 2 o que estou procurando? Bem, não, então ao invés eu sou vai passar para a próxima. Então, basicamente, eu diria, trav igual trav seguinte. 3 é o que eu estou procurando, não. Então eu continuar a ir através, até que finalmente chegar a 6, que é o que estou procurando para com base na chamada de função Eu tenho no topo lá, e assim que eu sou feito. 

Agora, e se o elemento que eu sou procurando não está na lista, é que ainda vai funcionar? Bem, observe que a lista aqui é sutilmente diferente, e esta é uma outra coisa que é importante com listas ligadas, você não tem que preservar los em qualquer ordem particular. Você pode, se quiser, mas você já deve ter notado que não estamos mantendo o controle de o elemento de número estamos. 

E isso é um tipo de comércio que tem com lista ligada versos arrays, é que não temos acesso aleatório mais. Não podemos apenas dizer, eu quero para ir para o elemento 0, ou o elemento sexto da minha matriz, que eu posso fazer em uma matriz. Eu não posso dizer que eu quero ir para o Elemento 0, ou o elemento 6, ou o elemento 25 da minha lista ligada, não há nenhum índice associado com eles. E por isso realmente não importa se preservar nossa lista em ordem. Se você quiser você certamente podem, mas há nenhuma razão para que eles precisam ser preservados em qualquer ordem. Então, novamente, vamos tentar 6 encontrar nesta lista. Bem, vamos começar no começando, não encontramos 6, e então nós não continuar a encontrar 6, até que, eventualmente, chegar a aqui. Tão certo pontos agora trav para o nó contendo 8, e seis não está lá. 

Assim, o próximo passo seria para ir para o próximo ponteiro, assim dizem trav igual trav seguinte. Bem, Trav seguinte, indicada pela a caixa vermelha lá, é nulo. Portanto, não há nenhum outro lugar para ir, e por isso neste momento podemos concluir que chegamos o fim da lista ligada, e 6 não está lá. E isso seria devolvido false neste caso. 

OK, como é que vamos inserir uma nova nó na lista vinculada? Então, nós temos sido capazes de criar uma lista vinculada do nada, mas nós provavelmente quer construir uma cadeia e não criar um grupo de listas distintas. Queremos ter uma lista que tem um monte de nós na mesma, não um monte de listas com um único nó. Portanto, não podemos apenas continuar usando o Criar função que definimos anteriormente, agora nós deseja inserir um lista que já existe. 

Então, neste caso, nós vamos para passar em dois argumentos, o ponteiro para a cabeça do que lista que deseja adicionar à ligados. Novamente, é por isso que é tão importante que nós sempre acompanhar, porque é a única maneira de realmente tem que se referir a toda a lista é apenas por um ponteiro para o primeiro elemento. Por isso, queremos passar em um ponteiro para esse primeiro elemento, e qualquer valor que deseja adicionar à lista. E, eventualmente, esta função vai retornar um ponteiro para o novo chefe de uma lista ligada. 

Quais são as etapas envolvidas aqui? Bem, assim como com a criar, precisamos alocar dinamicamente espaço para um novo nó, e certifique- garantir que não fique sem memória, outra vez, porque nós estamos usando malloc. Então, nós queremos preencher e inserir o nó, de modo que o número, o que quer val é, para o nó. Queremos inserir o nó em o início da lista encadeada. 

Há uma razão para que eu quero fazer isso, e pode valer a pena tomar um segundo para pausar o vídeo aqui, e pensar por que eu iria querer inserir no início de um ligado Lista. Mais uma vez, eu mencionei anteriormente que ele realmente não importa se nós preservá-lo em qualquer ordem, portanto, talvez seja uma pista. E você viu o que aconteceria se nós queria a-- ou de apenas um segundo atrás, quando estávamos indo através de pesquisa você podia ver o que pode acontecer se nós estávamos tentando para inserir no fim da lista. Porque não temos um ponteiro para o fim da lista. 

Portanto, a razão que eu gostaria para inserir no início, é porque eu posso fazê-lo imediatamente. Eu tenho um ponteiro no início, e vamos ver isso em um visual em um segundo. Mas se eu quiser inserir no final, Eu tenho que começar do início, percorrer todo o caminho para a final, e depois pregá-la por diante. Então, isso significaria que inserir no fim da lista se tornaria um o de n operação, voltando para a nossa discussão de complexidade computacional. Ele tinha se tornado um o de n operação, onde como a lista ficou maior e maior, e maior, ele vai se tornar mais e mais difícil para alinhavar algo em no final. Mas é sempre muito fácil alinhavar algo em no início, você está sempre no início. 

E nós vamos ver um visual desta novamente. E, em seguida, uma vez que estamos a fazer, uma vez temos inserido o novo nó, queremos voltar nosso ponteiro para o novo chefe de uma lista ligada, o que já que estamos inserindo no começando, vai ser realmente um ponteiro para o nó que acabamos de criar. Vamos visualizar esta, porque eu acho que ele vai ajudar. 

Então aqui está a nossa lista, que consiste em quatro elementos, contendo um nó 15, o que aponta para um nó contendo 9, que aponta para um nó que contém 13, o que aponta para um nó que contenha 10, que tem o nulo ponteiro como seu próximo ponteiro de modo que é o fim da lista. Por isso, queremos inserir um novo nó com o valor 12 no início do presente lista, o que vamos fazer? Bem, primeiro nós malloc espaço para a nó, e, em seguida, vamos colocar 12 em lá. 

Então, agora chegamos a um ponto de decisão, certo? Nós temos um par de ponteiros que pudéssemos mover, qual devemos avançar em primeiro lugar? Devemos fazer 12 pontos para o novo chefe da lista-- ou me desculpar, devemos fazer 12 apontar para o antigo chefe da lista? Ou deveríamos dizer que o lista agora começa a 12. Há uma distinção lá, e nós olharemos o que acontece com ambos em um segundo. 

Mas isto conduz a um grande tema para a barra lateral, que é um dos que o as coisas mais complicadas com listas ligadas é organizar os ponteiros na ordem correta. Se você mover as coisas fora de ordem, você pode acabar acidentalmente orphaning o resto da lista. E aqui está um exemplo disso. Então, vamos ir com a idéia de-- bem, que acabamos de criar 12. Sabemos 12 vai ser o novo chefe da lista, e assim por que não vamos apenas mover o ponteiro lista para apontar lá. 

OK, então isso é bom. Então, agora onde é que 12 próximo ponto? Quero dizer, visualmente podemos ver que irá apontar para 15, como seres humanos é muito óbvio para nós. Como o computador sabe? Não temos nada apontando para mais 15, certo? 

Perdemos qualquer capacidade de referir-se a 15. Não podemos dizer nova seta ao lado equals alguma coisa, não há nada lá. Na verdade, temos órfãos o resto da lista ao fazê-lo, nós temos acidentalmente quebrou a cadeia. E nós certamente não queremos fazer isso. 

Então, vamos voltar e tentar novamente. Talvez a coisa certa a fazer é situado ao lado do ponteiro 12 para o antigo chefe da primeira lista, então podemos mover a lista mais. E, de fato, que é o ordem correta que nós precisamos seguir quando estamos Trabalhando com uma lista vinculada isoladamente. Nós sempre queremos conectar o novo elemento na lista, antes de tomar esse tipo de importante passo de alteração onde a cabeça da lista ligada é. Novamente, isso é uma coisa tão fundamental, nós não queremos perder o controle dela. 

Então, nós queremos ter certeza de que tudo é encadeados, antes de passar esse ponteiro. E assim esta seria a ordem correta, o qual é para ligar para a lista 12, em seguida, dizer que a lista começa a 12. Se disse que a lista começa em 12 e em seguida, tentou se conectar 12 da lista, já vimos o que acontece. Perdemos a lista por engano. 

OK, então mais uma coisa para falar. E se a gente quiser se livrar de toda uma lista ligada de uma vez? Mais uma vez, estamos mallocing todo este espaço, e por isso, preciso libertá-la quando estamos a fazer. Então, agora queremos excluir toda a lista ligada. Bem, o que nós queremos fazer? 

Se nós alcançamos o ponteiro nulo, nós quer parar, caso contrário, basta apagar o resto da lista e, em seguida, me libertar. Excluir o resto da lista, e, em seguida, liberar o nó atual. O que significa que o som como, qual técnica tem falamos sobre anteriormente é que o som como? Excluir todos os outros, em seguida, voltar e me excluir. 

Isso é recursão, fizemos o problema um pouco menor, nós estamos dizendo excluir todos mais, então você pode me excluir. E mais abaixo na estrada, esse nó vai dizer, excluir todos os outros. Mas eventualmente nós vamos chegar ao ponto em que a lista é nulo, e esse é o nosso caso base. 

Então, vamos dar uma olhada nisso, e como isso pode funcionar. Então aqui está a nossa lista, é o mesmo listar nós estávamos falando sobre, e há os passos. Há um monte de texto aqui, mas espero que a visualização vai ajudar. 

Então, nós have-- e eu também puxou a nossa pilha de quadros ilustração do nosso vídeo sobre pilhas de chamadas, e espero que tudo isso juntos irá mostrar-lhe o que está acontecendo. Então aqui está o nosso código pseudocódigo. Se chegarmos a um valor nulo ponteiro, parar, caso contrário, excluir o resto da lista, em seguida, liberar o nó atual. Então, agora, lista-- o ponteiro do que nós somos passando para destruir a 12 pontos. 12 não é um ponteiro nulo, por isso estamos indo para eliminar o resto da lista. 

O que é a exclusão do resto de nós envolvidos? Bem, isso significa fazer uma chamar para destruir, dizendo 15 é que o início do resto da lista queremos destruir. E assim a chamada para destruir 12 é uma espécie de em espera. Ele está congelado lá, esperando o chamar para destruir 15, para terminar o seu trabalho. 

Bem, 15 não é um ponteiro nulo, e por isso vai dizer, tudo bem, bem, exclua o resto da lista. O resto da lista começa às 9, e por isso vamos apenas espere até que você exclua tudo o que material, em seguida, voltar e apagar mim. Bem 9 vai dizer, bem, Eu não sou um ponteiro nulo, assim eliminar o resto da lista a partir daqui. E assim tentar destruir 13. 13 diz: Eu não sou ponteiro nulo, mesma coisa, ele passa o buck. 10 não é ponteiro nulo, 10 contém um ponteiro nulo, 10, mas não é ela própria uma Ponteiro Nulo agora, e assim que passa a bola também. 

E agora listar pontos lá, realmente chama a atenção para some-- se eu tivesse mais espaço na imagem, ele chama a atenção para algum espaço aleatório que nós não sabemos o que é. É o ponteiro nulo, porém, a lista é, literalmente, agora é definido valores nulos. Ele está apontando para a direita dentro daquela caixa vermelha. Chegamos a um ponteiro nulo, de modo podemos parar, e estamos a fazer. 

E assim que quadro roxo é agora-- no topo da stack-- esse é o quadro ativo, mas ele é feito. Se chegamos a um ponteiro nulo, pare. Nós não fazemos qualquer coisa, nós não pode liberar um ponteiro nulo, nós não malloc qualquer espaço, e por isso estamos a fazer. Então, esse quadro função é destruído, e nós resume-- nós pegar onde paramos fora com o mais elevado seguinte, que é este quadro azul escuro aqui. Então, nós pegar exatamente onde paramos. Nós excluído o resto do lista já, então agora estamos vai liberar os nós atuais. Então agora podemos libertar este nó, e agora chegamos ao fim da função. E assim que o quadro função é destruído, e nós pegar na uma luz azul. 

Por isso, says-- Eu já done-- a exclusão do resto da lista, de modo libertar o nó atual. E agora a moldura amarela é de volta ao topo da pilha. E assim como você pode ver, estamos agora destruindo a lista da direita para a esquerda. 

O que teria acontecido, porém, se tivéssemos feito as coisas de forma errada? Assim como quando tentámos adicionar um elemento. Se errei a cadeia, se nós não ligar os ponteiros na ordem correta, se nós apenas liberado o primeiro elemento, se nós só libertou o cabeça da lista, agora nós não têm nenhuma maneira para se referir a o resto da lista. E por isso, teria órfãs tudo, teríamos o que é chamado de fuga de memória. Se você se lembrar do nosso vídeo na alocação dinâmica de memória, isso não é coisa muito boa. 

Então, como eu disse, há várias operações que precisamos usar para trabalhar com lista ligada de forma eficaz. E você pode ter notado que eu omitido um, excluindo um único elemento a partir de um ligado Lista. A razão pela qual eu fiz isso é que é realmente tipo de complicado para pensar sobre como excluir um único elemento de uma isoladamente lista ligada. Precisamos ser capazes de passar por cima algo na lista, que Significa chegarmos a um que ponto-- quer apagar este node-- mas, a fim de torná-lo assim que nós não perca nenhuma informação, precisamos conectar este nó aqui, aqui. 

Então eu provavelmente fiz isso errado a partir de uma perspectiva visual. Então, estamos no início da nossa lista, estamos a proceder por meio de, que deseja excluir este nó. Se nós apenas excluí-lo, nós quebramos a corrente. Este nó aqui refere-se a tudo o resto, ele contém a cadeia de agora em diante. 

Então, o que precisamos fazer, na verdade, depois de chegarmos a este ponto, é que precisamos dar um passo atrás um, e conectar esse nó durante a esse nó, para que possamos, em seguida, apagar o um no meio. Mas as listas vinculada isoladamente não fazer nos fornecer uma maneira de ir para trás. Então, precisamos quer manter dois ponteiros, e movê-los espécie de off passo, um atrás do outros como nós vamos, ou chegar a um ponto e, em seguida, enviar um outro ponteiro completamente. E como você pode ver, pode ficar um pouco confuso. Felizmente, temos outra maneira de resolver isso, quando falamos de listas duplamente ligadas. 

Eu sou Doug Lloyd, este é CS50.