[Resolvido] Listas Ligadas

[AJBM]

Boas!

Eu tenho que fazer este exercício

Este primeiro exercício consiste na criação de uma listalig ada (LinkedList). A lista ligada deverá possuir as seguintes operações:Add e Remove

Para que seja possível verificar a integridade da lista ligada crie uma função que imprima todos os elementos da lista.

Eu já tenho aqui o código mas não sei se é a maneira mais correcta de fazer, queria saber a vossa opinião

public class ListaLigada {

private String name;
private ListaLigada next;
public ListaLigada(String name, ListaLigada next) {
    this.name = name;
    this.next = next;
}
public ListaLigada(String name) {
    this.name = name;
}
public String getName() {
    return name;
}
public void setName(String name) {
    this.name = name;
}
public ListaLigada getNext() {
    return next;
}
public void setNext(ListaLigada next) {
    this.next = next;
}
@Override
public String toString() {
    return "ListaLigada{" + "name=" + name + ", next=" + next + '}';
}



}

public class ConjListaLigada {

private List<ListaLigada> lista= new ArrayList<ListaLigada>();
public ConjListaLigada() {
}

boolean add(ListaLigada l){


    return l!=null && lista.add(l);
}


void remove(int posicao){

    posicao-=1;

    lista.remove(index);
}

String imprimir(){
    String dados="";

    for (int i = 0; i < lista.size(); i++) {
        dados=dados+lista.get(i)+"\n";
    }
    return dados;
}

}

public class ED_Ficha2_Parte1_ex1 {
/**
    * @param args the command line arguments
    */
public static void main(String[] args) {

    ConjListaLigada lista= new ConjListaLigada();

    lista.add(new ListaLigada("Pedro", new ListaLigada("Rita")));
    lista.add(new ListaLigada("Rui", new ListaLigada("Maria", new ListaLigada("Luis"))));
    System.out.println(""+
    lista.imprimir());

}
}

[HappyHippyHippo]

o objectivo do programa é não usar o List e seus derivados, e aprenderes a estrutura de lista ligada, logo está mal resolvido.

[AJBM]

Boas!

Podes dar-me uma dica do que fazer, por exemplo: o método adicionar tenho que ser eu mesmo a criar o codigo?

[SteveWorks]

Bom dia!

Quando tens pela frente um problema de programação, primeiro tens de parar para pensar e só depois é que te atiras ao Java.

Neste caso deves questionar-te sobre o seguinte: O que é uma lista ligada?

Rapidamente chegas à conclusão que é um agregado de Nós. Então é isso que tens de implementar: uma classe que represente um Nó.

Agora surge outra questão: O que é que esta classe necessita ter?

Tal como tu fizeste (e bem), necessita ter o seu valor e uma referência para o próximo Nó.

O teu problema recai na forma como interpretar esta tua implementação. Se te pedem para implementares tu uma lista, certamente não poderás utilizar a API referente a listas. Tens é que descobrir como funcionar com os nós que tu criaste. As acções principais recaem sobre as acções Add e Remove. Vejamos então:

- Independentemente do tamanho actual da lista, na operação Add tu necessitas saber qual o teu último nó, portanto concluis que vais ter sempre uma referência para o ultimo nó da lista e que ao efectuares esta operação, esse objecto vai ter de ser alterado.

- Na operação Remove, dada a posição, tens de percorrer a lista desde o início. Portanto concluis também que necessitas ter sempre uma referência para o início da lista.

Para percorrer a lista é só andar de "next" em "next".

Só um pequeno conselho: tem atenção aos nomes que utilizas. Nessa tua implementação, ao teres "List<ListaLigada>" aparenta que tens uma lista de listas, o que é mentira. Não se trata de uma questão de implementação, mas sim de brio no trabalho e no código.

Espero ter ajudado e boa sorte!

[AJBM]

Boas!!

Podes ver se é mais ao menos isto eu tive a pesquisar um bocado sobre o assunto, mas nao tenho a certeza se é assim que se faz

public class ListaLigada {


String elemento;
ListaLigada next;
public ListaLigada(String el) {
    this.elemento=el;
    next=null;

}




}

public class ConjListaLigada {

private ListaLigada first, last;
private int nelementos;
public ConjListaLigada() {
    first = null;
    last = null;
    nelementos = 0;
}
void add(String l) {

    nelementos++;
    ListaLigada nova = new ListaLigada(l);
    if (first == null && last == null) {

        last = nova;

    } else {

        nova.next = first;
        last.next=first;
        first = nova;
    }

}

public static void main(String[] args) {
    ConjListaLigada lista = new ConjListaLigada();
    lista.add("Pedro");
    lista.add("Rui");
    lista.add("Joao");

    System.out.println(""
            + lista.imprimir());
}

[HappyHippyHippo]

já tentaste compilar isso ?

[AJBM]

Sim e funciona, agora não sei se a implementação é a mais correcta

[HappyHippyHippo]

isto funciona ??

System.out.println(lista.imprimir());

estou maravilhado pelos poderes adivinhos do Java ...

[AJBM]

public class ConjListaLigada {

private ListaLigada first, last;
private int nelementos;
public ConjListaLigada() {
    first = null;
    last = null;
    nelementos = 0;
}
void add(String l) {

    nelementos++;
    ListaLigada nova = new ListaLigada(l);
    if (first == null && last == null) {

        last = nova;

    } else {

        nova.next = first;
        last.next=first;
        first = nova;
    }

}
// void remove(String el) {
//
//     if(nelementos==0){
//         System.out.println("nada para remover:");
//     }
//     else{
//    
//        
//     }
//
// }
String imprimir() {
    String dados = "";




        dados=dados+last.elemento+" "+last.next.elemento+" "+first.elemento;


    return dados;
}
}

lool eu tenho esse método na class, eu não coloquei porque a minha duvida estava no método de adicionar. Mas a implementação esta correcta?

[HappyHippyHippo]

a resposta é muito simples : não

pega num papel e verifica que valor tem cada elemento inserido na lista (texto e ponteiro para próximo) em cada passo da inserção para todas as inserções que fazes.

[AJBM]

Eu fiz o que disseste e parece funcionar bem agora

public class ConjListaLigada {

private ListaLigada first, last;
private int nelementos;

public ConjListaLigada() {
first = null;
last = null;
nelementos = 0;

}

void add(String l) {


nelementos++;

ListaLigada nova = new ListaLigada(l);

if (first == null && last == null) {


last = nova;


} else {

if (nelementos == 2) {


nova.next = null;
first = nova;
last.next=first;


}
else {

first.next = nova;
first = nova;

}



}


}

// void remove(String el) {
//
// if(nelementos==0){
// System.out.println("nada para remover:");
// }
// else{
//
//
// }
//
// }
String imprimir() {
String dados = "";
int cont = 0;
System.out.println("O ultimo elemento e: "+last.elemento+"\n O Ultimo elemento"
+ " esta apontar para: "+last.next.elemento+"\nO Penultimo elemento esta apontar: "+last.next.next.elemento+"\nO primeiro elemento é: "+last.next.next.next.elemento);




return dados;
}
}

public static void main(String[] args) {
       ConjListaLigada lista = new ConjListaLigada();
       lista.add("Pedro");
       lista.add("Rui");
       lista.add("Joao");
       lista.add("Antonio");
       System.out.println(""
               + lista.imprimir());
   }

O output foi este :

O ultimo elemento e: Pedro

O Ultimo elemento esta apontar para: Rui

O Penultimo elemento esta apontar: Joao

O primeiro elemento é: Antonio

[HappyHippyHippo]

corre este código :

public static void main(String[] args) {
 ConjListaLigada lista = new ConjListaLigada();

 for (int i = 0; i < 100; i++)
 {
   lista.add("Pessoa "+Integer(i).toString());
 }

 System.out.println(lista.imprimir());
}

[AJBM]

Ja corri, eu alterei o lista.add("Pessoa "+Integer(i).toString) para lista.add("Pessoa "+Integer.toString(i)) porque estava a dar me erro e assim ja não da.

E tive este output:

O ultimo elemento e: Pessoa 0

O Ultimo elemento esta apontar para: Pessoa 1

O Penultimo elemento esta apontar: Pessoa 2

O primeiro elemento é: Pessoa 3

Como eu queria adicionar a cabeça parece me que esta certo

Edited October 8, 2012 at 10:45 AM by AJBM

[HappyHippyHippo]

ora bem ... o código parece dar um resultado correcto mas existe soluções mais eficientes

no entanto deixa ca ver como fica a tua lista

last                       first
|                          |
V                          V
pessoa1->pessoa2->pessoa3->pessoa4->

agora imagina que quero listar, é obvio que quero começar a listar pelo início, pelo primeiro em ontras palavras ...

conclusão:

void add(String l)
{
 ListaLigada novo = new ListaLigada(l); // criar o nó da lista (nó da lista, não uma lista como estás a chamar)

 if (nelementos == 0) // verificar se a lista se encontra vazia
 {
   first = novo; // apontar para o nó criado
   last = novo;  // apontar para o nó criado
 }
 else
 {
   last->next = novo; // guardar no elemento "next" do último nó guardado o ponteiro para o novo nó
   last = novo;       // alterar o ponteiro para o último elemento para o novo nó criado/guardado
 }

 nelementos++; // só incrementar no fim (após a inserção na lista)
}

vejamos ent

ao o que acontece quando adicionas elementos:

Lista vazia:
first last
|     |
V     V

Lista com um elemento:
first last
|     |
V     V
pessoa1

Lista com duas pessoas:
first    last
|        |
V        V
pessoa1->pessoa2

Lista com tres pessoas:
first             last
|                 |
V                 V
pessoa1->pessoa2->pessoa3

vê agora como se faz a impressão usando correctamente a iteração dos elementos guardados

String imprimir()
{
 String resultado = ""; // string que guardará o resultado da listagem, se bem que podias enviar directamente para o output

 ListaLigada iter = first; // como vês, começar é pelo início ...

 while (iter != NULL) // entrar num ciclo enquanto estivermos a apontar para um nó válido
 {
   resultado += "Pessoa : "+iter.elemento+"\n"; // apresentar o nome guardado no nó
   iter = iter.next; // avançar com a iteração (apontar para o próximo)
 }

 return resultado; // devolver a string criada
}

[AJBM]

Ok Obrigado pela tua ajuda 👍