Dando continuidade ao nosso Curso de Programação C e ao estudo da estrutura lista encadeada, vamos nesta aula aprender como remover um nó da estrutura lista simplesmente encadeada. Nesta primeira versão não utilizaremos a estrutura Lista, apenas a estrutura Nó.
Para remover um nó é necessário realizar uma busca, descobrir onde se encontra o elemento que desejamos remover. Assim como na inserção ordenada, teremos aqui ao menos duas possibilidades, remover o primeiro nó ou remover um nó no meio da lista.
Para remover o primeiro nó precisamos criar um ponteiro auxiliar para o mesmo e, em seguida, fazer o início da lista apontar para o próximo nó do nó que será removido. Para o retorno ha diversas possibilidades e a escolha vai depender do problema que você está resolvendo com uma lista encadeada. A primeira possibilidade é não retornar, liberando a memória do nó a ser removido. A segunda possibilidade é retornar apenas a informação do nó, neste caso um número inteiro. Por fim, podemos também retornar o ponteiro para o nó que está sendo removido. Aqui irei adotar esta terceira opção.
/*
remoção do primeiro nó da lista
num = valor a ser removido da lista
*/
No *remover = NULL;
if(*lista){
if((*lista)->valor == num){
remover = *lista;
*lista = remover->proximo;
}
else{
...
}
}
return remover;
Se o valor a ser removido não for o valor do primeiro nó, então precisamos percorrer a lista em busca deste valor que pode ou não existir. Criamos um ponteiro auxiliar para percorrer a lista enquanto o próximo for diferente de nulo e seu valor for diferente do valor procurado.
Esta repetição pode finalizar por dois motivos: ou porque encontramos o nó a ser removido ou porque chegamos ao final da fila. Se chegamos ao final da fila então o próximo será nulo e não faremos nada. Contudo, se o próximo for diferente de nulo, então é ele que iremos remover fazendo as devidas manipulações dos ponteiros.
/*
função completa para remover um nó da lista
*/
No* remover(No **lista, int num){
No *aux, *remover = NULL;
if(*lista){
if((*lista)->valor == num){
remover = *lista;
*lista = remover->proximo;
}
else{
aux = *lista;
while(aux->proximo && aux->proximo->valor != num)
aux = aux->proximo;
if(aux->proximo){
remover = aux->proximo;
aux->proximo = remover->proximo;
}
}
}
return remover;
}
Código completo em C para remover da Lista Simplesmente Encadeada
/*
Código escrito por Wagner Gaspar
Agosto de 2021
Aula 250: Lista Simplesmente Encadeada
Como remover SEM a estrutura lista?
*/
typedef struct no{
int valor;
struct no *proximo;
}No;
// procedimento para inserir no início
void inserir_no_inicio(No **lista, int num){
No *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
novo->proximo = *lista;
*lista = novo;
}
else
printf("Erro ao alocar memoria!\n");
}
// procedimento para inserir no fim
void inserir_no_fim(No **lista, int num){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
novo->proximo = NULL;
// é o primeiro?
if(*lista == NULL)
*lista = novo;
else{
aux = *lista;
while(aux->proximo)
aux = aux->proximo;
aux->proximo = novo;
}
}
else
printf("Erro ao alocar memoria!\n");
}
// procedimento para inserir no meio
void inserir_no_meio(No **lista, int num, int ant){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
// é o primeiro?
if(*lista == NULL){
novo->proximo = NULL;
*lista = novo;
}
else{
aux = *lista;
while(aux->valor != ant && aux->proximo)
aux = aux->proximo;
novo->proximo = aux->proximo;
aux->proximo = novo;
}
}
else
printf("Erro ao alocar memoria!\n");
}
// procedimento para inserir ordenado
void inserir_ordenado(No **lista, int num){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
// a lista está vazia?
if(*lista == NULL){
novo->proximo = NULL;
*lista = novo;
} // é o menor?
else if(novo->valor < (*lista)->valor){
novo->proximo = *lista;
*lista = novo;
}
else{
aux = *lista;
while(aux->proximo && novo->valor > aux->proximo->valor)
aux = aux->proximo;
novo->proximo = aux->proximo;
aux->proximo = novo;
}
}
else
printf("Erro ao alocar memoria!\n");
}
// função para remover um nó da lista
No* remover(No **lista, int num){
No *aux, *remover = NULL;
if(*lista){
if((*lista)->valor == num){
remover = *lista;
*lista = remover->proximo;
}
else{
aux = *lista;
while(aux->proximo && aux->proximo->valor != num)
aux = aux->proximo;
if(aux->proximo){
remover = aux->proximo;
aux->proximo = remover->proximo;
}
}
}
return remover;
}
void imprimir(No *no){
printf("\n\tLista: ");
while(no){
printf("%d ", no->valor);
no = no->proximo;
}
printf("\n\n");
}
int main(){
int opcao, valor, anterior;
No *removido, *lista = NULL;
do{
printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - InserirM\n\t4 - InserirO\n\t5 - Remover\n\t6 - Imprimir\n");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_no_inicio(&lista, valor);
break;
case 2:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_no_fim(&lista, valor);
break;
case 3:
printf("Digite um valor e o valor de referencia: ");
scanf("%d%d", &valor, &anterior);
inserir_no_meio(&lista, valor, anterior);
break;
case 4:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_ordenado(&lista, valor);
break;
case 5:
printf("Digite um valor a ser removido: ");
scanf("%d", &valor);
removido = remover(&lista, valor);
if(removido){
printf("Elemento a ser removido: %d\n", removido->valor);
free(removido);
}
else
printf("Elemento inexistente!\n");
break;
case 6:
imprimir(lista);
break;
default:
if(opcao != 0)
printf("Opcao invalida!\n");
}
}while(opcao != 0);
return 0;
}
