Ap Tulo 5

apítulo 5
Listas Ligadas

"É impossível para um homem aprender aquilo que ele acha que já sabe"

Vetores (listas implementadas com array) são uma excelente alternativa ao uso direto de arrays em Java, porém para algumas tarefas eles podem não ser eficientes, justamente por esse fato.

Adicionar um elemento na primeira posição de um Vetor, por exemplo, consome muito tempo, pois temos de deslocar todos os outros elementos uma posição para a frente. A performance dessa operação degrada a medida que a quantidade de elementos do nosso vetor cresce: ela consome tempo linear em relação ao número de elementos.

Analogamente, remover um elemento da primeira posição implica em deslocar todos os outros elementos que estão na sua frente para trás.

Em alguns casos, queremos uma implementação de Lista na qual a operação de adicionar ou a de remover um aluno na primeira posição seja computacionalmente eficiente. Conseguiremos isso através de uma Lista Ligada[/label].

Esta estrutura que vamos criar terá a inserção e remoção nas "pontas" da lista computacionalmente eficientes.

Lembrando que as operações da Lista para o nosso sistema de gerenciamento de alunos são:

Adiciona um dado aluno no fim da Lista.
Adiciona um dado aluno em uma dada posição.
Pega o aluno de dada posição.
Remove o aluno de dada posição.
Verifica se um dado aluno está armazenado.
Informar o número de alunos armazenados.
5.1 - Solução clássica de Lista Ligada
Para manipular uma estrutura sem ter de alterar todos seus vizinhos, precisamos de algo que não seja fixo. Uma array é uma estrutura fixa na memória, precisamos sempre empurrar todos seus vizinhos para um lado para conseguir espaço, ou para remover algum dos elementos, para não deixar espaços vazios.

Então a idéia aqui é ter uma forma de, dado um aluno, saber quem é o próximo, sem usar uma estrutura fixa. Podemos mudar a própria classe Aluno! Repare no código abaixo:

public class AlunoLista {

private String nome;

private int idade;

private