0

Tenho uma lista encadeada simples e preciso fazer uma função recursiva que adiciona no fim da lista um elemento, já tenho a função sem recursividade, mas a com recursividade está dando erro. Segue o código e o erro:

Função sem recursividade:

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

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

Função com recursividade:

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

    }

Erro:

Exception in thread "main" java.lang.NullPointerException

Lista:

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

}

Creio que o erro seja na recursão, mas não estou conseguindo arrumar!

7
  • O código inteiro não, mas fornecer um Exemplo Mínimo, Completo e Verificável é sim, necessário.
    – user28595
    10/09/2018 às 17:37
  • @Articuno coloquei um exemplo de função recursiva "removeFim()" que está funcionando, creio que seja o necessário, se não for, me avise 10/09/2018 às 17:47
  • Não é, veja o link que mandei. Nele ensina como criar um código relevante, onde seja possivel testar.
    – user28595
    10/09/2018 às 17:52
  • 1
    Se eu copiar o seu código para o meu Eclipse, Netbeans ou outra coisa parecida, ele compila? Não. É simples e trivial mexer em alguma coisa (como por exemplo, imports) para que ele compile? Não. Então o seu exemplo não é mínimo, completo e verificável porque ele falha na parte do "completo" e do "verificável". Faltam partes importantes do código para caracterizar o problema. Dessa forma, fica extremamente difícil dar alguma resposta satisfatória à pergunta. 10/09/2018 às 18:00
  • @VictorStafusa pronto, preferi colocar o código inteiro para ficar mais fácil de entender as funções e também para conseguir compilar!! 10/09/2018 às 18:07

1 Resposta 1

3

O problema é que você esqueceu um return no final do if do 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);

}

No entanto, faço mais algumas sugestões:

  • Observe que o parâmetro anterior no método addFimRecursivo nunca é usado e portanto você pode eliminá-lo facilmente.

  • Mover alguns métodos para dentro da classe Node deixaria o código mais simples.

  • Não se esqueça de usar os modificadores public e private.

  • Usar N como tamanho da lista não é um bom nome de variável e vai contra as convenções do código. Prefira tamanho.

1
  • Muito obrigado, principalmente pela paciência, ainda estou aprendendo a usar a plataforma. 10/09/2018 às 20:49

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 .