How do I remove a specific item from a double-chained list?

Question

How do I remove a specific item from a double-chained list?

Navigation

#1 by (1 votes)

0

Given the class No, being:

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;
}

}

I should create a boolean remover(T item) method, which I tried to do as follows:

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;
}

In this way, I was able to remove almost all items, except the last one before null , when the program fails.

Is there anything to do to fix this or even a better build for this method?

java lista-encadeada

asked by anonymous 06.12.2017 / 17:45

1 answer

Error executing POST method Create procedure in mysql

score 1 · Accepted Answer

You have two code problems:

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;
}
...

primeiro.anterior = null; If the next one has just gone ahead with primeiro = primeiro.proximo; it can stay in null which will give NullPointerException when it does primeiro.anterior .

You can easily solve this problem with a test:

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

n = n.proximo; If while has progressed to the last (the one where proximo is null ) then moving to the next will cause n to be null , which will give NullPointerException in the while comparison that follows:

while (n.anterior != null) {

This instruction is really over and just remove it.

See your code working on Ideone with these two changes

I would personally turn removal into something simpler:

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;
}

See this example also in Ideone

Note that I have additionally considered the case of the list already being empty in the first if , so as not to give error if you try to remove elements when you do not already have any. One of the ideas behind the doubly linked lists is that it is easy to know the previous and next element, so we can directly navigate to the element to be removed and make adjustments only from that.