Sobre o conceito de Listas Encadeadas, responda:
2. Explique como remover um nó de uma lista encadeada simples, destacando os cuidados necessários para não “perder” nós em memória.
2. Explique como remover um nó de uma lista encadeada simples, destacando os cuidados necessários para não “perder” nós em memória.
Passo 1
O enunciado pede para explicar como remover um nó de uma lista encadeada simples, cuidando para não “perder” nenhum nó em memória. O conteúdo envolvido é manipulação de ponteiros e liberação de memória (por exemplo, em C com
malloc
/free
). Vamos precisar percorrer a lista, ajustar os ponteiros de ligação e depois liberar o nó removido.Passo 2
Para começar, precisamos localizar o nó que será removido mantendo dois ponteiros durante a varredura:
prev
aponta para o nó anterior ao atual.cur
aponta para o nó que estamos examinando.
Inicializeprev \(=\) NULL
ecur \(=\) head
. Em seguida, faça um loop enquantocur !\(=\) NULL
ecur->data
não for o valor-chave que desejamos remover, atualizandoprev \(=\) cur; cur \(=\) cur->next;
.
Passo 3
Depois do loop, temos duas situações:
cur \(==\) NULL
: percorremos até o fim e não encontramos o nó. Nesse caso, não há nada a remover; encerramos a operação.cur !\(=\) NULL
: encontramos o nó a remover.
Passo 4
Ajuste os links para excluir
cur
da cadeia:- Se
prev \(==\) NULL
, significa quecur
era o primeiro nó (cabeça da lista). Logo fazemoshead \(=\) cur->next
. - Caso contrário, fazemos
prev->next \(=\) cur->next
.
Assim, todos os nós antes de
cur
continuam ligados aos nós após cur
.Passo 5
Agora que
. Chamar
. Opcionalmente, atribuir
cur
não faz mais parte da lista, restam dois cuidados fundamentais:free(cur)
(ou o equivalente no seu ambiente) para liberar a memória alocada para aquele nó.cur \(=\) NULL
para evitar ponteiros “pendurados” (dangling pointers).Passo 6
Não esqueça de tratar também o caso de lista vazia (quando
head \(==\) NULL
antes de tudo) e de remover o último nó (o que funciona da mesma forma, basta que cur->next \(==\) NULL
após localizar o nó).Resposta
Para remover um nó de uma lista encadeada simples sem “perder” nada em memória, faça assim:
. Use dois ponteiros (
. Se
. Se
. Chame
. Lembre-se de cobrir casos especiais: lista inicialmente vazia, remoção da cabeça ou do último nó. Dessa forma, nenhum nó é “descartado” sem que sua memória seja devidamente liberada.
prev
e cur
) para encontrar o nó-alvo mantendo sempre referência ao anterior.cur
for NULL
, o nó não existe e nada muda.prev
for NULL
, atualize head \(=\) cur->next
; caso contrário, faça prev->next \(=\) cur->next
.free(cur)
para devolver a memória ao sistema e, se quiser, faça cur \(=\) NULL
para não deixar ponteiro pendurado.