Na primeira parte deste artigo, vimos a definição de listas ligadas simples e métodos de inserção de nós. Agora vamos ver métodos de remoção.
Remoção à cabeça
Na figura acima, podemos ver que, se pretendemos remover o primeiro nó de uma lista (remoção à cabeça), o processo é muito simples. Precisamos de aceder a este nó, que está a ser apontado pela cabeça, obter o apontador para o segundo nó e copiá-lo para a cabeça. Desta forma, a cabeça passará a apontar para o segundo nó, o qual passará então a ser o primeiro nó. Por fim, libertamos o primeiro nó da memória. Já iremos ver o código mais à frente, o qual contemplará esta situação.
Remoção a meio da lista e à cauda
Para removermos um nó no meio da lista, temos que procurá-lo a partir do nó anterior. Isto porque, iremos precisar de ter acesso ao nó anterior para poder copiar o apontador do nó seguinte, do nó que pretendemos remover, para o nó anterior. Desta forma, fazemos o apontador do nó seguinte, do nó anterior ao que queremos eliminar, apontar para o nó que está a seguir a este (seta verde). Feita esta operação, poderemos libertar da memória o nó que queremos remover.
A remoção à cauda pode ser feita exactamente pelo mesmo processo, pois, nesse caso, o apontador do nó seguinte, do nó que queremos remover, está a apontar para NULL. Ao copiar este apontador para o nó anterior, estamos a torná-lo o novo último nó!
Vamos ver o código em C++, que vai procurar um nó com um determinado valor para o remover:
int v = valor_a_remover; bool removeu = false; no = cabeca; if (no->valor==v) { cabeca = no->seguinte; free(no); removeu = true; } else { while (no->seguinte!=NULL) { No *remover = no->seguinte; if (remover->valor==v) { no->seguinte = remover->seguinte; free(remover); removeu = true; break; } no = no->seguinte; } } if (!removeu) { cout << "O valor não foi encontrado!" << endl; }
Podemos ver, na linha 1, que declaramos uma variável inteira “v” com o valor que pretendemos remover. Na linha 4, testamos se o valor está no nó apontado pela cabeça (primeiro nó). Caso esteja, estamos perante uma remoção à cabeça! Então, na linha 5 alteramos a cabeça para apontar para o nó seguinte (segundo nó) e a seguir libertamos da memória o nó que queremos remover. Caso contrário, teremos que procurar o nó anterior ao que queremos eliminar num ciclo “while” (linha 10). Em cada iteração do ciclo, obtemos a referência ao nó seguinte (linha 11) para testar se é o que queremos remover (linha 12). Quando encontrarmos o nó que queremos remover, copiamos o seu apontador do nó seguinte para o nó anterior (linha 13) e, em seguida, libertamos o nó a remover da memória (linha 14). O código testa ainda se o valor a remover foi encontrado e exibe uma mensagem caso não o encontre.
Note que, neste código, não testámos se a lista estava vazia. Mas tal processo deve ser feito, como poderá ver mais abaixo, no código completo.
Outro aspecto importante, é que devemos sempre libertar da memória todos os nós que estejam ainda alocados, quando o programa termina. Uma forma de o fazer é implementando um método recursivo que vai até ao final da lista e começa a remover os nós do último ao primeiro:
void liberta_lista(No *n) { if (n!=NULL) { liberta_lista(n->seguinte); cout << "A libertar a nó com o valor: " << n->valor << endl; free(n); } else { return; } }
Antes de terminar o programa, evocamos este método passando a cabeça como argumento!
liberta_lista(cabeca);
Vejamos agora o programa completo:
#include <iostream> #include <stdlib.h> using namespace std; struct No { int valor; No *seguinte; }; void liberta_lista(No *n) { if (n!=NULL) { liberta_lista(n->seguinte); cout << "A libertar o nó com o valor: " << n->valor << endl; free(n); } else { return; } } int main() { No *cabeca = NULL; No *no = NULL; char menu = ' '; while (menu!='0') { cout << "1 - Inserir valor à cabeça" << endl; cout << "2 - Inserir valor no fim" << endl; cout << "3 - Listar valores dos nós" << endl; cout << "4 - Remover nó de valor x" << endl; cout << "0 - Sair do programa" << endl; cin >> menu; switch (menu) { case '0': break; case '1': char valor_para_cabeca[6]; cout << "Introduza um novo valor para o inicio da lista: "; cin >> valor_para_cabeca; no = (No*) malloc(sizeof(No)); no->valor=atoi(valor_para_cabeca); if (cabeca==NULL) { no->seguinte = NULL; } else { no->seguinte = cabeca; } cabeca = no; break; case '2': char valor_para_fim[6]; cout << "Introduza um novo valor para o fim da lista: "; cin >> valor_para_fim; no = (No*) malloc(sizeof(No)); no->valor=atoi(valor_para_fim); no->seguinte = NULL; if (cabeca==NULL) { cabeca = no; } else { No *procura_ultimo = cabeca; while (procura_ultimo->seguinte!=NULL) { procura_ultimo = procura_ultimo->seguinte; } procura_ultimo->seguinte = no; } break; case '3': if (cabeca==NULL) { cout << "A lista está vazia!" << endl; } else { no = cabeca; while (no!=NULL) { cout << "Valor: " << no->valor << endl; no = no->seguinte; } } break; case '4': if (cabeca==NULL) { cout << "A lista está vazia!" << endl; } else { char valor_remover[6]; cout << "Introduza o valor a remover: "; cin >> valor_remover; int v = atoi(valor_remover); bool removeu = false; no = cabeca; if (no->valor==v) { cabeca = no->seguinte; free(no); removeu = true; } else { while (no->seguinte!=NULL) { No *remover = no->seguinte; if (remover->valor==v) { no->seguinte = remover->seguinte; free(remover); removeu = true; break; } no = no->seguinte; } } if (!removeu) { cout << "O valor não foi encontrado!" << endl; } } break; default: printf("Opção inválida!"); break; } } liberta_lista(cabeca); return 0; }
Na terceira parte deste artigo iremos implementar esta lista em classes.
– Listas ligadas simples em C++ (Parte III)
Este artigo foi escrito de acordo com a antiga grafia.