Ajuda com lista dinâmica/ encadeada

4 de junho de 2017 3 respostas

lucas_panizio 4 de junho de 2017

Olá Pessoal,
Estou com uma dificuldade cruel, no que diz respeito a um método java. Para delimitar a posição do node, só tenho o método getProximo() conforme segue abaixo, portanto, não consigo excluir o node passado como parâmetro, sem excluir todos os consecutivos.

package br.edu.unifil.comp2022.listadinamica;
/**

Write a description of class ListaDinamica here.
@author (your name)

@version (a version number or a date)

*/

public class ListaDinamica{

private Node inicio;

private Node aux;

private int _tamanho = 0;

public ListaDinamica(){

}

public void inserir(Node node){

if(inicio == null){

inicio = node;

}else{

Node aux = inicio;

while(aux.getProximo() != null){

aux = aux.getProximo();

}

aux.setProximo(node);

}

aux = inicio;

}

public void remover(Node node){

if(aux != node){

while(aux.getProximo() != null && aux.getProximo() != node){

aux = aux.getProximo();

}

}else{

aux = null;

}

aux = inicio;

}

public boolean existe(Node node){

if(aux == null){

return false;

}else if(aux == node){

return true;

}else if(aux.getProximo() != null){

aux = aux.getProximo();

return existe(aux);

}

aux = inicio;

return false;

}

public int tamanho(){

Node aux = inicio;

while(aux != null){

aux = aux.getProximo();

_tamanho++;

}

return _tamanho;

}

<a class="mention" href="/u/override">@Override</a>

public String toString(){

String ret;

if(inicio == null){

ret = “[]”;

}else{

ret = “[”;

Node aux = inicio;

while(aux.getProximo() != null){

ret = ret + aux + ", ";

aux = aux.getProximo();

}

}

ret = ret + “]”;

return ret;

}

}

3 Respostas

TerraSkilll 4 de jun. de 2017

Consegue sim.

Um exemplo: dada a seguinte lista:

[1]->[2]->[3]->[4]->[5]->[null]

O método getProximo() no nó [1] retorna o nó [2]
O método getProximo() no nó [2] retorna o nó [3]

E assim por diante. Isso nos permite percorrer a lista, até o próximo ser null, certo? Então, como remover um nó? O nó [3], por exemplo?

Para isso, precisamos que, depois do nó [2], venha o nó [4]. Ou seja, o próximo nó do nó [2] será o [4], não mais o [3] . Então a ideia é pegar o próximo nó do do que queremos remover e tornarmos esse nó o próximo do que antecede o que queremos remover.

Os nós em questão são:

nó que queremos remover: [3];
antecessor: [2];
próximo: [4];

O truque é fazer isso ao percorrer a lista, mas no momento em que chegarmos ao nó antecessor ([2]), não quando chegarmos ao nó que queremos remover (pois quando estamos no nó [3], não temos como acessar o antecessor, só o próximo). Então você percorre a lista comparando o nó a ser removido com o próximo nó, não o corrente. Algo assim:

public void remover(Node node){
  Node aux = inicio;
  while (aux.getProximo() != node) do{ // se o próximo for o nó a ser removido, paramos, pois estamos no antecessor que queremos
    aux =aux.getProximo();
  }

  //aqui pegamos o próximo do nó a ser removido e o tornamos o próximo do nó antecessor
  aux.setProximo( node.getProximo() );
  //outra forma de escrever isso é:
  aux.setProximo(aux.getProximo().getProximo()); // pega o próximo do próximo
  // deixe somente uma das opções, não as duas
}

Obs: o código foi simplificado para entendimento. Podem ser necessários alguns ajustes, como ajustar o nó de início (se removermos o nó [1], o início precisa mudar).

Abraço.

lucas_panizio 4 de jun. de 2017 1 like

Boa tarde, muito obrigado pela resposta, porém, acredito que a intenção do exercício é deixar [2] = null quando houve [1] e [3] envolta, mantendo-os intactos.

TerraSkilll 4 de jun. de 2017

Não entendi bem. No meu código, a substituição do próximo do nó anterior ao que será removido já elimina o elemento da lista. O efeito é o mesmo de remover um elemento dela.

Se você simplesmente tornar um elemento nulo, não conseguirá mais percorrer a lista, pois não tem como fazer [null]->getProximo() (o que causa NullPointerException). É como se você quebrasse a lista no meio. A não ser que o enunciado seja específico quanto a essa demanda, isso não faz sentido.

Abraço.

Criado 4 de junho de 2017

Ultima resposta 4 de jun. de 2017

Respostas 3

Participantes 2

3 Respostas

Topicos relacionados