[JAVA] Lista concatenata

[D4rkAng3l]

Ciao,
posto parte dell'esercitazione trovata sul sito della mia proff circa le liste concatenate in Java. Tale esercitazione prevede di implementare una lista concatenata tramite l'uso di 2 classi: una che rappresenta oggetti nodo ed una che rappresenta la lista vera e propria e che usa la classe nodo.

Ho qualche dubbio sulla correttezza del mio materiale didattico e spero che possiate illuminarmi

La classe NodoInt è:

/** Classe che rappresenta e gestisce singoli nodi di una lista concatenata; Gli oggetti sono MUTABILI */

public class NodoInt{
	private int valore;				// Valore di tipo intero contenuto nel nodo (è il campo informazione del nodo)
	private NodoInt successivo;		// Contiene il riferimento ad un oggetto di tipo NodoInt che contiene l'elemento successivo
	
	/** COSTRUTTORE :crea un nodo il cui valore è quello del parametro e che non è concatenato ad alcun altro nodo */

	public NodoInt(int n){
		valore = n;						// Nel campo valore del nuovo nodo creato viene messo il valore del parametro
		successivo = null;				// Nel campo successivo viene messo il valore null: il nuovo nodo non punta a niente
	}
	
	/** Accede in lettura al valore del nodo oggetto ricevente */
	
	public int getValore(){
		return valore;				// Ritorna il valore contenuto nel nodo oggetto ricevente
	}
	
	/** Accede in lettura al riferimento al nodo che segue il nodo oggetto ricevente. *NB: Espone l'oggetto ricevente a
	    possibili effetti collaterali */
	
	public NodoInt getSuccessivo(){
		return successivo;
	}
	
	/** Configura l'oggetto ricevente in modo tale da avere il parametro come successore. *NB: Modifica l'oggetto ricevente */
	
	public void setSuccessivo(NodoInt altro){
		this.successivo = altro;
	}
	
	/** Fornisce una rappresentazione in forma di stringa dell'oggetto ricevente */
	
	public String toString(){
		String s = " " + valore + "";
		
		if(successivo != null) s+= "->":
		
		return s;
	}
}

La casse ListaDiInteri (per ora ho messo solo i 2 metodi che a mio avviso potrebbeo essere sbagliati) è:

/** Classe che rappresenta e gestisce una lista concatenata di nodi che contengono valori interi; Gli oggetti sono MUTABILI */

public class ListaDiInteri{
	
	private NodoInt N;			// Primo nodo della lista
	
	/** COSTRUTTORE: Crea un nuovo oggetto ListaDiInteri che inizialmente è una lista vuota*/
	
	public ListaDiInteri(){
		N = null;				// Il primo nodo è inizialmente un elemento nullo
	}
	
	/** Se il nodo parametro non ha successori lo aggiunge in testa alla lista alla lista, altrimenti crea un nodo il cui
	    valore coincide con quello del parametro e lo aggiunge in testa alla lista. *NB: Modifica l'oggetto ricevente */
	  
	public void aggiungiInTesta(NodoInt altro){
		NodoInt T = new NodoInt(altro.getValore());	// Costruisce un nuovo nodo T avente il valore di altro
		T.setSuccessivo(N);			// Il nodo T è diventatola la nuova testa della lista e punta alla vecchia testa
		N = altro;
	}
	
	/** Crea un nodo il cui valore coincide con il parametro di tipo intero e lo aggiunge in testa alla lista.
	    *NB: Modifica l'oggetto ricevente */
	  
	public void aggiungiInTesta(int n){
		NodoInt T = new NodoInt(n);
		T.setSuccessivo(N);
		N = altro;
	}
}

Secondo me i due metodi aggiungiInTesta che appunto aggiungono in testa un nuovo nodo sono concettualmente sbagliati perchè:

1) Il primo dei due metodi prende come parametro un oggetto NodoInt di nome altro (per semplicità consideriamolo senza successori) e modifica l'oggetto ricevente (una lista) mettendolo in testa alla lista.

