[JAVA] Implementazione dato astratto Lista esteso

[VincenzoTheBest]

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:

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)

public interface Posizione {
}

viene implementato dalla seguente classe:

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:

/**
 * 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!

[andbin]

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

Innanzitutto alcune considerazioni generali.

Entry rappresenta un nodo "concreto" della lista. Posizione è una interfaccia che rappresenta in modo più astratto (e aggiungo, "opaco" all'esterno di ListDoubleLinkedExt) un nodo.

Se Entry non serve altrove fuori da ListDoubleLinkedExt allora sarebbe anche appropriato mettere Entry come nested class privata di ListDoubleLinkedExt.

remove() è facile. Scansioni la lista linkata e quando trovi quello stesso identico oggetto Entry (qui si intende proprio uguaglianza del reference!) allora lo fai "saltare" via. Nel senso che il precedente nodo e il successivo nodo devono "puntarsi". Chiaramente non è detto che ci sia un nodo successivo .... ma non ti interessa, perché ti serve solo trattare il campo 'successivo' del nodo trovato.

Per dirlo a parole, sia 'corrente' il Entry trovato (lo stesso oggetto referenziato dal Posizione passato):

a) a corrente->precedente->successivo devi assegnare corrente->successivo (qualunque cosa sia)
b) se corrente->successivo non è null allora a corrente->successivo->precedente devi assegnare corrente->precedente

Con -> indico in generale il riferimento del campo (se puoi vuoi usare accesso diretto o setter/getter, vedi tu).


Il insert() è una cosa similare ma opposta, solo che qui inserisci un nuovo Entry in mezzo a due nodi. E immagino che il Entry devi inserirlo dopo il Posizione trovato.

[VincenzoTheBest]

nell'insert ho scritto il seguente codice:

		Entry q = (Entry)firstList();
		
		while(!endList(q))
		{
			if((Entry)p==q)
				break;
			
			q=(Entry)succ(q);
		}
		
		Entry nuovo = new Entry(e);
		
		nuovo.precedente = q; //punto indietro a q (in quanto lo inserisco dopo q)
		
		//se q ha un successivo
		if(q.successivo != null){
			nuovo.successivo = q.successivo; //in avanti punto al successivo di q
			q.successivo.precedente = nuovo; //il successivo di q punta indietro al nuovo
		}
		
		q.successivo = nuovo;
		
		n++;

Ho provato a testare con il codice seguente

		ListaExt list = new ListDoubleLinkedExt();
		
		System.out.println("Creazione di lista 1");
		System.out.println("la lista inizialmente e' vuota: " + list.isEmpty()+ "\n");
		
		list.insert("ultimo", list.firstList());
		list.insert("b", list.firstList());
		list.insert("c", list.firstList());
		list.insert("d", list.firstList());
		list.insert("e", list.firstList());
		
		System.out.println("Stampo tutti gli elementi: ");
		Posizione p = list.firstList();
		while(!list.endList(p))
		{
			System.out.println(list.readList(p));
			p=list.succ(p);
		}
		
		System.out.println("\nprimo lista: " + list.readList(list.firstList()));
		System.out.println("fine lista: " + list.readList(list.lastList()));

Ma stampa:
Creazione di lista 1
la lista inizialmente e' vuota: true

Stampo tutti gli elementi:
ultimo
e
d
c

primo lista: ultimo
fine lista: b



E' chiaramente sbagliato! Dove sbaglio?

[andbin]

Originariamente inviato da VincenzoTheBest
nell'insert ho scritto il seguente codice:

Nota alcune cose in generale:

- In if((Entry)p==q) il cast non serve.
- Hai usato i metodi firstList, endList, succ. Ok, tecnicamente è corretto. Ma questi sono metodi "pubblici" usati da chi, all'esterno, ha solo una visione "opaca" dei nodi. Potresti anche accedere più direttamente alle Entry, visto che dentro ListDoubleLinkedExt hai una visione "trasparente" dei nodi.

Originariamente inviato da VincenzoTheBest

Entry nuovo = new Entry(e);

nuovo.precedente = q; //punto indietro a q (in quanto lo inserisco dopo q)

//se q ha un successivo
if(q.successivo != null){
    nuovo.successivo = q.successivo; //in avanti punto al successivo di q
    q.successivo.precedente = nuovo; //il successivo di q punta indietro al nuovo
}

q.successivo = nuovo;

Potevi usare l'altro costruttore di Entry!! Infatti il 's' è q.successivo e 'p' è q.

Poi basta solo:
- se q.successivo diverso da null, assegnare a q.successivo.precedente il nuovo
- assegnare a q.successivo il nuovo (questo sempre, nessun test).

Come vedi molto semplice.

[VincenzoTheBest]

Ho fatto gli aggiustamenti che mi hai suggerito, ma i dati stampati continuano ad essere sbagliati!
Cosa posso fare?