Realizzazione del TDA Lista con liste concatenate

Presentiamo un'unica realizzazione del tipo di dati astratto Lista, in cui ogni istanza (cioè una lista) memorizza i suoi dati in una lista concatenata.

**ATTENZIONE:** non confondete i seguenti concetti
Tipo di dati astratto Lista	Corrisponde all'interfaccia `List`
Lista concatenata	E' una sequenza di oggetti della classe `ListNode` in cui ogni 'nodo' ha nel campo `next` un puntatore al nodo successivo. [Usate ad esempio nella classe `ListStack` per implementare il TDA Pila]
La classe `LinkedList`	La classe concreta che implementa l'interfaccia `List` utilizzando una lista concatenata per memorizzare gli elementi di un'istanza

Naturalmente è possibile realizzare il TDA Lista con strutture dati diverse, come Vector (si vedano gli esercizi), array, ...

Descrizione della classe LinkedList

La realizzazione in LinkedList dei seguenti metodi dell'intefaccia List è standard:

boolean add( Object x );
boolean remove( Object x);
boolean contains( Object x);
boolean isEmpty( );
void clear( );

Invece per il metodo

Iterator iterator()

si utilizzerà un concetto nuovo, quello di classe interna. Infatti LinkedList contiene la classe interna ProtectedItr, e il metodo iterator() restituisce un oggetto di questa classe.

La relazione tra le varie entità che costituiscono la classe LinkedList può essere descritta dal seguente diagramma di classi UML:

LinkedList: variabili d'istanza

In LinkedList ogni elemento della lista è memorizzato in un nodo, cioè un oggetto di tipo ListNode. Questi oggetti hanno due variabili d'istanza: element, che contiene l'elemento, e next che contiene un riferimento al prossimo nodo.

