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!