Soluzione 8.3

La classe ArrayListTester e` identica alla classe LinkedListTester scritta nell'esercizio precedente, se non per il fatto che usa oggetti di tipo ArrayList invece che di tipo LinkedList. E` quindi sufficiente usare il codice di LinkedListTester e sostituire gli enunciati "new LinkedList()" con enunciati "new ArrayList()".
La classe ArrayList realizza in maniera immediata i metodi di Container su array riempiti solo in parte. La parte piu` interessante dell'esercizio e` la realizzazione della classe interna ArrayListIterator.
import java.util.NoSuchElementException;

public class ArrayList implements List
{
    //costruttore
    public ArrayList()
    {   v = new Object[1];
        makeEmpty(); 
    }
  
    public void makeEmpty()
    {   //v = new Object[1];
        vSize = 0;
    }
  
    public boolean isEmpty()
    {   return vSize == 0;  }
  
    public ListIterator getIterator()
    {   return new ArrayListIterator(); }

    //campi di esemplare
    private Object[] v;
    private int vSize;

    //classe (privata) interna: ArrayListIterator
    //in molti dei metodi della classe ArrayListIterator accedo all'array v,
    //campo di esemplare privato della classe ArrayList: e` lecito farlo perche`
    //ArrayListIterator e` classe interna di ArrayList. Se volessi qualificare
    //completamente v, potrei usare la sintassi ArrayList.this.v (analogamente
    //a quanto fatto in aula per le classi LinkedList e LinkedListIterator)
    private class ArrayListIterator implements ListIterator
    {
        public ArrayListIterator()
        {   position = -1; }

        public boolean hasNext()
        {   return position + 1 < vSize;  }

        public Object next() throws NoSuchElementException
        {   if (!hasNext())  throw new NoSuchElementException();
            position++;  //prima incremento position, 
            return v[position]; //poi leggo l'elemento dell'array
        }

        public void add(Object obj)
        {   if (vSize == v.length)  //se l'array e` pieno lo devo ridimensionare
            {   Object[] vTmp = new Object[2 * vSize];
                for (int i = 0; i < vSize; i++)
                    vTmp[i] = v[i];
                v = vTmp;
            }
            //devo spostare in avanti di uno tutti gli elementi dell'array tra
            //position e vSize, per fare posto al nuovo elemento da inserire
            for (int i = vSize; i > position + 1; i--)
                v[i] = v[i-1];
            v[++position] = obj;
            vSize++;
        }

        // A differenza del metodo remove di LinkedListIterator, questo remove
        // *non* va sempre invocato dopo next o add (se non la prima volta)
        // Infatti qui non abbiamo problemi con i riferimenti ai nodi: in questa
        // realizzazione non esistono nodi e riferimenti, ma array e indici! 
        public void remove() throws IllegalStateException
        {   if (position == -1)   throw new IllegalStateException();
            for (int i = position; i < vSize-1; i++)
                v[i] = v[i+1];
            vSize--;
            position--;
        }
        //campo di esemplare di ArrayListIterator
        private int position;
    }
}