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:
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!
0 comentários:
Postar um comentário