listas ligadas

LISTAS LIGADAS

Estrutura de Dados
LISTAS LIGADAS

Cefet-PI UNED Parnaíba
Prof: Jefferson S. Silva

LISTAS LIGADAS
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.

INTRODUÇÃO
Adicionar um elemento na primeira posição de um Vetor 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.

LISTAS LIGADAS
Nossa interface
1)
2)
3)
4)
5)
6)

Adicionar um dado elemento no fim da Lista.
Adicionar um dado elemento em um dada posição.
Pegar o elemento de uma dada posição.
Remover o elemento de uma dada posição.
Verificar se um dado elemento está contido na Lista.
Informar a quantidade de elementos da Lista.

1

Solução clássica de Lista Ligada

Solução clássica de Lista Ligada

Precisamos de algo que não seja fixo como um array.
Então a idéia aqui é ter uma forma de, dado um aluno, saber quem é o próximo, sem usar uma estrutura fixa

Solução clássica de Lista Ligada

Célula e Lista Ligada

Repare que, apesar do efeito de um aluno estar “ao lado” do outro, na memória é mais provável que eles não se encontrem um ao lado do outro, e sim em regiões bem diferentes da memória, só que cada um deles sabe dizer em que local se encontra o próximo aluno (pois temos a referência ao proximo).

2

Célula e Lista Ligada

Célula e Lista Ligada

Crie a classe Celula com dois atributos:
Celula proxima
Object elemento

public class Celula { private Celula proxima;

e os metodos getters e setters, além de
construtores