Estrutura de dados dinâmica realmente não é o assunto mais fácil da linguagem C, é realmente necessário estudar bastante para entender perfeitamente os conceitos e ideias por trás deste assunto.

Visando clarear mais a mente de nossos estudantes, a apostila C Progressivo vai explicar o conceito de lista apenas com figuras e explicações escritas, nada de código por hora.

Obtenha sua certificação em C e entre no Mercado de Trabalho! Leia este tutorial no seu computador ou celular: Apostila C Progressivo Lista encadeada - O nó Agora temos que 'ligar', 'conectar' ou 'encadear' esses dois nós.

Lembre-se que o ponteiro é para o tipo do nó, então podemos fazer com que o ponteiro do primeiro nó aponte para o segundo nó! E como o nó foi alocado de maneira dinâmica, ele também é representado por um endereço de memória, que será usado pelo ponteiro do elemento 1.
No nó 1, fazemos: ptr = Elemento2;
Porém, o ponteiro do segundo nó ainda aponta para outro endereço de memória (lixo).
Para podermos identificar que esse elemento é o último da lista, vamos fazer com que o ponteiro do nó 2 aponte para NULL, veja como ficou nossa lista encadeada:
[Image]  Pronto! Temos uma lista simples, com duas estruturas conectadas.




Inserindo nó ao final da lista Vamos colocar outro nó na lista?

Primeiro declaramos o elemento 3.

[Image]
Como queremos que ele fique depois do elemento 2, fazemos com que o ponteiro deste segundo elemento aponte para o nó 3. E para identificar o nó 3 como o último da lista, fazemos seu ponteiro apontar para NULL. Veja:

[Image]
 Simples, não? Agora raciocine como seria para colocar um quarto nó ao final da lista.
O que você faria? Quem apontaria para quem? E qual ponteiro vai apontar para NULL agora?

Conectando nós no início da lista Nos exemplos acima, conectamos nós ao final da lista.
Basicamente fazemos com que o nó antigo, que era o último, aponte para o novo nó, e o ponteiro desse novo nó aponte para NULL: é o nosso algoritmo para inserir um nó ao fim da lista.

Agora iremos aprender como inserir o nó no COMEÇO da lista, na primeira posição!
Como antes, primeiro declaramos um novo nó, o Elemento 4.
Ele está em algum lugar na memória, perdido e solitário, assim como o seu ponteiro.

[Image]
Precisamos, agora, conectar esse novo nó na lista.
Porém, ninguém vai apontar para ele desta vez. Agora é ele que vai apontar para o primeiro nó da lista, que é sempre chamado de head (ou cabeça, em português).

Ou seja, no ponteiro do novo nó, fazemos:
ptr = Elemento1 ou ptr=cabeca

[Image] E pronto! Adicionamos o nó 4 no início da lista. Simples e óbvio, não?
Inserindo um nó no meio da lista Vimos que para adicionar um nó no início da lista, basta o novo primeiro nó apontar para o antigo primeiro nó. Já para colocar ao fim da lista, simplesmente apontávamos o ponteiro do último nó para o novo nó.
E para adicionar no meio da lista? Fazemos as duas coisas. Por exemplo, para colocar o nó na segunda posição: primeiro declaramos o nó 4, que está em um lugar qualquer da memória. Agora fazemos com que o primeiro ponteiro deixe apontar para o nó 2 e aponte para o novo nó, o nó 4. E agora fazemos com que o nó 4 aponte para o nó 2.


[Image]

Excluindo um nó da lista Para excluir um nó de uma lista, devemos fazer com que esse nó não aponte para ninguém e que ninguém da lista aponte para ele. Ou seja, ele não pode se relacionar com nenhum nó, deve se isolar.
No exemplo anterior, se quisermos tirar o nó 2, é só fazermos os passos contrários.
[Image]
O nó 4 apontava para o 2. Vamos cortar essa relação: agora o nó 4 não vai mais apontar par ao nó 2, e sim para o nó 3. Podemos ainda fazer com que o nó 2 que apontava para o nó 3, aponte para outro lugar.
Pronto. Ninguém aponta para o nó 2, e ele não aponta para ninguém. O nó 1 aponta para o 4, que aponta para o 3, que aponta para NULL. Cadê o nó 2? Não faz mais parte, vai ficar lá perdido na memória, pois não vai se relacionar com ninguém da lista.

[Image]
E para excluir o primeiro nó?
Ora, o nó 1 só faz apontar para o nó 2. Se fizermos ele apontar para NULL, ele sai da lista, já que ele é o primeiro e ninguém aponta para ele.

E para excluir o último nó ?
Basta fazer com que o penúltimo nó, que apontava para o último, deixe de apontar para ele e aponte para NULL. Pronto, agora ninguém aponta pro último e ele ficou apontando para NULL, logo, não tem mais nenhuma relação com a lista encadeada.

Simples, bonitinho, com desenhos e tudo fazendo sentido.
Se não entender, leia, releia até entender. Só podemos ir para o próximo passo depois de entendido perfeitamente este tutorial de nosso curso.

Caso tenha entendido, é hora de partir para os códigos em C.
No próximo tutorial vamos ensinar como programar uma lista encadeada em C. Até lá.