Out4Mind O seu portal multi-temático
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.
