Listas Encadeadas

Programação Java
#1

Estou com uma grande duvida na implementação de uma lista.
A duvida é seguinte

public class No{
public int chave;
public No prox;
}

public class Lista{
private No prim;
private No ult;

public Lista(){
prim = null;
ult = null;
}

public void inserir(No item){
if(prim == null){
prim = item;
ult = item;
}
else{
ult.prox = item; //Não entendi essa linha de comando com ele cria outro no sendo que prox do atributo da
classe do tipo No;
ult = item;
}
}

public void imprimir(){
No aux = prim;
while(aux != null){
System.out.println(aux.chave);
aux = aux.prox; // Não entendi como o aux avança para o proximo.
}
}

Não entendi como o proximo criando e avançando mais um.Ficarei grato se alguem puder sanar essa minha duvida. agradeço desde ja

#2

O que você não entendeu?

Outra coisa, formate o seu código seguindo as dicas abaixo:
http://www.guj.com.br/posts/list/50115.java

Senão fica difícil de ler… :wink:

#3

poste seu codigo entre CODE

fica mais facil lhe ajudar

#4

[quote=wanderson.si]Estou com uma grande duvida na implementação de uma lista.
A duvida é seguinte

public class No{
  public int chave;
  public No prox;
}

public class Lista{
  private No prim;
  private No ult;
  
   public Lista(){
     prim = null;
     ult    = null;
   }

  public void inserir(No item){
     if(prim == null){
       prim = item;
       ult = item;
     }
     else{
       ult.prox = item;
       ult = item;
     } 
  }

