Chained JAVA Lists

Asked

Viewed 2,618 times

2

How to invert a simple chained list in Java? For example, I have the following values: 3 - 2 - 1 and the end result will have to be 1 - 2 - 3.

Note: no use of native Java functions such as Arraylist.

public void inverteLista() {
    Lista atual = new Lista();
    atual.setProx(primeiro);
    for (int i = 0; i < tamanho; i++) {
        atual = atual.getProx();
        System.out.println(atual.getValor());
    }
}

This code prints the list in normal order, however I do not know which logic used to reverse it.

java

  • take a read on Bubble Sort, then apply to java, there are examples ready in java on netna net. this is the easiest but not very efficient method for large lists.

  • How is the algorithm and structure of the simple chained list? The inversion implementation may be dependent on this.

  • 1

    If in the original list the next of A is B, in the inverted list the next of B is A. If in the original list the next of the last is null, in the inverted list the next of the first is null. Based on this, you can invert it with a single pass (but the code is different if you want to modify the original list or if you want a new list - let us know if you need help with that). By the way, why are you doing Lista atual = new Lista(); atual.setProx(primeiro);? Why not just Lista atual = primeiro;, and pass the atual = atual.getProx() for the end of the loop?

  • @mgibsonbr thanks for the explanation and the tip about the list, I had not thinking about this logic and I ended up doing by the longest method, I will update the code.

1 answer

2


It’s very simple, just create a recursive function that traverses the list elements where the recursive call happens before printing the elements:

public void imprimeContrario(Lista l) {
  //verifica se o nó é nulo
  if (l!=null){

      // Se não for, não é o final da lista, então faça uma chamada recursiva
      // passando o próximo elemento como parâmetro
      imprimeContrario(l.getProximo());

      // imprime o elemento após a chamada recursiva ter sido completada
      System.out.println(l.getInfo());
    }
}

Example of code execution:

List: [1] -> [2] -> [3] -> [null]

Thus, when we pass [1] to the function, the following iterations will take place:

printContrario([1])
printContrario([2])
printContrario([3])
printContrario([null])
System.ou.println([3])
System.ou.println([2])
System.ou.println([1])

Output: 3 2 1

  • Creating in another method a new list with the values and passing as parameter to the method printContrario(), it returns the same order of the list, ie 1 2 3.

Browser other questions tagged java

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