Problem due to add at the end of a Simple Chained List

0

I have a simple linked list and need to do a recursive function that adds at the end of the list an element, I already have the function without recursion, but the one with recursion is giving error. Here is the code and 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;
    }

}

Test List:

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 think the error is in recursion, but I can not fix it!

    
asked by anonymous 10.09.2018 / 19:11

1 answer

3

The problem is that you forgot 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, here are some more suggestions:

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

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

  • Do not forget to use the public and private modifiers.

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

10.09.2018 / 20:25