Antes de tudo precisamos compreender do que se trata este tipo de implementação mais conhecida como
Lista Ligada ou
Lista Encadeada, é uma estrutura de dados
linear e dinâmica. Podemos guarda apenas o endereço do primeiro elemento, já que, cada um dos elementos (mais conhecidos como nó) apontam para o próximo, tendo o último nó apontado para uma célula nula (representando fim de lista).
Nó 1 >> Nó 2 >> Nó 3 >> No n >> NULL (nulo)
Vantagem
1. A inserção ou remoção de um determinado nó da lista não implicará na mudança de posição de outros nós.
2. Não precisamos saber qual será o número máximo de nós na lista, portanto não desperdiçaremos espaço na
Memória Principal (Memória RAM) do computador.
Desvantagens
1. Se a ligação entre os nós for mal feita poderá acarretar na perda de toda a lista.
2. Para acessar o nó na posição n da lista, deve-se percorrer os
n - 1 anteriores.
A partir daqui o leitor deverá ter no mínimo
conhecimento sobre a linguagem citada e
compreender os conceitos sobre o assunto. Cada um dos códigos abaixo teve suas principais características citadas, no entanto não foram abordados profundamente, o intuito deste guia é auxiliar na compreensão do assunto, portanto esperasse que o leitor já tenha ao menos tentado trabalhar com tal estrutura anteriormente.
Tudo aquilo que vier a seguir não foi copilado, portanto
pode conter erros, caso encontre-os apenas deixe um recado nos comentários que procurarei corrigir quando ler.
Estrutura (struct)
struct no
{
int numero;
struct no *prox;
};
O campo “
int numero;” representa um valor do tipo inteiro, poderíamos sem problemas adicionar outros campos à estrutura, como por exemplo um “
char letra;” na linha seguinte. O trecho “
struct no *prox;” será o ponteiro para o próximo nó da lista.
Inserção (ordem crescente)
no *inserir(struct no *raiz, int numero)
{
struct no *novo;
novo = (struct no*)malloc(sizeof(struct no));
novo->numero = numero;
if(raiz == NULL) {
raiz = novo;
novo->prox = NULL;
} else {
if(raiz->numero > numero) {
novo->prox = raiz;
return (novo);
} else {
struct no *aux_antes = raiz, *aux_depois = raiz;
while(aux_depois->prox != NULL) {
aux_depois = aux_depois->prox;
if(aux_depois->numero > numero) {
aux_antes->prox = novo;
novo->prox = aux_depois;
return (raiz);
}
aux_antes = aux_antes->prox;
}
aux_depois->prox = novo;
novo->prox = NULL;
}
}
return (raiz);
}
A função anterior irá inserir um novo nó no inicio se lista for nula ou o seu número for menor que o primeiro valor já existente na lista. Caso contrário será necessário procurar pelo local mais adequado, para isso percorreremos a lista através de um “
while”. Portanto o novo elemento será adicionado na posição encontrada ou no final caso não haja valores maiores que o novo nó,
retornará o nó inicial da lista.
Remoção (primeira ocorrência de um número)
no *remover(struct no *raiz, int numero)
{
if(raiz == NULL){
printf("A lista ja esta vazia.\n");
} else {
struct no *aux = raiz;
if(aux->numero == numero) {
aux = aux->prox;
free(raiz);
} else {
struct no *aux_antes = raiz, *aux_depois = raiz;
while(aux->prox != NULL) {
aux = aux->prox;
aux_depois = aux->prox;
if(aux->numero == numero) {
aux_antes->prox = aux_depois;
free(aux);
return (raiz);
}
}
}
}
return (raiz);
}
A função anterior irá remover um nó da lista, sendo que este seja a primeira ocorrência de valor informado. Percorrerá a lista desde que não seja nula,
retornará o nó inicial da lista.
Impressão (imprimir todos os nós)
void imprimir(struct no *raiz)
{
int contador = 0;
if(raiz == NULL){
printf("A lista esta vazia.\n");
} else {
struct no *aux = raiz;
while(aux->prox != NULL) {
contador++;
printf("Valor do no %d: %d\n", contador, aux->numero);
}
}
printf("Numero de nos: %d\n", contador);
}
A função anterior irá imprimir todos os valores da lista informando a qual nó se refere, ao terminar será impresso o número total de elementos. Percorrerá a lista desde que não seja nula.
Procurar por um número
int procurar(struct no *raiz, int numero)
{
if(raiz == NULL){
printf("A lista esta vazia.\n");
} else {
int posicao = 0;
struct no *aux = raiz;
while(aux->prox != NULL) {
posicao++;
if(aux->numero == numero) {
printf("Valor encontrado em: %d\n", posicao);
return 1;
}
}
}
printf("Valor nao encontrado.");
return 0;
}
A função anterior irá procurar por um determinado valor na lista, caso encontre imprimirá a sua posição. Percorrerá a lista desde que não seja nula,
retornará 0 caso não encontre e 1 caso tenha encontrado.
Alguns trechos deste artigo foram baseados na leitura desta página.