Per fare ciò crea un nodo T copia dell'oggetto altro ricevuto (copia il valore di altro nel campo valore del nuovo nodo T).
Poi modifica il campo successivo del nodo T appena creato e lo fà puntare alla lista N (praticamente lo fà puntare alla vecchia testa della lista N). Ok...fino quì tutto bene credo...la cosa che mi turba è l'istruzione:
N = altro;
Perchè?!?! altro era il parametro che era stato copiato in T...non dovrebbe essere:
N = T; ?!?!
Cioè ho creato un nuovo nodo T che contiene la copia di altro, ho fatto puntare T alla vecchia testa della lista N ed ora devo modificare N e dire che la nuova testa è T...

Anche nel secondo metodo mi impiccio su questa cosa...ha sbagliato la poff o sono io che non vedo qualcosa?

Grazie
Andrea

[wizard1993]

a me quel coso non compila

[D4rkAng3l]

Originariamente inviato da wizard1993

a me quel coso non compila

mmm che palle...ora a parte il compilare o meno...poi vedrò...volevo sapere se come ragionamento ho sbagliato io o è sbagliato l'esempio della proff...

[D4rkAng3l]

cmq non compilava la classe NodoInt perchè c'era un errore di punto e virgola.
E non compilava l'altra classe proprio perchè nel secondo metodo aggiungiInTesta c'è quel problema che io ritengo un errore...se lo metto così compila (anche se tra sintassi e semantica magari ce ne passa...)

public void aggiungiInTesta(int n){
		NodoInt T = new NodoInt(n);
		T.setSuccessivo(N);
		N = T;
	}

Però giustamente se gli metto N = altro; com'è sulle dispense...ma lui in questo secondo caso altro non sà proprio cosa sia...quindi mi fà sospettare sempre di più che il mio ragionamento sia giusto e che la lista N debba essere impostata con il riferimento all'oggetto T che è la nuova testa.

C'è qualcuno di ferrato che mi sà dare una risposta certa?

Grazie
Andrea

[Oceans11]

"Certamente" hai ragione tu!

Mi riferisco al primo metodo del codice che hai postato, per intenderci questo:

public void aggiungiInTesta(NodoInt altro){
	NodoInt T = new NodoInt(altro.getValore());
	T.setSuccessivo(N);
	N = altro;
}

Ritengo superfluo l'uso di T. Infatti avrei fatto:

public void aggiungiInTesta(NodoInt altro){
	altro.setSuccessivo(N);
	N = altro;
}

Ma dovendo passare per T, la soluzione giusta è quella che credi tu, ossia:

public void aggiungiInTesta(NodoInt altro){
	NodoInt T = new NodoInt(altro.getValore());
	T.setSuccessivo(N);
	N = T;
}

la prof ha evidentemente fatto un miscuglio pauroso tra le 2 soluzioni!

[D4rkAng3l]

Originariamente inviato da Oceans11

"Certamente" hai ragione tu!

Mi riferisco alla prima versione del codice che hai postato, per intenderci questa:

public void aggiungiInTesta(NodoInt altro){
	NodoInt T = new NodoInt(altro.getValore());
	T.setSuccessivo(N);
	N = altro;
}

Ritengo superfluo l'uso di T. Infatti avrei fatto:

public void aggiungiInTesta(NodoInt altro){
	altro.setSuccessivo(N);
	N = altro;
}

Ma dovendo passare per T, la soluzione giusta è quella che credi tu, ossia:

public void aggiungiInTesta(NodoInt altro){
	NodoInt T = new NodoInt(altro.getValore());
	T.setSuccessivo(N);
	N = T;
}

la prof ha evidentemente fatto un miscuglio pauroso tra le 2 soluzioni!

doh all'inizio mi ero spaventato leggendo il tuo codice

In pratica quando tu dici:

public void aggiungiInTesta(NodoInt altro){
	altro.setSuccessivo(N);
	N = altro;
}

praticamente gli passa il riferimento ad un nodo altro e gli imposta il campo successivo con il riferimento alla lista N e poi giustamente impone ad N il riferimento alla nuova testa che è altro...ok...

