Coda: implementare il metodo delete

[Bombonera]

Salve,

Devo creare una coda e quindi ho implementato due puntatori di tipo Nodo<E>. Il primo punta al primo nodo della lista (head) e il secondo all'ultimo nodo della lista(tail).

Non ho capito come posso implementare il metodo delete, cioè il metodo che elimina l'ultimo elemento della lista (cioè quello puntato da tail) e restituisce l'elemento generico E.

So che per eliminare l'ultimo nodo devo selezionare il penultimo nodo e settare next a null. Ma siccome tail punta all'ultimo nodo a cosa mi serve ? Cioè dovrei far andare tail indietro di un nodo e impostare next a null. Ora come faccio ciò ?

Grazie.

[andbin]

Devo creare una coda e quindi ho implementato due puntatori di tipo Nodo<E>. Il primo punta al primo nodo della lista (head) e il secondo all'ultimo nodo della lista(tail).

Ma la coda è "doppiamente linkata" (con next/previous nei nodi) oppure no? Perché se no, il tail generalmente è utile solo per l'aggiunta veloce in coda, visto che non puoi tornare indietro.

[Bombonera]

Ma la coda è "doppiamente linkata" (con next/previous nei nodi) oppure no? Perché se no, il tail generalmente è utile solo per l'aggiunta veloce in coda, visto che non puoi tornare indietro.

No, non è doppiamente linkata. I nodi hanno solo due campi: uno per memorizzare un dato e un'altro per puntare il nodo successivo (next).

Non vedo l'utilità del puntatore tail. Forse c'è bisogno di un puntatore ausiliare che precede tail ?

[Bombonera]

Comunque per andare indietro si dovrebbe fare:

tail = head

e iterare tail fino alla fine della coda. Il fatto è che tail per eliminare l'ultimo nodo dovrebbe puntare al penultimo nodo.

Forse è come dici tu, devo creare una lista con due puntatori per nodo. Non lo so.

[andbin]

Non vedo l'utilità del puntatore tail.

In una lista "singolarmente" linkata il tail è utile, ma come ho detto solo per poter aggiungere velocemente in coda.

Forse c'è bisogno di un puntatore ausiliare che precede tail ?

Tecnicamente certo che si può fare (non è molto tipico) ma complica la gestione, devi far quadrare tutto e in tutti i casi e le operazioni.

L'alternativa è la (ovvia) scansione dal head.

[Bombonera]

Quindi devo mettere per forza due puntatori per nodo ?

[Bombonera]

PASSO-1.jpg
PASSO - 2.jpg

PASSO - 3.jpg

[Bombonera]

va be le immagini sono troppo piccole. Quindi devo implementare una lista doppiamente concatenato. Ho capito. Grazie!!.

[andbin]

Quindi devo implementare una lista doppiamente concatenato.

Se vuoi rimuovere velocemente il nodo in coda .. sì. Altrimenti se non ti interessa questo aspetto, puoi scansionare partendo dal head.