public class LinkedList implements List {
    protected ListNode first;
    protected ListNode last;
    protected int modCount;

...

first mantiene un riferimento al primo nodo della lista
last mantiene un riferimento all'ultimo nodo
modCount è un contatore di modifiche, usato per determinare se ci sono delle modifiche concorrenti dutante l'uso di un iteratore.

Il metodo add

public boolean add( Object x ) {
    if ( x == null )
      throw new IllegalArgumentException( );
       modCount++;
       // caso lista inizialmente vuota
       if ( isEmpty( ) ) {
            first = last = new ListNode( x );
       }

       else {
       // caso lista non vuota
            last.next = new ListNode( x );
            last = last.next;
       }
    return true;
}

Il metodo remove

public boolean remove(Object x ) {

      // Oggetto nullo: viene sollevata un'eccezione.
    if ( x == null )
      throw new IllegalArgumentException( );

      // Lista vuota: si restituisce false.
    if ( isEmpty( ) )
      return false;

// Il nodo da eliminare è il primo della lista:
if ( x.equals( first.element ) ) {

if ( first == last ) // è anche l'ultimo
last = null;

          // non è l'ultimo (caso 3b)
            first = first.next;
            modCount++;
      return true;
        }

      // Il nodo da eliminare non è il primo della lista.
    for ( ListNode h = first; h.next != null; h = h.next ) {
      if ( x.equals( h.next.element ) ) {
         if ( h.next == last )   // è anche l'ultimo
                   last = h;
              // non è l'ultimo (caso 4b)
               h.next = h.next.next;
               modCount++;
         return true;
               }
        }
    returnfalse;
    }

I metodi contains, isEmpty, clear e iterator

public boolean contains( Object x ) {
    if ( x == null )
     throw new IllegalArgumentException( );
    for (ListNode h = first; h != null; h=h.next ){
       if ( x.equals( h.element ) )
          return true;
         }
    return false;
}

public boolean isEmpty( ) {
return first == null;
}

public void clear( ) {
modCount++;
first = last = null;
}

public Iterator iterator( ) {
return new ProtectedItr( );
}

Le Classi Interne

In Java è possibile dichiarare una classe Aall'interno di un'altra classe B: in questo caso A è una classe interna di B.
L'uso di classi interne è abbastanza raro. Ha senso dichiarare A come una classe interna di B quando:

l'esistenza di una istanza di A ha solo senso in relazione ad una istanza di B;
può essere utile avere più istanze di A per una stessa istanza di B.

Ad esempio, un iteratore può esistere solo in presenza della collezione su cui deve operare, e per la stessa collezione possiamo creare più iteratori che la scandiscono in modo indipendente.

Regole di visibilità

Una classe interna (con i suoi medodi e variabili d'istanza) è visibile solo nella classe che la include (classe contenitrice), ed è invisibile all'esterno.
Le istanze di classe interna possono essere passate all'esterno della classe contenitrice come valore restituito da una chiamata di un suo metodo.
Variabili e metodi della classe contenitrice sono visibili alla classe interna, anche se privati.
Il codice della classe interna può usare nomi semplici, cioè senza usare la "dot-notation", per riferire variabili e metodi della classe esterna.

Schema di utilizzo di una classe interna

// Classe contenitrice
public class MiaOuterClass {

..... metodi e variabili di MiaOuterClass

   // metodo per costruire un'istanza
   // della classe interna
   InnerClassInterface miaInner( ) {
    return new MiaInnerClass( );
   }

// Classe interna
class MiaInnerClass implements InnerClassInterface{

..... metodi e variabili di MiaInnerClass

} // Fine Classe interna

} // Fine Classe contenitrice

Si noti che il tipo del metodi miaInner() è una interfaccia visibile all'esterno della classe contenitrice: non potrebbe essere MiaInnerClass(), perché non è visibile all'esterno.

La Classe interna ProtectedItr: variabili

ProtectedItr ha tre variabili di istanza:

cursor, che individua il nodo il cui elemento è stato restituito dall'ultima chiamata di next(); se questo è stato cancellato con una remove() allora cursor coincide con precursor. La variabile cursor vale null quando viene creato l'iteratore.

precursor, che individua il penultimo elemento restituito da next(), se esiste, altrimenti vale null.

expectedModCount, che tiene conto delle modifiche fatte alla lista, per individuare eventuali modifiche concorrenti; viene inizializzata con il valore corrente di modCount.

protected class ProtectedItr implements Iterator {

      protected ListNode cursor;  
      protected ListNode precursor;

           // per accorgersi di modifiche concorrenti  
      protected int expectedModCount;

      ProtectedItr( ) {
          precursor = cursor = null;
          expectedModCount = modCount;
      }

....

La classe interna ProtectedItr: metodi (I)

    public boolean hasNext( ) {
      if ( modCount != expectedModCount ) // Modifica concorrente
         throw new ConcurrentModificationException( );
      return ( !isEmpty( ) &&
                   ( (cursor == null) || (cursor.next != null) ) );

     public Object next( ) {
     if ( !hasNext( ) )            // la lista è finita
         throw new NoSuchElementException( );
         precursor = cursor;
         cursor = (cursor == null) ? first : cursor.next;
     return cursor.element;
     }

Il significato dell' espressione condizionale in next()è :

if (cursor == null)
cursor = first;
else cursor = cursor.next;

Graficamente,

La classe interna ProtectedItr: metodi (II)

Il metodo remove() può essere invocato solo una volta per ciascuna chiamata a next(). Infatti ha successo solo se precursor e cursor sono diversi.

Attenzione: correggere le dispense...

   public void remove( ) {
    if ( modCount++ != expectedModCount++ )
     throw new ConcurrentModificationException( );
    if ( (cursor == precursor) || isEmpty( ) )
     throw new IllegalStateException( );
    if ( precursor == null ) { // Cursor punta al primo elemento
          if ( first == last )   // ... e ultimo elemento
               last = null;
          first = first.next;
       } else {    // Cursor punta ai nodi successivi
          if ( cursor == last ) // Ultimo elemento
                   last = precursor;
               precursor.next = cursor.next;
               }
       cursor = precursor;
      }

Esercizi su realizzazione di liste

1) Definire la classe VectorList che realizza List usando la classe Vector.

2) Definire l'interfaccia RichList che estende List con i metodi seguenti.

boolean removeAll( Object x )

che cancella tutte le occorrenze di x, anziché solo la prima.

int occur( Object x )

che conta le occorrenze di un oggetto x nella lista. Restituisce 0 nel caso l'oggetto non compaia nella lista. Definire la classe RichLinkedList che realizza RichList estendendo LinkedList. Scrivere una classe TestRichList che utilizza i nuovi metodi.