How to remove a specific item from a double-chained list?

Asked

Viewed 1,103 times

0

Given 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 must create a method boolean remover(T item), 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 the null, when the program gives error.

There is something to be done to fix this or even a better construction for this method?

java chain-list

  • The program also gives NullPointerException if you try to remove an item from an empty list, correct?

  • Yeah, that’s right

  • General case to remove an item from a double chained list: Find the node to be deleted and do the proximo of the former becoming the anterior next. There are two special cases, which are the removal at the beginning or at the end of the list. To remove from the beginning, just make nullthe anterior of the second element. To exclude from the end, simply make nullthe proximo penultimate. If the list is empty, the method remover can be returned right at the beginning.

  • I don’t have access to Java at the moment, so I can’t create any code to help you or run your code. So I just explained in text only.

  • All right, but if you can show me later, when you’re available, I’d appreciate it. It’s hard for me to visualize like this.

  • Okay, if no one has answered by then, I’ll help you.

Show 1 more comment

1 answer

1


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

  1. primeiro.anterior = null; If the next one just went through with primeiro = primeiro.proximo; can stay in a null what will give NullPointerException when you do primeiro.anterior.

    Can solve this problem easily with a test:

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

  2. n = n.proximo; If the while advanced to the last (the one in which the proximo is null) then moving on to the next will cause n stay the null, that will give NullPointerException in comparison of while coming right after:

    while (n.anterior != null) {

    This instruction is even more and just remove it.

See your code working on Ideone with these two changes

I would personally turn the 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 contemplated the case that the list is already empty in the first if, not to make a mistake if you try to remove elements when you no longer have any. One of the ideas behind the double-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 the adjustments only from that.

Browser other questions tagged java chain-list

You are not signed in. Login or sign up in order to post.