[Dati e Algoritmi] Lista con posizione astratta

[absinth]

Ciao a tutti! Chiedo un aiuto con il seguente problema "teorico". Considerando una lista con posizioni astratte (non so se sia un concetto diffuso, come l'ho capito io qui grazie all'incapsulamento si ispeziona usando la posizione, un oggetto che offre pubblico solo il metodo getElement() ). Se non è chiaro o non è sempre uguale nel mondo dell'informatica ditemi che lo spiego meglio.
Dopo aver letto questa slide la mia domanda è...
[img]http://i.imgur.com/kDoW37O.png?2[/img]

Come faccio ad avere quel metodo per la verifica dell'appartenenza in passato o presente di quella posizione all'oggetto list con prestazione Theta(1)? Non sono riuscito a trovare un trucco ma pensando per esempio alla posizione numerica di un array, si potrebbe semplicemente salvare ogni volta la posizione massima dentro l'oggetto e tenerla per il futuro anche quando viene cancellata, per poi fare il confronto con un eventuale posizione esterna per capire se era mai esistita.
Pensando al caso astratto forse un altro modo è quello di salvare nelle posizioni la lista di appartenenza ma là toccherebbe andare sul costruttore e fare altre cose strane con tante modifiche...
Qualcuno sa per caso in cosa consiste il trucco? O un altro modo che soddisfi tale condizione?

Se non è chiaro in questo caso cosa si intende per posizione astratta:

[img]http://i.imgur.com/tMb4uL6.png?1[/img]

[apatriarca]

Il trucco può essere quello di associare in qualche modo la posizione alla lista. Se la lista è rappresentata insomma da una classe Lista, puoi avere un campo privato di tipo WeakReference all'interno dell'implementazione della tua posizione contenente un riferimento alla lista.

[absinth]

puoi avere un campo privato di tipo WeakReference all'interno dell'implementazione della tua posizione

Intanto grazie mille per la risposta! Non ho presente comunque cosa sia questo weakreference e come implementarlo. Se può brevemente spiegarmelo o darmi un riferimento a qualche spiegazione mi farebbe un gran piacere. Qui in ogni caso dovrei applicarlo all'oggetto creato, quindi forse dovrei usare "this" in qualche modo? Dentro la posizione pensavo a questo ma non sono sicuro...

private WeakReference<Lista> ref = new WeakReference<Lista>(this);
public WeakReference<Lista> getRef()
{ 
    return ref;
}

[apatriarca]

Non credo sia possibile implementarlo, è qualcosa reso disponibile dal linguaggio. Se hai idea di cosa sia il garbage collector, allora si può brevemente descrivere come un riferimento ad un oggetto che non impedisce all'oggetto di essere eliminato dal garbage collector. Se non sai cosa sia allora il discorso si fa un po' troppo lungo. Un'alternativa è quella di mantenere un intero univoco alla particolare lista.

[absinth]

ma il codice è giusto che ho scritto sopra? se è sbagliato dove ho sbagliato? (dovrebbe essere dentro la classe position)

[apatriarca]

No, hai bisogno di qualcosa che rappresenti la lista come sequenza di posizioni, la classe posizione rappresenta solo un nodo di essa. Nota che se tutto quello che hai di una lista sono le posizioni cioè interpreti il caso in cui scambi due nodi di due liste diverse?

[absinth]

Si, considero due nodi di due liste diverse. Però non va bene cosi come ho fatto prima infatti me l'ha fatto capire perché "this" si riferisce alla posizione, classe interna alla classe lista, quindi devo salvare nell'oggetto posizione un riferimento all'oggetto di tipo lista al quale appartiene. Se la classe esterna a Position fosse "Lista" allora dovrei fare Lista.this per WeakReference:

public class Lista 
{  
     ....
     public class Position
     {
                    ....
                    private WeakReference<Lista> ref = new WeakReference<Lista>(Lista.this);
                    public WeakReference<Lista> getRef()
                            { 
                                   return ref;
                            }
                    ....
     }
}

e dopo in un codice esterno avendo più liste di tipo Lista, se voglio verificare che la posizione che ho ricevuto appartenga a una certa lista basta che verifichi il riferimento no? è giusto il ragionamento?

[apatriarca]

No, this è legato ad una istanza, non alla classe. Quel valore va inizializzato nel costruttore della classe. Ma tutto ciò è per lo più astratto e inutile. In primo luogo perché non c'è alcuna ragione per implementare una lista in un linguaggio come Java. E poi perché la scelta delle strutture dati e degli algoritmi va fatta in base al problema che si cerca di risolvere o diventa un puro esercizio mentale. Prima di cercare di risolvere questo problema dovresti chiederti perché sei interessato a rispondere a quella domanda e se stai usando la giusta struttura dati. Non esistono risposte corrette o sbagliate in programmazione. A patto che funzioni cine dovrebbe, tutto è corretto.