Lista de Estruturas de Dados

Programação
#1

Gente preciso de ajuda na disciplina de estrutura de dados, sou de adm e estou pagando a disciplina eletiva de programação de ti, não tenho base pra fazer esse exercício até porque eu tinha que aprender no curso de ti nas primeiras disciplinas pra saber bem isso, me ajudem por favor.

image
image.png703×528 86.6 KB

#2

vamos la, vc sabe o que é uma double-ended list?

melhor, vc sabe o que uma lista?

de uma forma superficial, uma lista é uma coleção de nós, onde vc define que um um Nó contem “dados” e “informações” sobre os outros nós.

uma double-ended list é definida como uma lista onde cada nó sabe o proximo elemento E o anterior.

imagine uma lista contendo os numeros 1, 2 e 3

o 1 não tem elemento anterior, mas tem o posterior: 2
o 2 tem anterior e posterior
o 3 tem anterior mas não tem posterior

sacou?

é como se fosse assim ( muito simplificado )

public class No {
  public No anterior;
  public No posterior;
  public Object valor;
  public No(Object valor) {
      this.valor = valor;
  }
}

E como seria essa lista?

Ora vc pode definir uma lista assim:

public class Lista {
  public No primeiro;
}

Eu defini os atributos como sendo publicos pra evitar escrever os getters /setters - estou com preguiça. fica de exercicio ao leitor.

Agora vamos la: como vc adiciona o primeiro nó?

vc quer adicionar a string “qq coisa”:

Lista lista = new Lista();
lista.primeiro = new No("qq coisa");

pronto. agora como vc adiciona mais “alguma coisa”?

No no = new No("alguma coisa")
lista.primeiro.proximo = no;
no.anterior = lista.primeiro;

percebeu a mutreta? porem como fica pra adicionar mais alguma coisa? ai ja fica chato

o que vc precisa fazer é percorrer desde o primeiro até encontrar o ultimo.

e isso não deve ser diferente de adicionar o primeiro elemento, segundo o N

vamos elaborar um algoritmo para adicionar o no na lista

  1. pega o lista.primeiro. é nulo? então inicia com o no. fim
  2. pega o lista.primeiro e salve em uma variavel chamada ultimo. enquanto ( while) ultimo for diferente de nulo, vc faz ultimo = ultimo.proximo;. dessa forma no fim desse loop vc vai ter uma variavel que aponta para o fim da lista. vc vai fazer
ultimo.proximo = no; 
no.anterior = ultimo;

pronto. ja definimos o add(Object)

então, quando vc não pode adicionar? ora se vc tiver alguma restrição de tamanho ou de valor. o exercicio não deixa isso claro então desde que vc tenha memoria esta ok (se vc ficar sem memoria, dificilmente vc vai poder fazer alguma coisa. isso é uma situação bem singular e não adianta retornar false pq provavelmente seu programa vai ter um problema nos passos seguintes - sem falar que sistemas operacionais modernos fazem uso de Swap e OOM Killer então na pratica vc não precisa se preocupar com “faltar memoria”, seu programa todo vai pro saco antes de vc sequer ficar sabendo disso).

talvez seja proibido adicionar null nessa lista. o que pode faz todo o sentido. ( pra que criar um objeto para guardar nada ).

Como vc implementa o contains:

  1. pega o lista.primeiro. é nulo? então não contains nada
  2. pega o lista.primeiro e salve em uma variavel chamada atual. enquanto atual for diferente de nulo, vc veja se atual.no.contains(...) senão vc faz atual = atual.proximo; e continua.

aqui é interessante a classse nó expor um metodo para comparar se um dado objeto é igual ao valor que ela segura. aqui vc tem que pensar em como vc vai implementar, veja essa sugestão:

https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html#contains(java.lang.Object)

indexOf é a mesma coisa, mas vc vai usar um contador = -1 e a cada passo do seu laço while vc incrementa logo no começo.

pronto, vc ja consegue terminar.

Porém vc tem algumas pegadinhas ai:

  • remover vc precisa reconectar os links dos nos anterior e posterior corretamente.

isso : 1 <-> 2 <-> 3
se vc remover o 2 fica 1 <-> 3

  • remover o primeiro elemento significa remover também o lista.primeiro ( atribuir null )

  • inserir fica MUITO mais rapido se vc salvar na lista alem do primeiro, o ultimo. fique atento que se vc remover o ultimo vc precisa atualizar o ultimo da lista como sendo o penultimo. é uma decisão de projeto e eu só faria isso se toda a classe funcionar bonitinha

  • size vc vai ter que percorrer toda a lista até o fim ( ultimo.proximo != nil ) para calcular. vc pode salvar o tamanho em um atributo da classe Lista e incrementar / decrementar a cada add / remove. é uma decisão de projeto e eu só faria isso se toda a classe funcionar bonitinha

no caso eu dei exemplo de usar uma string mas vc pode usar qq objeto.

no caso de usar Alunos vc precisa implementar o metodo equals(Object) para comparar 2 alunos ( se tem a mesma matricula e nome vc pode considerar identicos)

assim, senta na cadeira e vai programar pq é bastante coisa. vc tem varios casos-limites ai ( remover mais do que possui, remover nas bordas, etc )

boa sorte

#3

Obrigado pelas dicas, vou seguir sua explicação, tentarei fazer alguma coisa com base em sua explicação, caso eu tenha dúvidas pergunto por aqui mesmo.