Cmq credo che anche gli altri metodi più complessi contengano vari chili di errori...di solito la proff è molto precisa ma credo che a questo giro ci sia andata un po' giù pesante con il copia e incolla....mettendoci dentro vari errori

[D4rkAng3l]

Al volo...quest'altro metodo invece mi sembra corretto:
Serve per inserire in una lista un certo nodo (o anche un'altra lista) ad una certa posizione i della lista di partenza.

Quindi se la mia lista inizialmente è:

LISTA A: 1 --> 2 --> 3 --> 4 --> 5 --> 6

ed in posizione i=3 gli voglio inserire la lista:
LISTA B: 50 -->97 --> 120

alla fine avrò la lista:

1 --> 2 --> 3 --> 50 -->97 --> 120 --> 4 --> 5 --> 6

Quindi in pratica mi devo scorrere la lista A fino all'i-esimo elemento e registrarmi il riferimento all'i+1-esimo elemento.

Devo collegare all'ultimo elemento della lista B tale i+1esimo riferimento di A che mi ero registrato.

E poi devo far puntare l'i-esimo elemento della lista A alla testa della lista B.

In codice questo dovrebbe andare bene?

/** Aggiunge il nodo parametro (con i suoi eventuali succesori) all'interno della lista nella posizione specificata
	    dal secondo parametro. *NB: Modifica l'oggetto ricevente */
	    
	public int aggiungiInPosizione(NodoInt altro, int i){
		NodoInt T = N;			// Metti in T il riferimento alla lista N
		NodoInt S;
		int conta = 0;
		
		if(N == null){			// Se la lista N è una lista vuota
			
			if(i == 0) aggiungiInTesta(altro);	// e se il parametro i è pari a 0 metti il nodo altro in testa alla lista
			else conta = -1;					// altrimenti situazione di errore
		}
		else{	// Se la lista N non è vuota
			while(T.getSuccessivo() != null && conta < i-1){	// finchè non è finita la lista o non si è superato la posizione i
				conta++;						// Incrementa conta
				T = T.getSuccessivo();			// Passa al prossimo nodo della lista
			}
		
			S = altro;	// Memorizza in S il riferimento alla testa dell'altra lista da inserire nell'i-esima posizione	della lista N
			
			while(S.getSuccessivo() != null){		// Scorri la lista da aggiungere fino al suo ultimo elemento
				S = S.getSuccessivo();				// e memorizza il riferimento all'ultimo elemento in S
			}
			
			S.setSuccessivo(T.getSuccessivo());	  // Collega l'ultimo elemento della lista da inserire al primo della seconda metà di N
			T.setSuccessivo(altro);
		}
			
		return conta;
	}

Chiedo conferma visto che questa esercitazione non è assolutamente commentata ed è pienza zeppa di errori...vediamo se ho capito bene...

Grazie
Andrea

[Oceans11]

Originariamente inviato da D4rkAng3l

doh all'inizio mi ero spaventato leggendo il tuo codice
In pratica quando tu dici:

public void aggiungiInTesta(NodoInt altro){
	altro.setSuccessivo(N);
	N = altro;
}

praticamente gli passa il riferimento ad un nodo altro e gli imposta il campo successivo con il riferimento alla lista N e poi giustamente impone ad N il riferimento alla nuova testa che è altro...ok...

Esatto! sinceramente non ho capito il perchè dell'esistenza di T : in questo modo infatti, per ogni nodo che vuoi inserire, ne crei 1, lo copi in un altro, poi inserisci quest'ultimo. Insomma è un ghirigoro assurdo!

Se per gli altri metodi hai dubbi, posta pure, magari trovi una spiegazione od una soluzione

[D4rkAng3l]

Originariamente inviato da Oceans11

Esatto! sinceramente non ho capito il perchè dell'esistenza di T : in questo modo infatti, per ogni nodo che vuoi inserire, ne crei 1, lo copi in un altro, poi inserisci quest'ultimo. Insomma è un ghirigoro assurdo!

Se per gli altri metodi hai dubbi, posta pure, magari trovi una spiegazione od una soluzione

eheh ti ho anticipato ed al precedente post te ne ho mandato un altro per chiedere conferma...sei molto gentile, ti ringrazio :-)

