Lista Simplesmente Encadeada com Descritor - Implementação
Lista simplesmente encadeada (LSE)
O ideal é falar que, geralmente trabalhamos com pelo menos duas classes, a primeira é a
Classe nó
características:
- valor inteiro
- referência ao próximo, do tipo nó
- getters and setters
Classe ListaSE
características: referência ao inicio
métodos:
- inserirInicio(No novoNo);
- inserirFim(No novoNo);
- removerInicio();
- listar();
Método InserirInicio(No novoNo)
- passa como parâmetro a referêcia do tipo No novoNo
- verifica se a lista está vazia
- tá vazia, faz o inicio apontar pro novoNo
public void inserirInicio(No novoNo) {
if(inicio == null) {
inicio = novoNo;
}else {
novoNo.setProximo(inicio);
inicio = novoNo;
}
}
Método InserirFim(No novoNo)
- passa como parâmetro a referêcia do tipo No novoNo
- verifica se a lista está vazia
- tá vazia, faz noAux apontar pro inicio
- percorre lista até o final
- faz o último elemento setar o novoNo
public void inserirFim(No novoNo) {
if(inicio == null) {
inicio = novoNo;
}else {
No noAux = inicio;
while(noAux.getProximo()!= null) {
noAux = noAux.getProximo();
}
noAux.setProximo(novoNo);
}
}
Método RemoverInicio()
- sem parâmetro
public void removerInicio() {
if(inicio == null) {
System.out.println("A lista está vazia!");
}else {
No noAux = inicio;
noAux = noAux.getProximo();
inicio = noAux;
}
}
Caso faça inicio = inicio.getProximo(); vai funcionar num primeiro momento, mas vai deixar o elemento preso na memória e perder a referência. Porque o elemente fica amarrado a lista, o que muitas vezes ocasiona um leak in.
Método Listar()
- checar se as operações estão funcionando como o planejado
public void listar() {
if(inicio == null) {
System.out.println("Lista vazia");
}else {
No noAux = inicio;
while(noAux != null) {
System.out.println(noAux.getValor()+" ");
noAux = noAux.getProximo();
}
}
Todas as listas encadeadas começam sempre, em todas as operações, com a verificação se a lista está vazia.
Lista simplesmente encadeada com descritor (LSED)
Classe nó //da LSED é igual LSE
características:
- valor inteiro
- referência ao próximo, do tipo nó
- getters and setters
Quando temos encapsulamento, quer dizer que estamos protegendo os atributos de classe.
Nó representa espaço em memória para alocar valores, ou seja, faz todo sentido dar visibilidade aos atributos. Não de forma direta, colocando ele como public, mas trabalhando com ele private e criando getters and setters para inserir os elementos dentro desses atributos.
Classe Lista
características:
- referência ao inicio
- atributo quantidade //com descritor
- referência ao fim
métodos:
- inserirInicio(No novoNo);
- inserirFim(No novoNo);
- removerInicio();
- listar();
Não são criados getters and setters na classe Lista, porque, com isso viria a possibilidade de o usuário externo dar um lista.setInicio = null; o que apagaria toda a lista.
A forma de interagir com a lista ocorrerão extritamente através dos métodos.
Método InserirFim(No novoNo)
- passa como parâmetro a referêcia do tipo No novoNo
- verifica se a lista está vazia
- tá vazia, faz noAux apontar pro inicio
- percorre lista até o final
- faz o último elemento setar o novoNo
public void inserirFim(No novoNo) {
if(inicio == null) {
inicio = novoNo;
fim = novoNo;
qnt++;
}else {
fim.setProximo(novoNo);
fim = novoNo;
qnt++;
}
}
Como esses trechos de código se repetem, tanto em if quanto em else, podemos otimizar colocando o pra fora das condicionais:
public void inserirFim(No novoNo) {
if(inicio == null) {
inicio = novoNo;
}else {
fim.setProximo(novoNo);
}
fim = novoNo;
qnt++;
}
Questões
1.A função de remover no fim da lista encadeada deve funcionar quando tem somente um nó?
Sim.Tem que garantir com os ifs e elses que isso funcione sempre.
-RESUMIR-
Sempre temos que considerar qualquer método, de qualquer tipo de estrutura de dados, pra resolver qualquer uma das situações. Então independente se a lista estiver vazia, no caso da lista sequencial, se ela estiver cheia, se a posição específica existir ou não, nunca podemos mudar o erro, sempre temos que tratar.
Se tiver, por exemplo, uma lista com um único elemento e eu peço pra remover no fim, ele tem que matar esse elemento e a lista ficará vazia.
No caso da Lista Simplesmente Encadeada, eu faria meu inicio apontar pra nulo, daí pronto, perde a referência daquele objeto, o Garbage Collector passa e mata aquele elemento.
Senão, terei de navegar na minha lista até o penúltimo elemento, pra poder matar a referência pra esse último elemento, depois de matar o apontamento para o elemento, está resolvido.
Não adianta navegar atéo final e dizer que o auxiliar é igual a nulo. Isso não faz nada, só estou limpando a referência. Tem que caminhar até o penúltimo e o setProximo dele apontar para nulo. Ele fica sozinho e o Garbage Collector mata ele.
Se tu estiver lidando com uma lista simplesmente encadeada, vai ter que verificar se o início é diferente de nulo. Pra qualquer método que tu faça lista encadeada, vai ter que fazer isso.
Outra informação importante de se saber é se o inicio getProximo é nulo. (significa que só tem um elemento)
//não pode fazer direto, porque se o inicio for nulo da null pointer exception
2.Se eu tenho uma lista encadeada, onde estão inseridos os valores 1, 2 e 3...
e quero inserir o número 5 na posição 1, como a lista ficaria?
Quando falamos de lista, sempre vamos trabalhar com a mesma lógica de indexação da lista sequencial. Nunca pode perder ou sobrescrever valores. Logo, se ele estiver fazendo inicio setProximo novoNo, vai perder o restante da lista.
Na inserção em uma posição específica é importante varrer a lista até chegar na posição anterior a posição em que se quer inserir. Cria-se então um noAux pra varrer a lista até a posEspecifica - 1 e então, novoNo setProximo aponta para noAux getProximo.
E depois, noAux setProximo apontando para o mesmo lugar que o novoNo.
Logo o resultado seria #1,5,2,3
"Sempre que for alocar alguma coisa na lista, comece alocando o novoNo."
Comentários
Postar um comentário