[Powered by Google Translate] Na programação, muitas vezes precisamos representar listas de valores, como os nomes dos alunos em uma seção ou os seus resultados no último teste. 

Na linguagem C, declarado matrizes podem ser utilizadas para armazenar listas. É fácil enumerar os elementos de uma lista armazenados em uma matriz, e se você precisa acessar ou modificar o elemento da lista om por algum índice arbitrário I, que pode ser feito em tempo constante, mas as matrizes apresentam desvantagens, também. 

Quando nós declará-los, somos obrigados a dizer na frente como eles são grandes, isto é, quantos elementos que podem armazenar e qual o tamanho destes elementos são, que é determinada pelo tipo. Por exemplo, int arr (10) pode armazenar 10 itens que são do tamanho de um int. 

Nós não podemos mudar o tamanho de uma matriz após a declaração. Nós temos que fazer uma nova matriz se deseja armazenar mais elementos. A razão dessa limitação existe é que o nosso programa armazena todo o conjunto como um pedaço contíguo de memória. Dizer que este é o buffer onde se armazenados em nossa matriz. Pode haver outras variáveis localizado ao lado da matriz na memória, por isso não podemos apenas fazer a matriz maior. 

Às vezes, nós gostaríamos de trocar de velocidade a matriz de acesso rápido de dados para um pouco mais de flexibilidade. Digite a lista ligada, uma outra estrutura de dados básica você não pode ser tão familiarizado. A um nível elevado, uma lista ligada armazena os dados numa sequência de nodos que estão ligados uns aos outros com links, portanto, "lista ligada." o nome Como veremos, esta diferença no projeto conduz a diferentes vantagens e desvantagens de uma matriz. 

Aqui está um código C para uma lista muito simples ligada de inteiros. Você pode ver que temos representado cada nó na lista como uma estrutura que contém duas coisas, um inteiro para armazenar chamado 'Val' e um link para o próximo nó na lista que representamos como um ponteiro chamado 'próximo'. Dessa forma, é possível acompanhar toda a lista com apenas um único ponteiro para o nó 1, e então podemos seguir os ponteiros próximos para o nó 2, para o nó 3, ao nó 4, e assim por diante, até chegar ao fim da lista. 

Você pode ser capaz de ver uma vantagem isso tem sobre a estrutura de array estático - com uma lista ligada, não precisamos de um grande pedaço de memória completamente. O nó 1 da lista poderia viver neste lugar na memória, eo nó 2 poderia ser todo o caminho até aqui. Podemos chegar a todos os nós, não importa onde eles estão na memória, porque a partir do nó 1, o ponteiro próximo de cada nó nos diz exatamente onde ir. 

Além disso, não temos que dizer na frente como uma grande lista encadeada será a nossa forma de fazer com arrays estáticos, uma vez que podemos continuar a adicionar nós a uma lista enquanto não há espaço em algum lugar na memória para novos nós. Portanto, listas ligadas são fáceis de redimensionar dinamicamente. Dizer, mais tarde no programa, precisamos adicionar mais nós em nossa lista. Para inserir um novo nó em nossa lista em tempo real, tudo o que temos a fazer é alocar a memória para esse nó, plop no valor de dados, e depois colocá-lo onde quiser, ajustando os ponteiros apropriados. 

Por exemplo, se quiséssemos colocar um nó no meio os nós 2 e 3 da lista,  não teríamos para mover os nós 2 ou 3 em tudo. Dizer que estamos inserindo este nó vermelho. Tudo que temos a fazer é definir ponteiro próximo do novo nó de para apontar para o nó 3 e, em seguida, religar ponteiro próximo nó 2 do para apontar para o novo nó. Assim, podemos redimensionar nossas listas na mosca desde o nosso computador não dependem de indexação, mas sim na ligação entre o uso de ponteiros para armazená-los. 

Listas No entanto, uma desvantagem do ligadas é que, ao contrário de uma matriz estática, o computador não pode simplesmente pular para o meio da lista. Desde que o computador tem que visitar cada nó na lista ligada para chegar ao próximo, que vai levar mais tempo para encontrar um nó específico do que seria em um array. Para percorrer a lista inteira leva um tempo proporcional para o comprimento da lista, ou O (n) em notação assintótica. Em média, atingindo qualquer nó também leva um tempo proporcional a n. 

