[C] LinkedList - inserire elementi già in ordine

[ka0s]

Avrei bisogno di creare una linked list la quale, dopo ogni inserimento di un nuovo nodo, risulti già ordinata. Per cui l'operazione di inserimento deve mettere il nodo già nella sua posizione corretta.
Sapete se ci sono modi efficienti per fare un'operazione del genere o magari conviene inserire tutti i nodi disordinati e poi ordinarli in seguito (al momento che servono ordinati)?
tnx!

[yorkeiser]

Direi che a spanne l'algoritmo più efficiente (oltre che probabilmente più semplice) è quello di effettuare l'ordinamento già in fase di inserimento: ovvero per inserire un elemento scorri la lista, salvandoti il puntatore all'elemento precedente; quando arrivi ad un elemento maggiore di quello che stai inserendo (supposto che è questa la regola di ordinamento), fai puntare il puntatore salvato all'elemento che stai inserendo, e questo all'elemento attuale della lista.

[ka0s]

ok grazie, era l'idea che avevo anche io... solo che mi dava dei problemi perchè non tenevo conto del fatto che un elemento può finire in testa o in coda alla lista (oltre che in mezzo a due elementi). Per cui ho dovuto distinguere i tre casi... credo non ci siano altri metodi no?
Si accettano consigli

[AMD_GO]

Originariamente inviato da yorkeiser

Direi che a spanne l'algoritmo più efficiente (oltre che probabilmente più semplice) è quello di effettuare l'ordinamento già in fase di inserimento: ovvero per inserire un elemento scorri la lista, salvandoti il puntatore all'elemento precedente; quando arrivi ad un elemento maggiore di quello che stai inserendo (supposto che è questa la regola di ordinamento), fai puntare il puntatore salvato all'elemento che stai inserendo, e questo all'elemento attuale della lista.

Quoto, se devi usare una lista ordinata questo metodo va benissimo, solo che hai un tempo di inserimento un pò scarso (O(n) nel caso peggiore). Altrimenti sei costretto ad implementarti un'altra struttura....poi se non ti interessa il tempo di esecuzione le cose cambiano...

[ka0s]

Originariamente inviato da AMD_GO

Quoto, se devi usare una lista ordinata questo metodo va benissimo, solo che hai un tempo di inserimento un pò scarso (O(n) nel caso peggiore). Altrimenti sei costretto ad implementarti un'altra struttura....poi se non ti interessa il tempo di esecuzione le cose cambiano...

sinceramente il tempo di esecuzione ora come ora non mi interessa più di tanto (quello attuale va piu che bene!), però giusto per curiosità ci sarebbe un'altra struttura dati che mi permette degli inserimenti (e cancellazioni) come la lista, ma che sia piu efficiente?

[yorkeiser]

Dipende da cosa devi fare, ma le liste puoi salvarle benissimo su degli array, piuttosto che con dei record puntati