[JAVA] Coda doppia

[michelexeno]

Ciao a tutti sto progettando il dato astratto coda doppia in java, (consente di inserire, cancellare, esaminare elementi in entrambe le estremità) implementandolo con una lista doppiamente collegata. Ci sto impiegando troppo tempo e mi sto confondendo parecchio..mi servirebbe una mano, grazie.

package coda;

public class CodaDoppiaCollegata implements CodaDoppia {
	
	private Record inizio = null; //Punta all'elemento in testa
	private Record fine = null; ////Punta all'elemento in coda
	
	private class Record {
		public Object elem;
		public Record next; //Punta all'elemento successivo
		public Record prev; //Punta all'elemento precedente
		
		public Record(Object e) {
			elem = e;
			next = prev = null;
		}
	}

	@Override
	/**
	 * Inserisce un elemento in testa.
	 */
	public void enqueueStart(Object e) {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p;
			
		} else {
			inizio.next = new Record(e);
			inizio = inizio.next;
		}
	}

	@Override
	/**
	 * Inserisce un elemento in coda.
	 */
	public void enqueueEnd(Object e) {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p;
			
		} else {
			fine.next = p;
			fine = fine.next;
		}
	}

	@Override
	/**
	 * Rimuove l'elemento in testa.
	 */
	public void dequeueStart() {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		inizio = inizio.next;
	}

	@Override
	/**
	 * Rimuove l'elemento in coda.
	 */
	public void dequeueEnd() {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		fine = fine.next;
	}

	@Override
	/**
	 * Verifica se la coda e' vuota.
	 */
	public boolean isEmpty() {
		return (inizio == null) && (fine == null);
	}

	@Override
	/**
	 * Restituisce l'elemento in testa.
	 */
	public Object first() {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		return inizio.elem;
	}

	@Override
	/**
	 * Restituisce l'elemento in coda.
	 */
	public Object last() {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		return fine.elem;
	}
	
	private static void inizializza(CodaDoppia doubleQueue) {
		doubleQueue.enqueueStart("secondo");
		doubleQueue.enqueueStart("primo");
		doubleQueue.enqueueEnd("terzo");
		doubleQueue.enqueueEnd("quarto");
	}
	
	public static void main(String args[]) {
		
		CodaDoppia test = new CodaDoppiaCollegata();
		inizializza(test);
		System.out.println(test.first());
		System.out.println(test.last());
		test.dequeueStart();
		System.out.println(test.first());
		test.dequeueEnd();
		System.out.println(test.last());
	}

}

[wingman87]

prev non lo usi praticamente mai... inoltre dovresti inizializzare anche il prev/next dell'elemento che inserisci, non solo aggiornare (correttamente) la vecchia testa/coda

[michelexeno]

In precedenza i metodi per aggiungere in testa e coda gli elementi gli avevo scritti cosi

@Override
	/**
	 * Inserisce un elemento in testa.
	 */
	public void enqueueStart(Object e) {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p.prev = p.next = p;
			
		} else {
			p.next = inizio.next;
			inizio.next.prev = p;
			inizio.next = p;
			inizio = inizio.next;
		}
	}

	@Override
	/**
	 * Inserisce un elemento in coda.
	 */
	public void enqueueEnd(Object e) {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p.prev = p.next = p;
			
		} else {
			p.next = fine;
			fine.next.prev = p;
			fine.next = p;
			fine = fine.next;
		}
	}

Ma neanche così va bene, mi confondo con i vari puntatori e non mi è del tutto chiaro il meccanismo..

[wingman87]

Ma quello che hai scritto non ha alcun senso
Non è difficile da tradurre in codice se hai capito la struttura a livello concettuale.
Inizio e fine puntano rispettivamente al primo e all'ultimo elemento. Se la coda è vuota non puntano a nulla. Se la coda contiene un solo elemento ovviamente inizio e fine puntano allo stesso elemento.
Il precedente di ogni nodo punta al precedente a meno che l'elemento è in testa, nel qual caso punta a null. Il successivo di ogni nodo punta al successivo a meno che l'elemento è alla fine nel qual caso punta a null.
Quando viene inserito un elemento in testa questo diventa il nuovo inizio. Il "vecchio inizio" diventa il suo successore, inoltre il "nuovo inizio" diventa il predecessore del "vecchio inizio". Ragionamento analogo quando inserisci un elemento in coda.

