Salve ragazzi,

sto cercando di implementare il dato astratto Lista, ma la sua estensione (che mi è stata suggerita dal prof)!

Penso che tutti sappiate quali sono le operazioni generiche del dato astratto quindi vi posto direttamente l'interfaccia estesa in java:

codice:
public interface ListaExt {

	public boolean isEmpty();
	public Posizione firstList();
	public Posizione lastList(); //ext
	public boolean endList(Posizione p);
	public int lengthList(); //ext
	public Posizione pred(Posizione p);
	public Posizione succ(Posizione p);
	public Object readList(Posizione p);
	public void insert(Object e, Posizione p);
	public void writeList(Object e, Posizione p);
	public void remove(Posizione p);
}
gli operatori contrassegnati con il commento "ext" rappresentano l'estensione del dato astratto.

Il tipo Posizione (che è una interfaccia vuota)
codice:
public interface Posizione {
}
viene implementato dalla seguente classe:
codice:
class Entry implements Posizione{
	
	Object elemento;
	Entry successivo;
	Entry precedente;
	
	Entry(Object e, Entry s, Entry p)
	{
		elemento = e;
		successivo = s;
		precedente = p;
	}
	
	Entry(Object e)
	{
		elemento = e;
		successivo = this;
		precedente = this;
	}
}
Invece, la classe che sto cercando di scrivere (che implementa l'interfaccia ListaExt) ed usa la classe Entry è la seguente:

codice:
/**
 * Per evitare di dover trattare come casi speciali l'inserimento e la rimozione
 * di elementi alle estremità si può ricorrere a una realizzazione circolare doppiamente
 * collegata con una cella(listHead) il cui puntatore in avanti contiene l'informazione di inizioLista
 * e il cui puntatore indietro contiene l'informazione di ultimoLista
 */
public class ListDoubleLinkedExt implements ListaExt{
	
	private int n=0;
	private Entry listHead = new Entry(null);

	public boolean isEmpty()
	{
		return n==0;
	}
	
	public Posizione firstList()
	{
		return listHead.successivo; //è inizio lista
	}
	
	public Posizione lastList()
	{
		return listHead.precedente; //è fine lista
	}
	
	public boolean endList(Posizione p)
	{
		return p==lastList();
	}
	
	public int lengthList()
	{
		return n;
	}
	
	public Posizione pred(Posizione p)
	{
		if(isEmpty())
			throw new IndexOutOfBoundsException("Lista vuota");
		
		return ((Entry)p).precedente;
	}
	
	public Posizione succ(Posizione p)
	{
		if(isEmpty())
			throw new IndexOutOfBoundsException("Lista vuota");
		
		return ((Entry)p).successivo;
	}
	
	public Object readList(Posizione p)
	{
		if(isEmpty())
			throw new IndexOutOfBoundsException("Lista vuota");
		
		return ((Entry)p).elemento;
	}
	
	public void insert(Object e, Posizione p)
	{

		//... ...

		n++;
		
	}
	
	public void writeList(Object e, Posizione p)
	{
		((Entry)p).elemento=e;
	}
	
	public void remove(Posizione p)
	{
		if(isEmpty())
			throw new IndexOutOfBoundsException("Lista vuota");
		
                //... ....
		
		n--;
	}

}
Osservazioni:
- La classe dunque sfrutta i puntatori Entry per salvare gli oggetti e costruire così la lista direttamente in listHead.
- La variabile di istanza n è stata introdotta per poter implementare l'operatore lengthList().

Spero qualcuno mi aiuti ad impostare l'implementazione degli operatori insert e remove perchè
non so da dove partire!