Listas Encadeadas

Aprenda a implementar uma lista encadeada completa, incluindo operações de adição, remoção e busca de elementos, seja no início, meio ou fim.
Primeiramente, veja como funciona uma lista encadeada através da imagem abaixo:

Os retângulos acima são chamados de nós(ou nodes, em inglês) da lista, os quais são compostos de um valor e um ponteiro para o próximo nó. Perceba que, é necessário um ponteiro para guardar o primeiro nó da lista(conhecido como a cabeça da lista), na representação acima o mesmo foi chamado de head. Já o ultimo nó da lista aponta para nada(NULL).

Agora vamos iniciar a implementação da lista em C, irei mostrar a implementação para uma lista de números inteiros, mas fica seu critério escolher o tipo de dado.

Para representar um nó, podemos criar uma struct, da seguinte maneira:
Como exposto acima, é necessário armazenar o primeiro nó da lista. É possível fazer isto de duas maneiras: fazendo um simples ponteiro ou armazenando um ponteiro em uma struct, que pode guardar mais algumas informações, como o tamanho da lista, por exemplo. Veja abaixo a implementação com struct:

Inicialização

É necessário inicializar os valores da lista antes de utilizá-la, já que, as variáveis estarão armazenando algum lixo de memória, o que traria problemas para a variável tamanho que deve ser iniciada com o valor 0 e é importante iniciar a cabeça com NULL, para "sabermos" se a lista está vazia(head = NULL). Para isso, vamos criar a função init:

Inserção

Há três tipos de inserção em uma lista encadeada, inserção no inicio, no fim e definida por número, veja a descrição e o algoritmo de cada uma destas a seguir:

• No inicio

Esta é a mais simples das três, basta definir o nó inserido como a cabeça da lista e definir como seu próximo a atual cabeça da lista:

• No fim

Para fazer esta inserção, é preciso lembrar que o ultimo nó da lista é aquele que aponta para NULL, veja novamente a imagem no inicio da postagem. Assim, basta ir percorrendo a lista até encontrar um nó que aponta para NULL e redefinir o prox para o no que será inserido, e já que estamos inserido no final, o nó a ser inserido deve apontar para NULL.

• No meio

Nesse caso, é preciso que seja dado um índice n para inserir o novo nó na enésima posição da lista.Aqui irei considerar o índice 0 como a primeira posição da lista, assim como acontece em um vetor.

Remoção

Existem vários tipos de remoção, alem dos tipos de inserção(inicio, por índice e fim), há tambem a remoção dado um valor, na qual o primeiro nó com este valor será removido da lista;

• No inicio

Para remover do inicio, siplesmente mudamos a cabeça da lista para o proximo nó após a cabeça e,claro, desalocar o nó removido. Veja o código:

• No fim

Só é preciso percorrer a lista até chegar ao penultimo elemento, mudar seu proximo para NULL e desalocar o último nó.

• Dado um valor


Nesse caso, é necessário percorrer a lista até encontrar um nó cujo seu próximo tenha o valor dado e redefinir seu próximo para o próximo do que está sendo removido.Veja a imagem acima e o código abaixo:

Busca

A busca consiste em, dado um valor a função retorna o primeiro nó que o contem, o código é bem simples, basta percorrer a lista até encontrar um nó que tem aquele valor e retorná-lo, caso não exista um nó com o valor dado, a função retorna NULL, veja:

Impressão

Função simples que percorre a lista, imprimindo os valores de seus elementos:

Se encontrar algum erro ou tiver alguma dúvida, faça um comentário!