[Oceans11]

Il codice mi sembra corretto, il tuo ragionamento lo è di sicuro!

[D4rkAng3l]

pfff...continuo a spremermi le meningi con la stupida classe della proff...che più vado avanti...più mi pare fatta ad cazzum

Sempre nella stessa classe questa volta vuole implementare un metodo che: se la lista non è vuota rimuove il nodo della lista che si trova in posizione i specificata dal parametro.

A casa mia fare questo significa questo, ho una lista:

10 --> 34 --> 77 --> 32 --> 11 -> 19

Voglio eliminare l'elemento in posizione 3 e la lista viene modificata in:

10 --> 34 --> 32 --> 11 -> 19

In pratica se elimino l'elemento in posizione 3 basta mettere il riferimento del quarto nodo nel campo successivo del secondo...ed il terzo nodo si va a farsi benedire nella mia lista concatenata....

Lei fa questo, che per me è SBAGLIATO:

/** Se la lista è non vuota e se la lista contiene un numero sufficiente di elementi, rimuovere il nodo della lista che
	    si trova nella posizione specificata dal parametro. *NB: Modifica l'oggetto ricevente */
	    
	public int rimuovereDaPosizione(int i){
		NodoInt T;
		int conta = 0;
		
		if(N==null) conta = -1;		// Se la lista N è vuota, metti in conta il valore di situazione d'errore
		else{						// Altrimenti se la lista N non è vuota
			if(N.getSuccessivo()==null){	// Se contiene un solo elemento
				if(i==1) N = null;			// e se bisgonava eliminare la testa, rendi vuota la lista N
				else conta = -1;			// altrimenti metti il conta il valore di situazione d'ettore
			}
			else{					// Se invece la lista contiene più di un elemento
				T = N;				// Metti in T il riferimento alla testa della lista N
				while(T.getSuccessivo() != null && T.getSuccessivo().getSuccessivo() != null && conta<i-1){
					conta ++;
					T = T.getSuccessivo();		// Scorri la lista fino all'i-1esimo elemento
				}
				T.setSuccessivo(null);
			}
		}
			return conta;
	}

Vabbè se la lista N è vuota...mette in conta il valore d'errore -1 OK

Se la lista non è vuota ma contiene un solo elemento ed io volevo togliere proprio la testa della lista mi trasforma N nella lista vuota...altirmenti mette in conta -1 perchè è una situazione di errore...OK

Se la lista N invece contiene più di un elemento mette in T il riferimento alla lista N (perchè?per poterla scorrere ed avere sempre in N il riferimento alla testa?)...inizia a scorrere la lista fino all'i-1esimo elemento e di questo setta a NULL il campo successivo....

Ma così NON HA ELIMINATO L'i-esimo elemento....HA ELIMINATO TUTTI I NODI a partire dall'i-esimo...

Se io ad esempio volevo eliminare il terzo elemento della precedente lista ora avrei:

10 --> 34

e non 10 --> 34 --> 32 --> 11 -> 19 come dovrebbe essere.

E' corretto o mi sò perso qualcosa?

Secondome dovrei mettere dentro il campo "successivo" dell'i-1esimo elemento il riferimento all'i+1esimo e così avrei correttamente eleiminato l'iesimo senza stravolgere la lista...

Che palle...le liste sono un argomento ostico...e questa è l'unica dispensa fatta di merda su tutte quelle del corso che sono ottime

[Oceans11]

Hai di nuovo ragione tu!

Dovendo eliminare quello in posizione i, ed ammettendo che stai puntando attualmente il nodo in posizione i-1 (chiamiamolo aux), dovresti fare:

aux.setSuccessivo() = aux.getSuccessivo().getSuccessivo();

Originariamente inviato da D4rkAng3l

Se la lista N invece contiene più di un elemento mette in T il riferimento alla lista N (perchè?per poterla scorrere ed avere sempre in N il riferimento alla testa?)...inizia a scorrere la lista fino all'i-1esimo elemento[...]

anche qui è tutto giusto, pure il ragionamento sull'utilizzo di T (quello che io ho chiamato "aux"), poi la tua prof si perde