  public void imprimir(){
    No aux = prim;
    while(aux != null){
       System.out.println(aux.chave);
       aux = aux.prox; 
    }   
 }

Não entendi como o prox criando e avançando mais um.Ficarei grato se alguem puder sanar essa minha duvida. agradeço desde ja
[/quote]

#5

Não entendi o prox na linha 21 e 30
na linha 21 ele cria mais um no, a minha duvida como ele cria mais um no sendo que ele é somente um atributo
do tipo No.

na linha 30 como ele avança mais um???

estou com um verdadeiro no na cabeça com esta lista…rsrs

#6

Na linha 21 você associa o nó recebido no parâmetro a lista.

Veja o que está escrito ali. O “último nó da lista agora terá um próximo nó, que é o recebido pelo parâmetro”. Na linha debaixo daí vc diz. “Portanto, o último nó agora é esse recebido.”.

Na linha 30, seu programa diz:
“A variável auxiliar, deve conter o valor do próximo nó”. Ou seja, o valor da variável auxiliar, se antes era o do primeiro nó, passará para o segundo nó. Chamando essa linha novamente, o valor passará do segundo nó, para o próximo nó (terceiro nó). E assim por diante.

#7

[quote=ViniGodoy]Na linha 21 você associa o nó recebido no parâmetro a lista.

Veja o que está escrito ali. O “último nó da lista agora terá um próximo nó, que é o recebido pelo parâmetro”. Na linha debaixo daí vc diz. “Portanto, o último nó agora é esse recebido.”.

Na linha 30, seu programa diz:
“A variável auxiliar, deve conter o valor do próximo nó”. Ou seja, o valor da variável auxiliar, se antes era o do primeiro nó, passará para o segundo nó. Chamando essa linha novamente, o valor passará do segundo nó, para o próximo nó (terceiro nó). E assim por diante.
[/quote]

Completando o que o Vini falou.

No método Inserir, você recebe um Nó pra inserir na sua Lista, certo?
Caso a Lista já contenha Nós, você deverá inserí-lo na ÚLTIMA POSIÇÃO da Lista.
Então, você faz seu último Nó (Referenciado por Ult), apontar para o novo Nó(item) que você recebeu como argumento, como na linha abaixo.

ult.prox = item;

Neste momento, a referência ult já não “aponta” mais para o último Nó da Lista(item), mas para o penúltimo. O último passo é fazer ult referenciar o novo ultimo Nó (item) da sua Lista.
ult sempre deverá aponta para o útlimo Nó da Lista!!!

ult = item;

Na linha anterior, foi atualizado a referência ult, que agora “aponta” corretamente para o novo útlimo Nó (item) da sua Lista.
Quando você for inserir outro Nó, isto se repetirá.
Uma forma de você entender melhor é desenhar, fica bem mais claro.

Espero ter ajudado!

#8

Vlw galera…conseguir entender o inserir mais, continuo com duvida na linha 30…entendi o seguinte, toda vez que eu chamo a linha e passa a referencia o proximo no, mais a maior duvida é como isso acontece??? vou usar como exemplo um contador de inteiros, quando eu quero avançar mais um no contador é so eu incrementar ele que passa a ter mais um certo, seria uma coisa semelhante q aconteceira com a variavel auxiliar mais não conseguir exergar até agora como isso acontece???

grato

#9

[quote=wanderson.si]Vlw galera…conseguir entender o inserir mais, continuo com duvida na linha 30…entendi o seguinte, toda vez que eu chamo a linha e passa a referencia o proximo no, mais a maior duvida é como isso acontece??? vou usar como exemplo um contador de inteiros, quando eu quero avançar mais um no contador é so eu incrementar ele que passa a ter mais um certo, seria uma coisa semelhante q aconteceira com a variavel auxiliar mais não conseguir exergar até agora como isso acontece???

grato[/quote]

Wanderson, no princípio é mesmo complicado de entender. :smiley:

Você tem um método imprimir, que deverá imprimir todos os valores da chave de sua Lista, correto?
Então começamos pelo primeiro Nó.

No aux = prim; //variável local aux recebe referência //ao primeiro Nó da Lista

Pelo que entendi, você não está conseguindo entender como é possível “andar” pela lista, sem realizarmos um incremento do tipo

i = i + 1;

Acho que você está associando Lista com vetores, é isso?
No vetor, realmente pra acessar o próximo elemento é necessário fazer incrementos.
Mas acontece que na Lista, o que você está acessando na verdade são posições de MEMÓRIA, então não é possível incrementarmos uma determinada posição X(Elemento atual) da memória com X + 1 (Próximo elemento). Como você garante que o próximo elemento está na posição X + 1?
Na verdade, sempre temos que perguntar para o elemento atual, qual a posição de memória em que se encontra o próximo elemento da Lista, até que ele seja NULL que será o final da Lista.

aux = aux.prox;

Na linha anterior, aux está simplesmente recebendo a referência para o próximo elemento da Lista.
Se aux for Null, paramos de imprimir, senão imprime a chave.
Como sabemos que aux.prox é o próximo elemento da Lista?
Quando você utilizou o método insere(), você quardou essa a posição do próximo, lembra?

ult.prox = item;

Isto é exatamente a posição do elemento seguinte, que neste caso era o útimo, mas com novas inserções passou a ser o penúltimo, anti-penúltimo e por ai vai… :lol:

Não sei se fui claro, mas tentei ser.

Abraço.

#10

Olá galera,

Esse código me lembra muito ling. C, rsrs, pergunto eu, não seria mais fácil fazer isso com Array List ???, dê uma consultada na documentação da Sun sobre array list, vai facilitar 99% do seu entendimento e seu código estará muito mais limpo, mas de resto é igual que o rmalati e o vinigodoy disseram, mas lembre-se que o Java veio para facilitar a nossa vida, principalmente as API’s que ele disponibiliza para a gente, flw, abraço …

Generosamente,

Frid

#11

É o Frid tem razão!
Mas eu acho que pra entender estrutura de dados, não é permitido utilizar as facilidades de Java na faculdade.
Pelo menos, quando eu aprendi isso não era permitido.

Abraço.

#12

Frid, a estrutura de dados que ele está implementando é o LinkedList, não o ArrayList. O ArrayList baseia-se em Vector e o LinkedList em uma lista encadeada.

Mas com certeza, ele está aprendendo Estrutura de Dados, e por isso, vai ter que sofrer fazendo isso no braço.

#13

[quote=ViniGodoy]Frid, a estrutura de dados que ele está implementando é o LinkedList, não o ArrayList. O ArrayList baseia-se em Vector e o LinkedList em uma lista encadeada.

Mas com certeza, ele está aprendendo Estrutura de Dados, e por isso, vai ter que sofrer fazendo isso no braço.[/quote]

Mas é só assim pra aprender né Vini :lol:

#14

Olá galera,

Eu sei que é LinkedList que ele está implementando, eu só dei uma sugestão de uma alternativa mais simples, mas como é para a facul, vai ter que sofrer mesmo, rsrsrs, tive que aprender isso em C, 10 vezes pior, ainda bem que isso é passado, rsrs, mas é isso mesmo, como é para fins acadêmicos, boa sorte e muita pesquisa que vc consegue, no que eu poder ajudar pode contar, abraços …

Generosamente,

Frid

#15

hauhaua, C é manipulação de ponteiros na veia!!!
eu tb sofri.

#16

Em C++ o código fica quase igual em Java.

E pra quem não vai fazer no braço, dá também para usar as classes vector (equiv. ao ArrayList) ou list (equiv. ao LinkedList), ambos da Standard Library (namespace std).

#17

Sem for fazer em C, a dica é: Desenhe a estrutura e os ponteiros. Fica simples para simular o algoritmo.

#18

bom comerçei a entender,so q me confundi novamente no metodo inserir
rmalati daria para vc explicar melhor esse trecho:

Neste momento, a referência ult já não “aponta” mais para o último Nó da Lista(item), mas para o penúltimo. O último passo é fazer ult referenciar o novo ultimo Nó (item) da sua Lista.

???

