0

Dado a classe No, sendo:

public class No<T> {

T elemento;
No<T> proximo;
No<T> anterior;

public No(T elemento, No<T> anterior, No<T> proximo) {
    this.elemento = elemento;
    this.proximo = proximo;
    this.anterior = anterior;
}

public No(T elemento) {
    this.elemento = elemento;
    proximo = null;
    anterior = null;
}  

}

Devo criar um método boolean remover(T item), o qual tentei fazer da seguinte maneira:

public boolean remover(T item) {

    if (primeiro.elemento.equals(item)) {
        primeiro = primeiro.proximo;
        primeiro.anterior = null;
        return true;
    }

    No<T> n = primeiro;
    T aux1 = null;
    T aux2 = null;

    while (n.proximo != null) {
        if (item.equals(n.proximo.elemento)) {
            aux1 = n.proximo.elemento;
            n.proximo = n.proximo.proximo;
            break;
        }

        n = n.proximo;
    }

    n = n.proximo;

    while (n.anterior != null) {
        if (item.equals(n.anterior.elemento)) {
            aux2 = n.anterior.elemento;
            n.anterior = n.anterior.anterior;
            break;
        }

        n = n.anterior;
    }

    if (aux1 == aux2) {
        tamanho--;
        return true;
    }

    return false;
}

Desse modo, eu consegui remover quase todos os itens, menos o último antes do null, quando o programa dá erro.

Existe algo a se fazer pra consertar isso ou até mesmo uma construção melhor para esse método?

6
  • O programa também dá NullPointerException se você tenta remover um item de uma lista vazia, correto?
    – Gabriel
    6/12/2017 às 16:52
  • Sim, isso mesmo
    – naosei
    6/12/2017 às 16:54
  • Caso geral para remover um item de uma lista duplamente encadeada: Encontre o nodo a ser excluído e faça o proximo do anterior se tornar o anterior do próximo. Há dois casos especiais, que são a remoção no início ou no fim da lista. Para remover do início, basta tornar nullo anterior do segundo elemento. Para excluir do fim, basta tornar nullo proximo do penúltimo. Se a lista estiver vazia, o método remover pode ser retornado logo no começo.
    – Gabriel
    6/12/2017 às 17:02
  • Não tenho acesso ao Java no momento, então não posso criar nenhum código para lhe ajudar, nem rodar o seu código. Por isso me limitei a explicar apenas em texto.
    – Gabriel
    6/12/2017 às 17:04
  • Tudo bem, mas se você puder me mostrar depois, quando estiver disponível, eu ficaria agradecido. Fica difícil para eu visualizar assim.
    – naosei
    6/12/2017 às 17:13

1 Resposta 1

1

Tem dois problemas código:

if (primeiro.elemento.equals(item)) {
    primeiro = primeiro.proximo;
    primeiro.anterior = null; //<-- esta linha (1)
    return true;
}
...
while (n.proximo != null) {
    if (item.equals(n.proximo.elemento)) {
        aux1 = n.proximo.elemento;
        n.proximo = n.proximo.proximo;
        break;
    }

    n = n.proximo;
}

n = n.proximo; //<-- e esta linha (2)

while (n.anterior != null) {
    if (item.equals(n.anterior.elemento)) {
        aux2 = n.anterior.elemento;
        n.anterior = n.anterior.anterior;
        break;
    }

    n = n.anterior;
}
...
  1. primeiro.anterior = null; Se o proximo acabou de avançar com primeiro = primeiro.proximo; pode ficar num null o que irá dar NullPointerException quando fizer primeiro.anterior.

    Pode resolver este problema facilmente com um teste:

    if (primeiro.elemento.equals(item)) {
        primeiro = primeiro.proximo;
        if (primeiro != null){
            primeiro.anterior = null;
        }
        return true;
    }
    
  2. n = n.proximo; Se o while avançou até ao ultimo (aquele em que o proximo é null) então avançar para o próximo vai fazer com que n fique a null, que irá dar NullPointerException na comparação do while que vem logo a seguir:

    while (n.anterior != null) {
    

    Esta instrução está mesmo a mais e basta apenas remove-la.

Veja o seu código a funcionar no Ideone com estas duas alterações


Eu pessoalmente transformaria a remoção em algo mais simples:

public boolean remover(T item) {    
    if (primeiro == null) return false; //se está vazia não faz nada

    if (primeiro.elemento.equals(item)) {
        primeiro = primeiro.proximo;
        if (primeiro != null){
            primeiro.anterior = null;
        }
        return true;
    }

    No<T> n = primeiro;     
    while (n != null && !n.elemento.equals(item)){ //achar o elemento a remover
        n = n.proximo;      
    }

    if (n == null) return false; //se não achou sai com false

    n.anterior.proximo = n.proximo; //ajusta o proximo do anterior
    if (n.proximo != null){ //ajusta o anterior do proximo se existir
        n.proximo.anterior = n.anterior;
    }
    tamanho--;
    return true;
}

Veja este exemplo também no Ideone

Note que contemplei adicionalmente o caso da lista já estar vazia no primeiro if, para não dar erro se tentar remover elementos quando já não tem nenhum. Uma das ideias por detrás das listas duplamente ligadas é que é fácil saber o elemento anterior e próximo, logo podemos diretamente navegar até ao elemento a remover e fazer os ajustes somente a partir desse.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .