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(n²): 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