 utl.prox = item; 
 utl = item;

na linha 1 esta dizendo que o proximo no da liste sera item, e na 2 ele atualizar o utl no para item isso??? agora nao consigo enxergar onde ele refenrencia utl.prox como null?

frid,
nao posso usar arraylist ou outra api,estou estudando para prova da faculdade,vai cair os tipos abstratos de dados pilha, fila e lista e to garrado legal em lista…vlw galera ai pela ajuda

#19

ViniGodoy,
quando você fala que o ultimo nó da lista terá um próximo,


if(prim == null){
  prim = item;
  ult = item;
}

você está falando que a linha 4 terá um próximo que sera o parametro recebido???

grato

#20

[quote=wanderson.si]bom comerçei a entender,so q me confundi novamente no metodo inserir
rmalati daria para vc explicar melhor esse trecho:

Neste momento, a referência ult já não “aponta” mais para o último Nó da Lista(item), mas para o penúltimo. O último passo é fazer ult referenciar o novo ultimo Nó (item) da sua Lista.

???

 utl.prox = item; 
 utl = item;

na linha 1 esta dizendo que o proximo no da liste sera item, e na 2 ele atualizar o utl no para item isso??? agora nao consigo enxergar onde ele refenrencia utl.prox como null?

frid,
nao posso usar arraylist ou outra api,estou estudando para prova da faculdade,vai cair os tipos abstratos de dados pilha, fila e lista e to garrado legal em lista…vlw galera ai pela ajuda
[/quote]

Wanderson, acho que entendi a sua dúvida.

utl.prox = item;

A linha anterior, faz o último NÓ apontar para o novo Último NÓ (item), ok?

utl = item;

Na linha anterior, o atributo da classe Lista (utl) que sempre referenciará o último elemento da Lista, deve agora referênciar o novo último NÓ que acabamos de inserir (item). item é agora nosso último NÓ da Lista, ok?

A classe NÓ, tem dois atributos (int chave, No prox), certo?
Quando você cria um novo objeto NÓ, os atributos(int chave, No prox) são inicializados com seus respectivos valores default. Esses valores são atribuídos implicitamente, quando você cria um novo objeto NÓ.
O compilador faz implicitamente assim:

chave = 0; //valor default para inteiros prox = null; //valor default para referências a objetos (prox é do tipo No)
Então, sempre que inserir um novo NÓ na sua lista, a referência desse novo NÓ(item) ao próximo elemento é sempre null, até o você inserir um novo NÓ, na Lista!!!

utl.prox = null;

Sempre o último NÓ deverá referenciar null.
Quando você percorrer o método imprime(), chegará no último NÓ inserido e verificará se seu atributo prox referencia um valor nulo, isso indica que chegamos ao fim da Lista!!!

while(aux != null){ //É checado se estamos no último NÓ da Lista, senão imprimimos a chave! System.out.println(aux.chave); aux = aux.prox; // se aux.prox é null, indica que chegamos ao final da Lista }

Ajudou a clarear ou ainda tá nebuloso? :?:

Abraço