Estruturas de Dados - Implementações de
Coleções usando Arrays
Objetivos da seção
- Examinar uma implementação da classe ArrayList, uma lista usando array
- Nesta seção implementaremos só a Lista
- Arrays não servem bem para conjuntos e mapas porque são lentos demais para a pesquisa
A interface
- Faremos uma implementação parcial considerando apenas os métodos seguintes:
- Veja abaixo (MinhaLista.java)
import java.util.Iterator;
interface MinhaLista {
int size();
boolean add(Object elemento);
void add(int index, Object elemento);
Object get(int index);
Object remove(int index);
boolean remove(Object elemento);
void clear();
boolean contains(Object elemento);
int indexOf(Object elemento);
Iterator iterator();
}
A implementação
- O array Java é a base da implementação
- O array deve crescer dinamicamente
- Veja abaixo (MeuVetor.java)
import java.util.*;
public class MeuVetor implements MinhaLista {
private final int CAPACIDADE_INICIAL = 10;
protected Object elementos[];
protected int contadorDeElementos;
public MeuVetor() {
this.elementos = new Object[CAPACIDADE_INICIAL];
contadorDeElementos = 0;
}
public int size() {
return contadorDeElementos;
}
public boolean add(Object elemento) {
assegureCapacidade(contadorDeElementos + 1);
elementos[contadorDeElementos++] = elemento;
return true;
}
private void assegureCapacidade(int capacidadeMínima) {
int capacidadeVelha = elementos.length;
if(capacidadeMínima > capacidadeVelha) {
Object dadosVelhos[] = elementos;
int capacidadeNova = 2 * elementos.length;
if(capacidadeNova < capacidadeMínima) {
capacidadeNova = capacidadeMínima;
}
elementos = new Object[capacidadeNova];
System.arraycopy(dadosVelhos, 0, elementos, 0, contadorDeElementos);
}
}
public void add(int index, Object elemento) {
if(index >= contadorDeElementos + 1) {
throw new ArrayIndexOutOfBoundsException(index + " > " + contadorDeElementos);
}
assegureCapacidade(contadorDeElementos + 1);
System.arraycopy(elementos, index, elementos, index + 1, contadorDeElementos - index);
elementos[index] = elemento;
contadorDeElementos++;
}
public Object get(int index) {
if(index >= contadorDeElementos) {
throw new ArrayIndexOutOfBoundsException(index);
}
return elementos[index];
}
public Object remove(int index) {
if(index >= contadorDeElementos) {
throw new ArrayIndexOutOfBoundsException(index);
}
Object valorVelho = elementos[index];
int numMovidos = contadorDeElementos - index - 1;
if(numMovidos > 0) {
System.arraycopy(elementos, index+1, elementos, index, numMovidos);
}
elementos[--contadorDeElementos] = null; // Coleta de lixo deve ser feita
return valorVelho;
}
public boolean remove(Object elemento) {
int i = indexOf(elemento);
if(i >= 0) {
remove(i);
return true;
}
return false;
}
public void clear() {
for(int i = 0; i < contadorDeElementos; i++) {
elementos[i] = null; // Coleta de lixo deve ser feita
}
contadorDeElementos = 0;
}
public boolean contains(Object elemento) {
return indexOf(elemento) >= 0;
}
public int indexOf(Object elemento) {
if(elemento == null) {
for(int i = 0; i < contadorDeElementos; i++) {
if(elementos[i] == null) {
return i;
}
}
} else {
for(int i = 0; i < contadorDeElementos; i++) {
if(elemento.equals(elementos[i])) {
return i;
}
}
}
return -1;
}
public Iterator iterator() {
return new Iterator() { // classe interna anônima
int cursor = 0;
public boolean hasNext() {
return cursor < size();
}
public Object next() {
try {
Object next = get(cursor);
cursor++;
return next;
} catch(IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
O Custo das Operações
- Ao comparar estruturas de dados (formas de imnplementar coleções), podemos comparar o custo das operações
- Usamos a notação O(...) (Ordem) para representar a complexidade computacional das operações
- A teoria por trás disso será vista em Estruturas de Dados e Algoritmos
- Algumas complexidades ocorrem frequentemente:
- O(1): complexidade constante
- Se o tamanho do problema cresce, a operação leva o mesmo tempo
- O(n): complexidade linear
- Se o tamanho do problema dobra, a operação leva 2 vezes mais tempo
- O(n2): complexidade quadrática
- Se o tamanho do problema dobra, a operação leva 4 vezes mais tempo
- O(log n): complexidade logarítmica
- Se o tamanho do problema cresce, o tempo da operação cresce com o logaritmo do tamanho
- No caso das operações do MeuVetor, temos
- Adição
- Se o array não tiver que crescer e a adição for no fim: O(1)
- Se inserir no meio: O(n)
- Se o array tiver que crescer: O(n)
- Portanto, no pior caso, a complexidade é O(n)
- Remoção: O(n)
- Acesso: O(1) (quando se sabe o index)
- Pesquisa: O(n)
- Conclusão: as operações são muito lentas
- Temos outras estruturas de dados com tudo O(1)
ed-3 programa anterior
próxima