Listas em C - O que é e como funciona uma List

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ó

Vamos tentar explicar, sem pressa e com detalhes, cada uma das ideias e elementos necessários para se estudar e trabalhar com estruturas de dados dinâmicas.

O objetivo deste tutorial de nossa apostila é que você entenda, na sua cabeça, como tudo funciona.
E esta é uma dica valiosa: antes de programar e fazer seu aplicativo rodar, ele tem que rodar perfeitamente na sua cabeça.  Ou seja: antes de começar, entenda e faça na mente.

Vamos chamar cada struct, a partir de agora, de nó.

Por exemplo, criamos uma struct com algumas variáveis e um ponteiro que aponta para o seu próprio tipo. Logo, quando criamos tal nó, é da seguinte forma:

Pronto. Esse nó está em algum ponto da memória, e seu ponteiro aponta para um endereço de memória qualquer.

Agora vamos declarar outro nó, o Elemento 2. Seu funcionamento e criação (alocando memória de maneira dinâmica) são idênticos ao Elemento 1, e essa estrutura, ou nó, está em um lugar qualquer da memória, bem como seu ponteiro aponta para um local aleatório, chamado de lixo.

Veja:

Conectando os nós de uma lista

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:

 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.

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:

 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.

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

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.

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.

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.

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á.