[teorico] Sentinella nelle liste

[Neptune]

Scusatemi per questo dilemma più teorico che pratico ma riguarda la sentinella nella realizzazioni delle liste.

Leggendo di pari passo dal libro dice che la sentinella non è altro che una cella con un valore appunto sentinella (non assomibile dagli altri elementi della lista) piazzato come primo elemento, ovvero la testa punterà direttamente a questo primo elemento. E mi dice che mi favorirà le operazioni di cancellazione e di insert, ma non riesco a capire perchè?

Cioè che mi serve una sentinella come prima posizione? Tra l'altro utilizzato anche con liste monodirezionali?

[zucchino]

La sentinella puo' essere utile per almeno due motivi:
- anche inserendo o eliminando l'elemento in prima posizione della lista, la testa della lista non cambia mai (appunto perchè punta alla sentinella) quindi puoi evitare di far ritornare tale valore dalle funzioni che operano sulla lista stessa.
- non devi gestire i casi di inserimento e cancellazione in prima posizione in modo diverso dagli altri elementi (se non avessi la sentinella dovresti sempre controllare se la lista e' vuota oppure no)

[Neptune]

Originariamente inviato da zucchino
- non devi gestire i casi di inserimento e cancellazione in prima posizione in modo diverso dagli altri elementi (se non avessi la sentinella dovresti sempre controllare se la lista e' vuota oppure no)

Questa cosa non l'avevo pensata, ed è ottima come cosa, effettivamente questa possibilità per gestirla è stata una bella scocciatura.

Un'altra domanda sulle liste, secondo il corso teorico tra i vari operatori ho il metodo "inslista" che dovrebbe inserire un elemeneto prima della posizione "p" che gli viene passata. Dove la posizione è un indirizzo di memoria o un indice di un array.

Ora dice che in caso la lista è lunga N e gli viene passata la posizione N+1 deve praticamente accodare alla fine della lista. Quello che mi domandavo è "come gli passo la posizione N+1" ?
Cioè sugli array gli indici sono sequenziali e basta effettivamente sommare 1, ma se parliamo di una lista con puntatori, dove le posizioni sono locazioni di memoria, come faccio a sommargli 1?

[Celebron]

Originariamente inviato da Neptune
Questa cosa non l'avevo pensata, ed è ottima come cosa, effettivamente questa possibilità per gestirla è stata una bella scocciatura.

Un'altra domanda sulle liste, secondo il corso teorico tra i vari operatori ho il metodo "inslista" che dovrebbe inserire un elemeneto prima della posizione "p" che gli viene passata. Dove la posizione è un indirizzo di memoria o un indice di un array.

Ora dice che in caso la lista è lunga N e gli viene passata la posizione N+1 deve praticamente accodare alla fine della lista. Quello che mi domandavo è "come gli passo la posizione N+1" ?
Cioè sugli array gli indici sono sequenziali e basta effettivamente sommare 1, ma se parliamo di una lista con puntatori, dove le posizioni sono locazioni di memoria, come faccio a sommargli 1?

sommare? Guarda che nelle liste gli elementi sono allocati dinamicamente, quindi gli indirizzi dei vari elementi non sono certo sequenziali.
Per dire: non puoi usare testa++ per ottenere l'indirizzo al primo elemento.

Ogni elemento, di norma, ha un puntatore "next" che punta a quello successivo

quindi se vuoi aggiungere in coda è sufficiente che fai

temp = testa;
while(temp.next!=null)
    temp = temp.next;

all'uscita del while avrai quindi l'ultimo elemento presente in coda (e quindi l'unico il cui next punta a null) e potrai aggiungerci quello che vuoi

[Neptune]

Allora stiamo parlando del c++, ho una specifica che mi dice che se ho una coda lunga n ed ho una posizione p <= n, allora inserisco l'elemento prima della posizione p, se invece ho la posizione p = n+1 allora devo inserire in coda alla lista. Mi sfugge appunto, in una lista non sequenziale come possa fare ad avere una posizione n+1.

[Celebron]

come dici tu appunto esiste una coda della lista

lista != vettore

il vantaggio di usare le liste è per appunto il basso costo di aggiungere un elemento in testa (Senza dover riestendere nulla) o in coda (se usi un elemento pcoda che punta per appunto all'ultimo elemento)

l'ultimo elemento in fondo ad una lista è L'UNICO di tutta la lista il cui puntatore next è a null. Se ti chiede di aggiungere un elemento in coda, semplicemente una volta trovato l'ultimo elemento attuale (o con il ciclo while che ti ho mostrato o usando un puntatore ausiliario pcoda) semplicemente fai la malloc del nuovo elemento e fai
pcoda.next = nuovoelemento;
nuovoelemento.next = null;
pcoda = nuovoelemento;