Implement and perform joint operations on chain lists

Question

Could someone help me implement a chained list to perform set operations? Without using native Java functions such as ArrayList.

The algorithm already generates a chained list and adds new nodes, but how do I make an operation like the union?

In the Main, I am instantiating two classes, each one would be a list with values, but what do I call a union function that takes as a parameter these two lists and how to go through them simultaneously? (I know how to go one at a time)

Code - Main

public class TrabalhoListas {

public static void main(String[] args) {
    ListaDinamica teste = new ListaDinamica();
    ListaDinamica teste2 = new ListaDinamica();
    teste.add(1);
    teste.add(2);
    teste.add(3);
    teste.imprimeLista();
    System.out.println("Segunda lista");
    teste2.add(1);
    teste2.add(6);
    teste2.add(3);
    teste2.imprimeLista();
    System.out.println("Primeira de novo");
    teste.imprimeLista();
}
}

--- List ---

public class Lista {

private int valor;
private Lista prox;

public Lista() {
}

public int getValor() {
    return valor;
}

public void setValor(int valor) {
    this.valor = valor;
}

public Lista getProx() {
    return prox;
}

public void setProx(Lista prox) {
    this.prox = prox;
}
}

Lista Dinâmica

public class ListaDinamica {

Lista primeiro;
Lista ultimo;
int tamanho = 0;

public ListaDinamica() {
    primeiro = null;
    ultimo = primeiro;
}

public void add(int valor) {
    Lista novo = new Lista();
    novo.setValor(valor);
    tamanho++;
    if (primeiro == null) {
        primeiro = novo;
        ultimo = novo;
        novo.setProx(null);
    } else {
        novo.setProx(primeiro);
        primeiro = novo;
    }
}

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

public void uniao(){

}
}

Answer 1

To make the union between two lists, just go through the list 1 until the last "valid element"( !=null) and add to list 2 as next to this element.

public static void uniaoLista(Lista l1, Lista l2){

    //Lista auxiliar que vai percorrer a lista 1
    Lista lAux = l1;


    //Percorre a lista l1 até chegar ao ultimo "elemento válido", ou seja, != de null
    while(lAux.getProx()!=null){

        lAux = lAux.getProx();
    }

    //Quando este elemento é achado, dizemos que seu próximo elemento será a lista l2
    lAux.prox = l2;
}

Thus, you would not need to create a class "Dynamic List", it would be enough to have a List object that receives the first list and then make the union between this list and another one. Example:

Suppose the lists:

List L1 = 1->2->3->4

List L2 = 5->6->7->8

To perform the union without ending the list L1, once the objects are passed by reference, do:

...
Lista lUniao = l1.clone();
uniaoLista(lUniao,l2);

//lUniao = 1->2->3->4->5->6->7->8

Answer 2

I think that would be it, that simply modifies a ListaDinamica concatenating in her another ListaDinamica:

public void uniao(ListaDinamica outraLista) {
    ultimo.setProx(outraLista.primeiro);
    ultimo = outraLista.ultimo;
    tamanho += outraLista.tamanho;
    removeDuplicatas();
}

And to remove duplicates, you end up going through the same list twice, one inside the other:

private void removeDuplicatas() {
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        for (Lista b = a.getProx(); b != null; b = b.getProx()) {
            if (a.getValor() == b.getValor()) {
                a.setProx(b.getProx());
                tamanho--;
            }
        }
    }
}

This algorithm to remove duplicates is not very efficient (it has quadratic time complexity), but it should work properly and should serve its purposes. Figuring out an efficient algorithm for this would be much more complicated, and in this case it would be better to use the classes that java already gives you (such as HashSet or TreeSet).

You should also place a call to removeDuplicatas() at the end of the method add(int). Or create a search method and use it in the method add(int) to avoid adding an existing element.

And then, you use this method at the end of the method main:

teste.uniao(teste2);
teste.imprimeLista();

If you prefer to join without modifying either list, then the best approach is to follow the of my other answer.

Answer 3

You can add a method to find out if an element exists in ListaDinamica:

public boolean existe(int elemento) {
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        if (a.getValor() == elemento) return true;
    }
    return false;
}

Modify the method add(int) not to add duplicates:

public void add(int valor) {
    if (existe(valor)) return; // Não deixa adicionar duplicatas.
    Lista novo = new Lista();
    novo.setValor(valor);
    tamanho++;
    if (primeiro == null) {
        primeiro = novo;
        ultimo = novo;
        novo.setProx(null);
    } else {
        novo.setProx(primeiro);
        primeiro = novo;
    }
}

And in the union, just add all the elements of the other list:

public void uniao(ListaDinamica outraLista) {
    for (Lista a = outraLista.primeiro; a != null; a = a.getProx()) {
        add(a.getValor());
    }
}

And then, you use this method at the end of the method main:

teste.uniao(teste2);
teste.imprimeLista();

Maybe you don’t like the fact of the method uniao modify the list. If this is the case, and you actually want to create a new list without modifying either one, then do this:

public ListaDinamica uniao(ListaDinamica outraLista) {
    ListaDinamica novaLista = new ListaDinamica();
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        novaLista.add(a.getValor());
    }
    for (Lista a = outraLista.primeiro; a != null; a = a.getProx()) {
        novaLista.add(a.getValor());
    }
    return novaLista;
}

And then in your method main:

ListaDinamica teste3 = teste.uniao(teste2);
teste3.imprimeLista();