Problem to add at the end of a Simple Chained List

Asked

Viewed 183 times

0

I have a simple chained list and need to do a recursive function that adds at the end of the list an element, I already have the function without recursiveness, but the with recursiveness is giving error. Follow the code and the error:

Function without recursion: 

void addFim(int chave) {
        if (isEmpty()) {
            addInicio(chave);
            return;
        }

        Node novo = new Node(chave);
        ultimo.prox = novo;
        ultimo = novo;
        N++;
    }

Function with recursion: 

void addFimRecursivo(int chave) {
        if (isEmpty()) {
            addInicio(chave);
            N++;
            return;
        }

        addFimRecursivo(null, primeiro, chave);
    }

    private void addFimRecursivo(Node anterior, Node atual, int chave) {
        if(atual.prox == null) {
            Node novo = new Node(chave);
            ultimo.prox = novo;
            ultimo = novo;
            N++;
        }

        addFimRecursivo(atual, atual.prox, chave);

    }

Error:

Exception in thread "main" java.lang.Nullpointerexception

List:

class Lista {

    private Node primeiro;
    private Node ultimo;
    private int N;

    /* construtor vazio */
    Lista() {
    }

    /* construtor */
    Lista(Node primeiro) {

        Node x;

        for (x = primeiro; x != null; x = x.prox) {
            addInicio(x.chave);
        }

    }

    void addInicio(int chave) {
        if (isEmpty()) {
            primeiro = new Node(chave);
            ultimo = primeiro;
            N++;
            return;
        }

        Node novo = new Node(chave);
        novo.prox = primeiro;
        primeiro = novo;
        N++;
    }

    void addFim(int chave) {
        if (isEmpty()) {
            addInicio(chave);
            return;
        }

        Node novo = new Node(chave);
        ultimo.prox = novo;
        ultimo = novo;
        N++;
    }

    void addFimRecursivo(int chave) {
        if (isEmpty()) {
            addInicio(chave);
            N++;
            return;
        }

        addFimRecursivo(null, primeiro, chave);
    }

    private void addFimRecursivo(Node anterior, Node atual, int chave) {
        if(atual.prox == null) {
            Node novo = new Node(chave);
            ultimo.prox = novo;
            ultimo = novo;
            N++;
        }

        addFimRecursivo(atual, atual.prox, chave);

    }

    void addEmOrdem(int chave) {

        if (isEmpty()) {
            addInicio(chave);
            return;
        }

        addEmOrdem(null, primeiro, chave);
    }

    void addEmOrdem(Node anterior, Node atual, int chave) {

        Node novo = new Node(chave);

        if (size() == 1) {
            if (chave < primeiro.chave) {
                addInicio(chave);
                return;
            } else {
                primeiro.prox = novo;
            }
            N++;
            return;
        }

        if (chave < atual.chave) {
            anterior.prox = novo;
            novo.prox = atual;
            return;
        }

        addEmOrdem(atual, atual.prox, chave);
    }

    void remove(int chave) {

        if (chave == primeiro.chave) {
            removeInicio();
            return;
        }

        remove(null, primeiro, chave);
    }

    private void remove(Node anterior, Node atual, int chave) {
        if (atual.chave == chave) {

            if (chave == ultimo.chave) {
                anterior.prox = null;
                ultimo = anterior;
                return;
            }

            Node sucessor = atual.prox;
            anterior.prox = sucessor;
            return;
        }

        remove(atual, atual.prox, chave);
    }

    void removeInicio() {
        primeiro = primeiro.prox;
    }

    void removeFim() {
        removeFim(null, primeiro);
    }

    private void removeFim(Node anterior, Node atual) {
        if (atual.prox == null) {
            anterior.prox = null;
            ultimo = anterior;
            return;
        }

        removeFim(atual, atual.prox);
    }

    void removeNInicio(int chave) {
        if (size() == 1) {
            removeInicio();
            return;
        }

        removeNInicio(null, primeiro, chave);
    }

    private void removeNInicio(Node anterior, Node atual, int chave) {
        for (int i = 0; i <= chave; i++) {
            atual = atual.prox;
            removeNInicio(atual, atual.prox, chave);
        }   
    }

    void imprime() {
        imprime(primeiro);
    }

    void imprime_invertido() {
        imprime_invertido(primeiro);
    }

    void imprime_invertido(Node x) {

    }

    private void imprime(Node x) {
        if (x == null) {
            return;
        }

        System.out.println(x.chave);
        imprime(x.prox);
    }

    Node metade() {
        int m = N / 2;
        return metade(primeiro, m);
    }

    Node metade(Node x, int m) {
        if (m == 0) {
            return x;
        }

        return metade(x.prox, m - 1);
    }

    boolean isEmpty() {
        return primeiro == null;
    }

    int size() {
        return N;
    }

}

Testa Lista:

class TestaLista {

    public static void main(String[] args) {

        Lista lista = new Lista();

        lista.addEmOrdem(1);
        lista.addEmOrdem(5);
        lista.addEmOrdem(2);
        lista.addEmOrdem(3);
        lista.addEmOrdem(4);

        lista.imprime(); 
    }

}

Node :

class Node {

    int chave;
    Node prox;
    Node ant;

    Node(int chave) {
        this.chave = chave;
    }

}

I believe the error is in recursion, but I’m not able to fix!

java recursion chain-list

  • The entire code does not, but provide a [mcve] is yes, necessary.

  • @Articuno put an example of recursive function "removeFim()" that is working, I think it is necessary, if it is not, let me know

  • No, see the link I sent. It teaches how to create a relevant code, where it is possible to test.

  • 1

    If I copy your code to my Eclipse, Netbeans or something, does it compile? No. It is simple and trivial to touch something (for example, imports) why does it Compile? No. So your example is not minimal, complete and verifiable because it fails the "full" and "verifiable" part. Important parts of the code are missing to characterize the problem. Thus, it is extremely difficult to give a satisfactory answer to the question.

  • @Victorstafusa ready, I preferred to put the whole code to be easier to understand the functions and also to be able to compile!!

  • I still can’t compile because I don’t have the class Node.

  • @Victorstafusa vdd, I’ll add

Show 2 more comments

1 answer

3


The problem is you missed one return at the end of if of addFimRecursivo:

private void addFimRecursivo(Node anterior, Node atual, int chave) {
    if(atual.prox == null) {
        Node novo = new Node(chave);
        ultimo.prox = novo;
        ultimo = novo;
        N++;
        return; // Faltou isso daqui.
    }

    addFimRecursivo(atual, atual.prox, chave);

}

However, I make a few more suggestions:

  • Note that the parameter anterior in the method addFimRecursivo is never used and therefore you can eliminate it easily.

  • Move some methods into the class Node would make the code simpler.

  • Don’t forget to use the modifiers public and private.

  • Use N as list size is not a good variable name and goes against code conventions. Prefer tamanho.

  • Thank you very much, especially for the patience, I’m still learning to use the platform.

Browser other questions tagged java recursion chain-list

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