Agora, vamos realmente escrever um código que trabalha com listas ligadas. Vamos dizer que queremos uma lista ligada de inteiros. Podemos representar um nó na nossa lista novamente como uma estrutura com dois campos, um valor inteiro chamado 'Val' e um ponteiro próximo para o próximo nó da lista. Bem, parece bastante simples. 

Vamos dizer que queremos escrever uma função que percorre a lista e imprime o valor armazenado no último nó da lista. Bem, isso significa que teremos que percorrer todos os nós da lista para encontrar a última, mas desde que não está adicionando ou apagar nada, não queremos mudar a estrutura interna dos ponteiros seguintes na lista. 

Então, vamos precisar de um ponteiro especificamente para passagem que chamaremos de "rastreador". Vai rastejar através de todos os elementos da lista seguindo a cadeia de ponteiros próximos. Tudo o que temos armazenado é um ponteiro para o nó 1, ou "cabeça" da lista. Pontos de cabeça para o nó 1. É o tipo de ponteiro a nó. 

Para obter o nó 1 real na lista, temos que dereference esse ponteiro, mas antes que possamos cancelar a referência de que, é preciso verificar se o ponteiro é nulo primeiro. Se for nulo, a lista está vazia, e devemos imprimir uma mensagem que, porque a lista é vazia, não há último nó. Mas, vamos dizer que a lista não é vazia. Se não é, então devemos rastrear toda a lista até chegarmos ao último nó da lista, e como podemos saber se nós estamos olhando para o último nó na lista? 

Bem, se ponteiro próxima de um nó é nulo, sabemos que estamos no final desde o último ponteiro seguinte teria nenhum nó seguinte na lista para apontar. É uma boa prática para manter sempre ponteiro próximo do nó passado inicializado como nulo ter uma propriedade padronizada que nos alerta quando chegamos ao fim da lista. 

Então, se rastreador → seguinte é nulo, lembre-se que a sintaxe flecha é um atalho para dereferencing um ponteiro para uma estrutura, em seguida, acessar seu próximo campo equivalente ao incómodo: (* Rastreador). Seguinte. Uma vez que tenhamos encontrado o último nó, queremos imprimir rastreador → val, o valor do nó actual que sabemos que é a última. Caso contrário, se nós não estamos ainda no último nó na lista, temos que seguir em frente para o próximo nó na lista e verificar se esse é o último. Para fazer isso, basta fazer o nosso ponteiro rastreador para apontar para o próximo valor do nó atual, isto é, o nó seguinte na lista. Isto é feito ajustando rastreador = rastreador → seguinte. Em seguida, repetimos este processo, com um laço, por exemplo, até encontrar o último nó. Assim, por exemplo, se rastreador estava apontando para a cabeça, vamos definir rastreador para apontar para rastreador → seguinte, que é o mesmo que o próximo campo do nó 1. Então, agora o nosso rastreador está apontando para o nó 2, e, de novo, repetir este com um ciclo, até que tenhamos encontrado o último nó, isto é, onde ponteiro próximo do nó está a apontar para null. E aí temos que, nós encontramos o último nó na lista, e para imprimir o seu valor, é só usar rastreador → val. 

O deslocamento não é tão ruim, mas o que sobre a inserção? Vamos dizer que nós queremos inserir um inteiro na posição 4 em uma lista de inteiros. Que se encontra entre os nós de corrente 3 e 4. Mais uma vez, temos que percorrer a lista apenas para chegar ao elemento terceiro, aquele que está inserindo depois. Então, criamos um ponteiro rastreador novamente para percorrer a lista, verificar se o nosso ponteiro cabeça é nulo, e se não é, aponta nosso ponteiro rastreador no nó de cabeça. Então, estamos no primeiro elemento. Nós temos que ir para a frente dois elementos mais antes que possamos inserir, por isso podemos usar um loop int i = 1; i <3, i + + e em cada iteração do loop, avançar nosso ponteiro rastreador frente por um nó verificando se o campo próximo do nó atual é nulo, e se não é, mover nosso ponteiro rastreador para o próximo nó definindo-o igual ao ponteiro próximo do nó atual. Assim, desde que o nosso circuito para fazer isso, diz duas vezes, chegamos ao nó 3, e uma vez que nosso ponteiro rastreador atingiu o nó após que queremos inserir o nosso inteiro novo, como é que nós realmente a inserção? 

