A definição de Lista é muito simples: elas mantêm a ordem de inserção e permitem a repetição dos elementos. As operações básicas são:
ADD(x): operação para adicionar um elemento no final da lista.
ADD(i,x): operação para adicionar um elemento em uma posição específica.
GET(i): operação para recuperar um elemento em uma posição específica.
REMOVE(i): operação para remover um elemento em uma posição específica.
O tipo de lista mais simples é o Vetor. Sua implementação é baseada em uma estrutura sequencial, onde por padrão os elementos são adicionados no final, após o último elemento. Seu acesso é através da posição (índice) em que foram inseridos.
Essa implementação é excelente para acessar rapidamente um elemento, por exemplo, para acessar o elemento 63, basta informar o índice 2 e o acesso será direto (GET(2))
Porém não é tão interessante quando queremos inserir um elemento em uma posição no meio, por exemplo, na posição 3 (ADD(2, 18)) pois teríamos que deslocar todos os demais elementos para direita.
Apesar esse deslocamento ser uma operação simples, em um vetor com muitos elementos essa operação pode ser custosa e demorada.
public class Vetor implements Lista {
String[] elementos = new String[10];
int indice;
@Override
public void add(String elemento) {
elementos[indice] = elemento;
indice++;
}
@Override
public String get(int i) {
return elementos[i];
}
@Override
public void add(int posicao, String elemento) {
for (int i = indice - 1; i >= posicao; i--) {
elementos[i + 1] = elementos[i];
}
elementos[posicao] = elemento;
indice++;
}
@Override
public void remove(int posicao) {
elementos[posicao] = null;
for (int i = posicao; i+1 < elementos.length; i++) {
elementos[i] = elementos[i+1];
}
indice--;
}
public static void main(String[] args) {
Vetor vetor = new Vetor();
vetor.add("A");
vetor.add("C");
vetor.add("D");
vetor.add("E");
System.out.println(Arrays.asList(vetor.elementos));
vetor.add(1, "B");
String c = vetor.get(2);
System.out.println(c);
System.out.println(Arrays.asList(vetor.elementos));
vetor.remove(2);
System.out.println(Arrays.asList(vetor.elementos));
}
}
Eis que surgem as Listas ligadas para o resgate =D.
Essas listas possuem uma implementação mais elaborada. Para percorrer os elementos é necessário que cada elemento saiba onde está seu sucessor.
A grande vantagem desta implementação é que se precisarmos inserir um elemento no meio (ADD(2,'E')), basta fazer com que o elemento anterior aponte para o novo e o novo para o sucessor tornando a inserção uma operação rápida.
Em contrapartida, como nem tudo são flores, o acesso a um determinado elemento pelo índice já não é mais tão fácil. Na verdade, precisamos navegar do primeiro elemento perguntando onde está o próximo até chegarmos na posição desejada.
Além disso a navegação ocorre apenas em uma direção, do primeiro elemento até o último e há casos em que gostaríamos de ir e voltar nessa navegação.
public class ListaLigada implements Lista {
No primeiro;
No ultimo;
@Override
public void add(String elemento) {
if (primeiro == null) {
primeiro = new No(elemento);
ultimo = primeiro;
} else {
ultimo.proximo = new No(elemento);
ultimo = ultimo.proximo;
}
}
@Override
public String get(int posicao) {
No no = buscarNo(posicao);
return no.elemento;
}
@Override
public void add(int posicao, String elemento) {
No retorno = buscarNo(posicao-1);
No novo = new No(elemento);
novo.proximo=retorno.proximo;
retorno.proximo = novo;
}
@Override
public void remove(int posicao) {
No retorno = buscarNo(posicao-1);
No temp = retorno.proximo;
retorno.proximo = temp.proximo;
}
private No buscarNo(int posicao) {
No retorno = primeiro;
int contador = 0;
while (contador < posicao) {
retorno = retorno.proximo;
contador++;
}
return retorno;
}
public void imprimir() {
String conteudo = primeiro.elemento;
No proximoNo = primeiro.proximo;
while(proximoNo != null) {
conteudo+=", "+proximoNo.elemento;
proximoNo = proximoNo.proximo;
}
System.out.println(conteudo);
}
public static void main(String[] args) {
ListaLigada listaLigada = new ListaLigada();
listaLigada.add("A");
listaLigada.add("C");
listaLigada.add("D");
listaLigada.add("E");
listaLigada.imprimir();
listaLigada.add(1, "B");
listaLigada.imprimir();
String c = listaLigada.get(2);
System.out.println(c);
listaLigada.remove(2);
listaLigada.imprimir();
}
}
Para ter uma navegação bidirecional, a listas podem ser duplamente ligadas. Isso significa que o elemento sabe não só a posição do próximo mas também do anterior a ele, seu antecessor.
public class ListaDuplamenteLigada implements Lista {
No primeiro;
No ultimo;
@Override
public void add(String elemento) {
addFim(elemento);
}
public void addFim(String elemento) {
if (primeiro == null) {
primeiro = new No(elemento);
ultimo = primeiro;
} else {
No novo = new No(elemento);
ultimo.proximo = novo;
novo.anterior = ultimo;
ultimo = novo;
}
}
public void addInicio(String elemento) {
if (primeiro == null) {
primeiro = new No(elemento);
ultimo = primeiro;
} else {
No novo = new No(elemento);
primeiro.anterior = novo;
novo.proximo = primeiro;
primeiro = novo;
}
}
@Override
public String get(int posicao) {
No no = buscarNo(posicao);
return no.elemento;
}
@Override
public void add(int posicao, String elemento) {
No novo = new No(elemento);
No esquerda = buscarNo(posicao - 1);
No direita = esquerda.proximo;
novo.proximo = direita;
novo.anterior = esquerda;
direita.anterior = novo;
esquerda.proximo = novo;
}
@Override
public void remove(int posicao) {
No retorno = buscarNo(posicao);
No esquerda = retorno.anterior;
No direita = retorno.proximo;
esquerda.proximo = direita;
direita.anterior = esquerda;
}
private No buscarNo(int posicao) {
No retorno = primeiro;
int contador = 0;
while (contador < posicao) {
retorno = retorno.proximo;
contador++;
}
return retorno;
}
public void imprimirParaFrente() {
String conteudo = primeiro.elemento;
No proximoNo = primeiro.proximo;
while (proximoNo != null) {
conteudo += ", " + proximoNo.elemento;
proximoNo = proximoNo.proximo;
}
System.out.println(conteudo);
}
public void imprimirParaTras() {
String conteudo = ultimo.elemento;
No noAnterior = ultimo.anterior;
while (noAnterior != null) {
conteudo += ", " + noAnterior.elemento;
noAnterior = noAnterior.anterior;
}
System.out.println(conteudo);
}
public static void main(String[] args) {
ListaDuplamenteLigada listaLigada = new ListaDuplamenteLigada();
listaLigada.add("C");
listaLigada.add("D");
listaLigada.add("E");
listaLigada.imprimirParaTras();
listaLigada.imprimirParaFrente();
System.out.println();
listaLigada.addInicio("A");
listaLigada.imprimirParaTras();
listaLigada.imprimirParaFrente();
System.out.println();
listaLigada.add(1, "B");
listaLigada.imprimirParaTras();
listaLigada.imprimirParaFrente();
System.out.println();
String c = listaLigada.get(2);
System.out.println(c);
listaLigada.remove(2);
listaLigada.imprimirParaTras();
listaLigada.imprimirParaFrente();
System.out.println();
}
}
Resumindo:
- Listas são estruturas que permitem armazenar elementos garantindo sua ordem de inserção e permitindo repetir elementos.
- Vetor tem acesso rápido e fácil aos elementos porém pode demorar mais para inserir em determinadas posições.
- Listas ligadas e duplamente ligadas são excelentes para inserção em posições desejadas porém não são boas para acessar elementos específicos.
A sua escolha em relação à qual usar vai depender da sua necessidade. Acesso ou Inserção.
Podemos concluir também que as Pilhas e Listas são um tipo de lista que possuem características mais específicas.
Nenhum comentário:
Postar um comentário