Dubbio sulle liste concatenate

[Dreamer89]

Salve. Ho ricopiato da un libro i seguenti sorgenti che mi permettono di aggiungere e rimuovere dei valori da una lista concatenata:

package cap7;

class ListNode
{
	Object data;
	ListNode nextNode;
	
	ListNode (Object object)
	{
		this (object, null);
	}
	
	ListNode (Object object, ListNode node)
	{
		data = object;
		nextNode = node;
	}
	
	Object getObject ()
	{
		return data;
	}
	
	ListNode getNext ()
	{
		return nextNode;
	}
}

public class List
{
	private ListNode firstNode;
	private ListNode lastNode;
	private String name;
	
	public List ()
	{
		this ("list");
	}
	
	public List (String listName)
	{
		name = listName;
		firstNode = lastNode = null;
	}
	
	public void insertAtFront (Object insertItem)
	{
		if (isEmpty ())
		{
			firstNode = lastNode = new ListNode (insertItem);
		}
		else
		{
			firstNode = new ListNode (insertItem, firstNode);
		}
	}
	
	public void insertAtBack (Object insertItem)
	{
		if (isEmpty ())
		{
			firstNode = lastNode = new ListNode (insertItem);
		}
		else
		{
			lastNode = lastNode.nextNode = new ListNode (insertItem);
		}
	}
	
	public Object removeFromFront () throws EmptyListException
	{
		if (isEmpty ())
		{
			throw new EmptyListException (name);
		}
		
		Object removedItem = firstNode.data;
		
		if (firstNode == lastNode)
		{
			firstNode = lastNode = null;
		}
		else
		{
			firstNode = firstNode.nextNode;
		}
		
		return removedItem;
	}
	
	public Object removeFromBack () throws EmptyListException
	{
		if (isEmpty ())
		{
			throw new EmptyListException (name);
		}
		
		Object removedItem = lastNode.data;
		
		if (firstNode == lastNode)
		{
			firstNode = lastNode = null;
		}
		else
		{
			ListNode current = firstNode;
			
			while (current.nextNode != lastNode)
			{
				current = current.nextNode;
			}
			
			lastNode = current;
		}
		
		return removedItem;
	}
	
	public boolean isEmpty ()
	{
		return firstNode == null;
	}
	
	public void print ()
	{
		if (isEmpty ())
		{
			System.out.printf ("Empty %s\n", name);
			return;
		}
		
		System.out.printf ("The %s is : ", name);
		ListNode current = firstNode;
		
		while (current != null)
		{
			System.out.printf ("%s ", current.data);
			current = current.nextNode;
		}
		
		System.out.println ("\n");
	}
}

package cap7;

public class EmptyListException extends RuntimeException
{
	public EmptyListException ()
	{
		this ("List");
	}
	
	public EmptyListException (String name)
	{
		super (name + " is empty");
	}
}

import cap7.*;

public class ListTest
{
	public static void main (String[] args)
	{
		List list = new List ();
		
		list.insertAtFront (-1);
		list.print ();
		list.insertAtFront (0);
		list.print ();
		list.insertAtBack (1);
		list.print ();
		list.insertAtBack (5);
		list.print ();
		
		try
		{
			Object removedObject = list.removeFromFront ();
			System.out.printf ("%s removed\n", removedObject);
			list.print ();
			
			removedObject = list.removeFromFront ();
			System.out.printf ("%s removed\n", removedObject);
			list.print ();
			
			removedObject = list.removeFromBack ();
			System.out.printf ("%s removed\n", removedObject);
			list.print ();
			
			removedObject = list.removeFromBack ();
			System.out.printf ("%s removed\n", removedObject);
			list.print ();
		}
		catch (EmptyListException e)
		{
			e.printStackTrace ();
		}
	}
}

Il programma funziona perfettamente, ma quello che non mi è chiaro è: quando vengono stampati tutti gli oggetti concatenati, noi ci spostiamo prendendo come riferimento solo firstNode. Ora, come è possibile che utilizzando solo quello, riusciamo a stampare anche i valori di lastNode? Eppure sono due oggetti diversi!

[index]

Nel metodo print() di ListNode Lei ha inserito questo statement:

current = current.nextNode; 

Quando non ci sono più nodi nella lista, il metodo nextNode() le restituisce NULL e lo assegna alla variabile current.
Nel ciclo while ha, pertanto, realizzato un controllo sul valore NULL di current. Ciò significa che il ciclo va avanti finchè il valore di current è diverso da NULL.
Nel caso in cui i nodi finiscono, il controllo nel while risulta vero e il ciclo si interrompe.

Spero di essere stato chiaro.
Saluti.

[Dreamer89]

Quello che non mi è chiaro è:

Quando inseriamo valori davanti alla lista, questi vengono concatenati ad oggetti di firstNode. Quando invece inseriamo valori alla fine della lista, questi vengono concatenati ad oggetti di lastNode.

A current vengono assegnati gli oggetti concatenati di firstNode. Come è possibile che sempre con current vengono stampati anche quelli di lastNode? Eppure l'ultimo oggetto di firstNode finisce con NULL, quindi non può essere collegato al primo di lastNode...

[index]

Ok. Penso di aver capito. Quello che probabilmente Le sfugge è che in realtà quelle variabili delle quali lei parla contengono solo dei riferimenti "dinamici".

Saluti.

[andbin]

Originariamente inviato da Dreamer89
A current vengono assegnati gli oggetti concatenati di firstNode. Come è possibile che sempre con current vengono stampati anche quelli di lastNode? Eppure l'ultimo oggetto di firstNode finisce con NULL, quindi non può essere collegato al primo di lastNode...

Le variabili di tipo "reference", contengono appunto solamente un "riferimento" ad un oggetto e basta. Cosa sia e cosa contenga realmente, a livello di bit, una variabile reference non è importante per il programmatore ... è un dettaglio implementativo che riguarda esclusivamente la JVM.
Basta solo sapere che contiene un riferimento ad un oggetto (o =null, cioè non fa riferimento ad alcun oggetto).

Le tue variabili firstNode, lastNode (di istanza) e current (locale in print() ) non hanno nulla a che fare direttamente tra di loro.

Quando la lista è vuota, firstNode e lastNode sono null. Se la lista contiene 1 elemento, allora è il caso (particolare) in cui firstNode e lastNode fanno riferimento allo stesso oggetto. Se la lista contiene più elementi allora le due variabili faranno certamente riferimento ad oggetti diversi, il primo oggetto in testa e l'ultimo oggetto in coda.

Quando in print() fai:

ListNode current = firstNode;

stai semplicemente creando una variabile che inizialmente ha una copia del valore di firstNode, quindi subito fa riferimento allo stesso oggetto referenziato da firstNode.
Man mano che si cicla nel while, current farà riferimento ai vari oggetti presenti nella lista, ognuno preso dal "next" dell'oggetto corrente.

[index]

Originariamente inviato da andbin
Le variabili di tipo "reference", contengono appunto solamente un "riferimento" ad un oggetto e basta. Cosa sia e cosa contenga realmente, a livello di bit, una variabile reference non è importante per il programmatore ... è un dettaglio implementativo che riguarda esclusivamente la JVM.
Basta solo sapere che contiene un riferimento ad un oggetto (o =null, cioè non fa riferimento ad alcun oggetto).

Le tue variabili firstNode, lastNode (di istanza) e current (locale in print() ) non hanno nulla a che fare direttamente tra di loro.

Quando la lista è vuota, firstNode e lastNode sono null. Se la lista contiene 1 elemento, allora è il caso (particolare) in cui firstNode e lastNode fanno riferimento allo stesso oggetto. Se la lista contiene più elementi allora le due variabili faranno certamente riferimento ad oggetti diversi, il primo oggetto in testa e l'ultimo oggetto in coda.

Quando in print() fai:

ListNode current = firstNode;

stai semplicemente creando una variabile che inizialmente ha una copia del valore di firstNode, quindi subito fa riferimento allo stesso oggetto referenziato da firstNode.
Man mano che si cicla nel while, current farà riferimento ai vari oggetti presenti nella lista, ognuno preso dal "next" dell'oggetto corrente.

esattamente.

[Dreamer89]

Quindi in realtà, l'ultimo riferimento di firstNode che punta al suo ultimo oggetto, non ha valore NULL, ma continua a riferirsi agli oggetti rimanenti?

Perchè nel metodo insertAtFront() il primo oggetto rimane sempre a NULL... però quando poi stampiamo continua oltre questo valore. Non credo di essermi spiegato bene

[andbin]

Immaginiamo che nella lista ci siano 3 oggetti ListNode. Si ha la seguente struttura:

+-------+      +-------+      +-------+
|       |      |       |      |       |
|  next------->|  next------->   next----> null
+-------+      +-------+      +-------+
    ^                             ^
    |                             |
    |                             |
    |                             |
firstNode                      lastNode

'next' è la variabile di istanza nextNode.

[Dreamer89]

Quindi, se è capito bene, in una classe è possibile avere solo una lista concatenata? E qualsiasi oggetto di classe auto-referenziale si riferisce sempre e solo a questa unica lista?

[andbin]

Originariamente inviato da Dreamer89
Quindi, se è capito bene, in una classe è possibile avere solo una lista concatenata? E qualsiasi oggetto di classe auto-referenziale si riferisce sempre e solo a questa unica lista?

Francamente non ho capito .... cosa non hai capito.
Che cosa è che non ti è chiaro delle classi List e ListNode??