Bem, o nosso novo inteiro tem de ser inserida na lista como parte de sua estrutura próprio nó, uma vez que esta é realmente uma seqüência de nós. Então, vamos fazer um novo ponteiro para o nó chamado "new_node ' e configurá-lo para apontar para a memória que agora alocar sobre a pilha para o próprio nó, ea quantidade de memória que precisamos alocar? Assim, o tamanho de um nó, e queremos definir seu campo val para o número inteiro que deseja inserir. Vamos dizer, 6. Agora, o nó contém o nosso valor inteiro. É também uma boa prática para inicializar próximo campo o novo nó de para apontar para null, mas e agora? 

Temos que mudar a estrutura interna da lista e os ponteiros próximos contida existente da lista Nós 3 e 4. Uma vez que os ponteiros próximos determinar a ordem da lista, E já que estamos inserindo nosso novo nó para a direita no meio da lista, pode ser um pouco complicado. Isto porque, lembre-se, o nosso computador só sabe a localização de nós na lista por causa dos ponteiros próximos armazenados nos nós anteriores. Então, se alguma vez perdeu a noção de qualquer um destes locais, dizer alterando um dos ponteiros próximos em nossa lista, por exemplo, dizer que mudou campo seguinte o nó 3 é para apontar para algum nó aqui. Nós estaríamos fora de sorte, porque não faria tem alguma idéia de onde encontrar o resto da lista, e isso é, obviamente, muito ruim. Então, nós temos que ter muito cuidado sobre a ordem em que manipular os ponteiros próximas durante a inserção. 

Então, para simplificar, vamos dizer que nossos primeiros quatro nós são denominados A, B, C, e D, com as setas que representam a cadeia de ponteiros que ligam os nós. Então, precisamos inserir nosso novo nó entre os nós C e D. É fundamental fazê-lo na ordem certa, e eu vou mostrar-lhe porquê. 

Vamos olhar para a maneira errada de fazer isso primeiro. Ei, sabemos que o novo nó tem que vir logo depois C, então vamos definir ponteiro próximo do C para apontar para new_node. Tudo bem, parece tudo bem, só temos que terminar agora por fazendo ponto o novo nó do ponteiro ao lado de D, mas espera, como podemos fazer isso? A única coisa que poderia nos dizer onde era D, o ponteiro próximo foi previamente armazenado em C, mas nós apenas reescreveu que o ponteiro para apontar para o novo nó, assim já não temos qualquer pista onde D é na memória, e nós perdemos o resto da lista. Não é bom em tudo. 

Então, como vamos fazer isso certo? Primeiro, apontar ponteiro seguinte, o novo nó no D. Agora, os ponteiros tanto o novo nó e C do próximo estão apontando para o mesmo nó, D, mas isso é bom. Agora podemos apontar ponteiro próximo do C no novo nó. Então, nós fizemos isso sem perder quaisquer dados. No código, C é o nó actual que a travessia ponteiro rastreador está apontando, e D é representada pelo nó apontado pelo campo seguinte do nó actual, ou rastreador → seguinte. Então, primeiro definir ponteiro seguinte, o novo nó para apontar para rastreador → seguinte, da mesma forma que disse ponteiro próxima new_node deveria apontar para D na figura. Então, podemos definir ponteiro próximo do nó atual para nosso novo nó, assim como nós teve de esperar até o ponto C para new_node no desenho. Agora tudo está em ordem, e não perdemos o controle de todos os dados, e fomos capazes de apenas furar o nosso novo nó no meio da lista sem reconstruir a coisa toda ou até mesmo deslocando todos os elementos do jeito que teria que ter com uma matriz de comprimento fixo. 

Então, listas ligadas são um básico, mas importante, estrutura de dados dinâmica que têm vantagens e desvantagens em comparação com as matrizes e outras estruturas de dados, e, como é frequentemente o caso em ciência da computação, é importante saber quando usar cada ferramenta, para que você possa escolher a ferramenta certa para o trabalho certo. 

Para mais prática, tente escrever funções para excluir nós de uma lista ligada - lembre-se de ter cuidado com a ordem em que você reorganizar os ponteiros próximos para garantir que você não perca um pedaço de sua lista - ou uma função para contar os nós em uma lista ligada, ou um divertimento, para inverter a ordem de todos os nós em uma lista ligada. 

Meu nome é Jackson Steinkamp, ​​este é CS50.