[PHØΞИIX]

Prova così.. Dovrebbe funzionare.. E ricordati di definire il lancio delle eccezioni nell'interfaccia..

public class CodaDoppiaCollegata implements CodaDoppia {
    
	private Record inizio = null; //Punta all'elemento in testa
	private Record fine = null; ////Punta all'elemento in coda
	
	private class Record {
		public Object elem;
		public Record next; //Punta all'elemento successivo
		public Record prev; //Punta all'elemento precedente
		
		public Record(Object e) {
			elem = e;
			next = prev = null;
		}
	}

	@Override
    /**
	 * Inserisce un elemento in testa.
	 */
	public void enqueueStart(Object e) throws EccezioneStrutturaVuota {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p;
			
		} else {
            p.next = inizio;
            inizio.prev = p;
            inizio = p;
		}
	}

	@Override
    /**
	 * Inserisce un elemento in coda.
	 */
	public void enqueueEnd(Object e) throws EccezioneStrutturaVuota {
		Record p = new Record(e);
		
		if(isEmpty()) {
			inizio = fine = p;
			
		} else {
            fine.next = p;
            p.prev = fine;
			fine = p;
		}
	}

	@Override
    /**
	 * Rimuove l'elemento in testa.
	 */
	public void dequeueStart() throws EccezioneStrutturaVuota {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		inizio = inizio.next;
        inizio.prev = null;
	}

	@Override
    /**
	 * Rimuove l'elemento in coda.
	 */
	public void dequeueEnd() throws EccezioneStrutturaVuota {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		fine = fine.prev;
        fine.next = null;
	}

	@Override
    /**
	 * Verifica se la coda e' vuota.
	 */
	public boolean isEmpty() throws EccezioneStrutturaVuota {
		return (inizio == null) && (fine == null);
	}

	@Override
    /**
	 * Restituisce l'elemento in testa.
	 */
	public Object first() throws EccezioneStrutturaVuota {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		return inizio.elem;
	}

	@Override
    /**
	 * Restituisce l'elemento in coda.
	 */
	public Object last() throws EccezioneStrutturaVuota {
		if(isEmpty())
			throw new EccezioneStrutturaVuota("CODA VUOTA!");
		
		return fine.elem;
	}
	
	private static void inizializza(CodaDoppiaCollegata doubleQueue) throws EccezioneStrutturaVuota {
		doubleQueue.enqueueStart("secondo");
		doubleQueue.enqueueStart("primo");
		doubleQueue.enqueueEnd("terzo");
		doubleQueue.enqueueEnd("quarto");
	}
	
	public static void main(String args[]) {
		
		CodaDoppiaCollegata test = new CodaDoppiaCollegata();
        try {
		inizializza(test);
		System.out.println(test.first());
		System.out.println(test.last());
		test.dequeueStart();
		System.out.println(test.first());
		test.dequeueEnd();
		System.out.println(test.last());
        } catch (EccezioneStrutturaVuota ex) {
            System.out.println(ex.getMessage());
        }
	}

}

[michelexeno]

Originariamente inviato da wingman87

Inizio e fine puntano rispettivamente al primo e all'ultimo elemento.

Il successivo di ogni nodo punta al successivo a meno che l'elemento è alla fine nel qual caso punta a null.

Grazie mille a entrambi!!Anche se avevo letto come funzionano inizio e fine, non li consideravo come gli elementi stessi che sono in coda o in testa e poi non mi era chiaro il "verso" degli elementi in coda.
Grazie e buone feste

[wingman87]

Occhio che nel codice di PHØΞИIX c'è un problema nei dequeue: quando la coda contiene un solo elemento vanno in errore.

[michelexeno]

Originariamente inviato da wingman87

Occhio che nel codice di PHØΞИIX c'è un problema nei dequeue: quando la coda contiene un solo elemento vanno in errore.

Si l'ho modificato, grazie ancora