ListaLinear_Arvores

Dessa forma, a lista pode ser distribuída com um grupo de vários pequenos blocos, interligados por ponteiros, que juntos formam uma só lista. Se cada bloco contiver cinco posições, quatro vão ser usadas para armazenar os elementos e uma posição (a última) será como um ponteiro que guardará o endereço do próximo elemento da lista (que está em outro bloco).

Estática

lista primeiro

último

Vantagens
Não requer movimentação de nós nas operações de inserção e eliminação (como na lista por contigüidade);
Apenas os ponteiros são alterados (lembre que cada registro pode conter campos complexos);
Não é necessário saber, anteriormente, o número máximo de elementos que uma lista pode ter, o que implica em não desperdiçar espaço na Memória Principal do computador;
Tamanho máximo para a lista é o tamanho da memória livre do computador.

Desvantagens
O acesso não é indexado, para acessar um k-ésimo nó tem que percorrer do primeiro elemento até chegar ao desejado;
Aumento do tempo de execução, o qual é gasto na obtenção de espaço de memória;
Reserva de espaço para armazenar os apontadores (campo PROX);
Necessário gerenciar os ponteiros PROX;
A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida.

public void inserirPrimeiro(Item elem){ No novoNo = new No (elem); if (this.éVazia()){ this.ult = novoNo;
}
novoNo.setProx(this.prim); this.prim = novoNo; this.quantNos++; } public void inserirUltimo (Item elem){ No novoNo = new No (elem); if (this.éVazia()){ this.prim = novoNo; } else { this.ult.setProx(novoNo); } this.ult = novoNo; this.quantNos++; } public No pesquisarNo (int chave){ No atual = this.prim; while ((atual != null) && (atual.getInfo().getChave() != chave)){ atual = atual.getProx(); } return atual; } public boolean removerNo (int chave) { No atual