[C] - code/queue e nodo sentinella

[ilgrigio]

salve gente, secondo voi ha senso inserire un nodo sentinella(fittizio) in una coda (queue) normale.
Se inserisco alla fine della coda e elimino all'inizio, dove lo piazzo sto nodo sentinella?

[sottovento]

Originariamente inviato da ilgrigio

salve gente, secondo voi ha senso inserire un nodo sentinella(fittizio) in una coda (queue) normale.
Se inserisco alla fine della coda e elimino all'inizio, dove lo piazzo sto nodo sentinella?

Normalmente i nodi sentinella vengono usati durante le ricerche: quando sei obbligato a scandire tutti i nodi (per esempio, la lista non e' ordinata, quindi la ricerca e' O(n)), piazzi la sentinella ALLA FINE, in modo che venga sempre trovata.
Questo ti permette di fare meno controlli nel ciclo di ricerca, riducendo il tempo di ciclo. Ovviamente la ricerca e' ancora O(n) poiche' kO(n) = O(n) ma all'atto pratico ne puoi avere dei benefici.

E' quindi evidente che il nodo sentinella lo devi mettere alla fine, se scandisci da testa a coda...

High Flying
Sottovento