Implementare coda con una lista collegata; perché sarebbe male inserire alla testa e rimuovere in coda?

Question

Nel mio libro di testo, strutture dati e algoritmi in Java, l'autore dice in sede di attuazione di una coda utilizzando una lista collegata si sceglie la parte anteriore della coda per essere alla testa della lista, e la parte posteriore della coda di essere a la coda della lista. In questo modo, si rimuove dalla testa e inserto in coda.

L'autore poi chiede criptico: "Perché sarebbe male inserire alla testa e rimuovere in coda?" senza fornire una risposta.

Non riesco a vedere quale sia la differenza è in realtà. In effetti, "testa" e "coda" sono solo nomi arbitrari definiamo. Che cosa sarebbe male se a enqueue () aggiungiamo una testa e creiamo un riferimento alla vecchia testa, e per dequeue () prendiamo dalla coda e spostare la coda sopra?

Qual è la risposta alla domanda dell'autore?

Answer 1

In una sola lista collegata, ogni elemento ha un puntatore all'elemento successivo. Se si dispone di un puntatore aggiuntivo per l'elemento di coda, che vi porta le operazioni di un numero costante og al Aggiungi per la lista in coda: ottenere il puntatore coda, aggiungere un elemento dopo la coda, mettere questa nuova elemento nuova coda. La rimozione dalla testa prende anche un numero costante di operazioni:. Farvi nuovo elemento nuovo, la testa, scegliere vecchia testa

Tuttavia, rimozione dalla coda richiede un puntatore alla precedente alla coda corrente. Questo porta il maggior numero di operazioni in quanto vi sono elementi, vale a dire in modo lineare molti.

Un'altra soluzione è quella di utilizzare una lista doppiamente collegata, allora si può scegliere ciò che si vuole, ma utilizza il doppio della memoria.

Answer 2

Rimozione dalla testa e inserendo in coda sono operazioni di tempo costanti con una lista concatenata, assumendo puntatori testa e di coda. Inserimento in coda è anche costante di tempo. Ma la rimozione dai mezzi di coda spostando il puntatore di coda verso la testa, e dal momento che non si dispone di un puntatore indietro non si può farlo senza attraversare l'intera lista di trovare l'elemento precedente alla coda. Questo rende l'inserimento di un tempo lineare, invece di un'operazione costante di tempo e per questo è peggio.