Out4Mind O seu portal multi-temático
Na primeira parte deste artigo, fiz uma introdução às listas duplamente ligadas e falei dos métodos de inserção de nós. Agora vamos ver métodos de remoção.
Remoção à cabeça
A remoção à cabeça é, também, feita de forma muito semelhante ao que fazermos nas listas ligadas simples. Acedemos, portanto, ao nó que está a ser apontado pela cabeça (primeiro nó) e copiamos o seu apontador “seguinte” para a cabeça, libertando-o em seguida da memória. Agora, temos ter em atenção que o “novo primeiro nó” – “790” – era o segundo nó na lista e o seu apontador “anterior” apontava para o nó “1234”. Como o nó “790” passa a ser o novo primeiro nó, o seu apontador “anterior” deverá ficar a NULL. A implementação é de todo parecida com a remoção à cabeça de uma lista ligada simples, tendo que ser adicionado o código para ajustar a apontador “anterior”. Experimente fazer!
Remoção à cauda
A remoção à cauda, é feita de forma semelhante à remoção à cabeça mas a partir do apontador “cauda“. Neste caso, copia-se o apontador “anterior” do último nó para a cauda e liberta-se o nó da memória. Porém, note mais uma vez que, o novo “último nó” terá ainda a seu apontador “seguinte” a apontar para o antigo nó “2154” e deverá ser alterado para NULL. Já iremos ver o código mais à frente.
Remoção a meio da lista
Para removermos um nó a meio de uma lista duplamente ligada, podemos fazer por dois processos. Ou procuramos o nó a partir da cabeça e usando os apontadores “seguinte“, ou procuramos o nó a partir da cauda e usando os apontadores “anterior“.
Vejamos o primeiro caso, procurando a partir da cabeça. Teremos então que procurar o nó que antecede o nó que queremos remover. Uma vez encontrado, e de forma semelhante à lista ligada simples, copiamos o apontador “seguinte” do nó a remover (na figura o nó “1234”) para o nó anterior (na figura o nó “4220”), de forma a que este agora passe a apontar para o nó que sucede o nó a remover (na figura o nó “790”). Mais uma vez, e porque estamos numa lista duplamente ligada, teremos que aceder a este último (“790”) e alterar o apontador “anterior” para o nó que antecede o nó que queremos remover. Efectuadas estas operações, a integridade da lista está garantida e podemos libertar o nó a remover da memória. Na lista ligada simples, vimos que podíamos usar este processo para remover o nó à cauda, pois ao copiar o apontador “seguinte” do último nó (que aponta para NULL) para o nó que o antecede, estamos a tornar este o novo último nó. Porém, há que ter em atenção que, numa lista duplamente ligada, temos o apontador “cauda” e este teria que ser também alterado! Caso contrário, ficaria a apontar para um nó que deixou de existir!
No caso de pretendermos procurar o nó a remover a partir da cauda, o processo será semelhante mas teremos que procurar o nó que sucede o nó que queremos remover e copiar o apontador “anterior” do nó a remover (na figura o “1234”) para o nó “790”, de forma a que este passe a apontar para o nó que antecede o nó a remover (“4220”). Em seguida, teremos que aceder a este nó (“4220”) para alterar o seu apontador “seguinte” para o nó “790”. Finalmente, efectuadas estas operações, podemos libertar o nó a remover da memória. Ainda neste caso, se o nó a remover fosse o primeiro, ao copiar o nó “anterior” deste para o nó que o sucede, estamos a tornar este o novo primeiro nó. Mas mais uma vez, teríamos que alterar o apontador “cabeça” para que este não fique a apontar para um nó que deixou de existir!
Vamos agora ver um exemplo de código para remover um nó com um determinado valor. Neste exemplo, vamos ver como fazer a pesquisa desse nó a partir da cauda (do fim para o início):
int v = valor_remover;
bool removeu = false;
no = cauda;
if (no->valor==v) {
cauda = no->anterior;
NoDuplo* no_antecedente = no->anterior;
if (no_antecedente==NULL) {
cabeca = NULL;
}
else {
no_antecedente->seguinte = NULL;
}
free(no);
removeu = true;
}
else {
while (no->anterior!=NULL) {
NoDuplo *remover = no->anterior;
if (remover->valor==v) {
no->anterior = remover->anterior;
NoDuplo* no_antecedente = remover->anterior;
if (no_antecedente==NULL) {
cabeca = no;
}
else {
no_antecedente->seguinte = remover->seguinte;
}
free(remover);
removeu = true;
break;
}
no = no->anterior;
}
}
if (!removeu) {
cout << "O valor não foi encontrado!" << endl;
}
Na primeira linha, declaramos uma variável “v” com o valor do nó que pretendemos remover e, como vamos procurar o nó a partir da cauda, na linha 3 iniciamos o apontador “no”, usado na pesquisa, com a valor do apontador “cauda”.
Na linha 4 verificamos se o valor a remover está no último nó, apontado pela cauda. Se estiver, estamos perante uma remoção à cauda! Assim, há que alterar a cauda para apontar para o nó anterior ao nó que queremos remover (linha 5) e definir um apontador para o nó antecedente para o actualizar (linha 6). Porém, há que ter em atenção um pormenor importante! E se estamos a remover o único nó da lista? Nesse caso, o apontador do nó antecedente será NULL (linha 7) e a lista deverá ficar vazia, pelo que teremos que alterar o apontador “cabeca” para NULL (linha 8)! Já o apontador “cauda”, ao receber o valor do “nó anterior”, sendo este NULL, ficará automaticamente a NULL. (1)
Caso não seja o único nó da lista, alteramos o apontador “seguinte” do nó antecedente para NULL uma vez que este passará a ser o “novo último nó” (linha 11).
Não tendo sido encontrado o valor a remover no último nó, seguimos com a pesquisa através do ciclo “while” da linha 17. Repare que, na linha 18, vamos procurar o valor a remover no nó anterior ao do ciclo, pois temos que manter em “no” a referência do nó que sucede o nó que queremos remover! Ao encontrar o valor a remover (linha 19), copiamos então o apontador “anterior” deste para o nó que o sucede (linha 20). Na linha 21, vamos aceder ao nó antecedente ao nó a remover e teremos que verificar se estamos a remover o primeiro nó! Nesse caso, este nó antecedente será NULL (linha 22) e teremos que alterar a cabeça para o nó que sucede o nó a remover (linha 23) que passará a ser o “novo primeiro nó”! Repare ainda que, se o nó a remover for o primeiro nó, este terá o seu apontador “anterior” a NULL e, ao fazer a cópia da linha 20, automaticamente iremos ter o nó que o sucede com o apontador “anterior” a NULL (primeiro nó / início da lista).
Caso contrário, copiamos o apontador “seguinte” do nó a remover para o seu nó antecedente (linha 26). O código testa ainda se o valor a remover foi encontrado e exibe uma mensagem caso não o encontre.
Note ainda 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.
Lembre-se também que, no fim da execução do programa, se a lista não estiver vazia, teremos que libertar todos os nós da memória. No código da lista ligada simples, usei um método recursivo como exemplo. Mas podemos usar outras soluções, como, por exemplo, eliminar sucessivamente os “primeiros nós” até a lista ficar vazia:
if (cabeca!=NULL) {
while (cabeca!=NULL) {
NoDuplo* libertar = cabeca;
cabeca = cabeca->seguinte;
cout << "A libertar o nó com o valor: " << libertar->valor << endl;
free(libertar);
}
cauda = NULL;
}
Repare que não é necessário estar a actualizar os apontadores “anterior” pois estamos a limpar tudo! Também, no fim do ciclo, o apontador “cabeca” ficará a NULL, mas não o apontador “cauda”, que ficará a apontar para uma alocação que deixou de existir. Por isso, depois do ciclo, colocamos a apontador “cauda” a NULL.
Vamos agora ficar com o código completo deste exemplo:
#include <iostream>
#include <stdlib.h>
using namespace std;
struct NoDuplo {
int valor;
NoDuplo* seguinte;
NoDuplo* anterior;
};
int main() {
NoDuplo* no;
NoDuplo* cabeca = NULL;
NoDuplo* cauda = NULL;
char menu = ' ';
while (menu!='0') {
cout << "1 - Inserir valor à cabeça" << endl;
cout << "2 - Inserir valor à cauda" << endl;
cout << "3 - Remover nó de valor x" << endl;
cout << "4 - Listar valores dos nós a partir da cabeca" << endl;
cout << "5 - Listar valores dos nós a partir da cauda" << 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 = (NoDuplo*) malloc(sizeof(NoDuplo));
no->valor=atoi(valor_para_cabeca);
no->anterior = NULL;
if (cabeca==NULL) {
no->seguinte = NULL;
cauda = no;
}
else {
cabeca->anterior = no;
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 = (NoDuplo*) malloc(sizeof(NoDuplo));
no->valor=atoi(valor_para_fim);
no->seguinte = NULL;
if (cauda==NULL) {
no->anterior = NULL;
cabeca = no;
}
else {
cauda->seguinte = no;
no->anterior = cauda;
}
cauda = no;
break;
case '3':
if (cauda==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 = cauda;
if (no->valor==v) {
cauda = no->anterior;
NoDuplo* no_antecedente = no->anterior;
if (no_antecedente==NULL) {
cabeca = NULL;
}
else {
no_antecedente->seguinte = NULL;
}
free(no);
removeu = true;
}
else {
while (no->anterior!=NULL) {
NoDuplo *remover = no->anterior;
if (remover->valor==v) {
no->anterior = remover->anterior;
NoDuplo* no_antecedente = remover->anterior;
if (no_antecedente==NULL) {
cabeca = no;
}
else {
no_antecedente->seguinte = remover->seguinte;
}
free(remover);
removeu = true;
break;
}
no = no->anterior;
}
}
if (!removeu) {
cout << "O valor não foi encontrado!" << endl;
}
}
break;
case '4':
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 '5':
if (cauda==NULL) {
cout << "A lista está vazia!" << endl;
}
else {
no = cauda;
while (no!=NULL) {
cout << "Valor: " << no->valor << endl; no = no->anterior;
}
}
break;
default:
printf("Opção inválida!");
break;
}
}
if (cabeca!=NULL) {
while (cabeca!=NULL) {
NoDuplo* libertar = cabeca;
cabeca = cabeca->seguinte;
cout << "A libertar o nó com o valor: " << libertar->valor << endl;
free(libertar);
}
cauda = NULL;
}
}
No artigo “Lista duplamente ligada com classes template (Parte I)” dou um exemplo de uma implementação de uma lista duplamente ligada com classes.
Siga-nos nas redes sociais e esteja a par das nossas novidades no nosso blogue multi-temático Out4Mind!
Este artigo foi escrito de acordo com a antiga grafia.
Notas:
- No caso de estarmos a fazer a pesquisa do nó com o valor a remover a partir da cabeça, se este for o único nó, o apontador “cauda” ficará a NULL mas não o apontador “cabeca”! Neste caso, deveremos alterar a “cabeca” para NULL, pois a lista ficará vazia e queremos ambos os apontadores, “cabeca” e “cauda”, a NULL.
