In una lista ordinata, gli elementi sono inseriti in modo che la lista sia costituita da una sequenza ordinata di elementi.
La struttura su cui andremo a lavorare sarà così composta:

typedef int t_atomo;
 
typedef
struct listaord
{
t_atomo info;
struct listaord *prox;
} t_listaord;

Si tratta di una struttura ricorsiva, con un campo info e un puntatore al suo nodo successivo. Questa struttura ricorsiva non ha uno spazio di memoria preallocato, saremo noi ad allocare dinamicamente ogni nuovo elemento e a collegarli in modo opportuno.

Algoritmo di inserimento di un elemento in una lista ordinata:

//INSERIMENTO IN UNA LISTA ORDINATA:  C.computazionale: O(n)
 
int in_lista_ordinata(t_listaord **p, t_atomo x){ // Inserisce in una lista p, un elemento x
t_listaord *temp, *prec, *corr;
temp = (t_listaord *) malloc(ziseof(t_listaord)); //Al solito, allochiamo un blocchetto di memoria in temp, che collegheremo alla lista ordinata.
 
if(temp){ //Se l'allocazione di memoria avviene con successo
temp->info = x; //Inserisce nel campo info, il valore X.
temp->prox = NULL; //Mentre prox lo fa puntare a NULL.
 
if (*p){ //Se la lista è diversa da NULL vorrà dire che vi saranno altri elementi. 
prec = NULL; //precedente lo fa diventare uguale a NULL. (perchè dato che partiremo dal nodo iniziale della lista, il suo precedente non esisterà e sarà uguale a NULL)
corr = *p; //corrente diventa uguale a *p (quindi partiamo dall'inizio della lista)
while((corr) && (corr->info < x)){ //finchè corr è diverso da NULL e il campo info di corr è < di x: 
prec = corr; //Il prcedente diventa il corrente.
corr = corr->prox; //il corrente diventa il successivo: corr->prox
}
 
//uscendo dal ciclo sopra avremo scansionato tutta la lista, e quindi corr è diventato NULL giungendo alla fine oppure è stato trovata la posizione dove inserire x.
if (prec) //Se prec è diverso da NULL (effettuiamo il controllo su prec e non su corr perchè corr potrebbe essere diventato uguale a NULL (in quel caso vorrà dire che dobbiamo inserire x alla fine della lista)).
{ //Se prec non è NULL, allora avremo trovato una posizione di mezzo in cui inserire l'elemento x. Di conseguenza inseriamo temp fra prec e corr.
prec->prox = temp; //Il campo prox di prec, punterà a temp.
temp->prox = corr; //Il campo prox di temp punterà a corr. in questo modo temp sarà perfettamente innestato fra i due.
}else{ //Se prec è NULL vorrà dire che X è minore del primo elemento in lista, di conseguenza diventa il primo elemento della lista.
temp->prox = *p; //il campo prox punterà al vecchio primo nodo della lista
*p = temp; //temp diventa il primonodo.
}
 
}else //Altrimenti se la lista è vuota, semplicemente vi inserisce temp (senza modificare il suo campo prox che punterà a NULL. 
*p = temp;
 
return 0; //Inserimento avvenuto con successo
}else //Allocazione di temp non riuscita
return 1;
}

Algoritmo di Ricerca in una lista ordinata:

//RICERCA IN UNA LISTA ORDINATA: C. computazionale: O(n), come una ricerca sequenziale.
 
t_listaord *ricerca_listaord(t_listaord *p, t_atomo x){ //mettiamo l'asterisco perchè deve restituire l'indirizzo di memoria in cui trova l'elemento.
t_listaord *prec, *corr; //ci dichiariamo prec e corr.
prec = NULL; //prec lo inizializziamo a null
corr = p; //corri lo inizializziamo al puntatore p.
while((corr) && (corr->info < x)){ //finchè corr è diverso da NULL e finchè non trova un elemento maggiore uguale a x.
prec = corr; //il precedente diventa il corrente
corr= corr->prox; //il corrente diventa il successivo.
}
 
//Uscendo dal ciclo sopra, se corr diventa uguale a NULL avremo scansionato tutto l'array senza trovarlo. Altrimenti se l'altra condizione diventa falsa, avremo trovato un elemento maggiore o uguale a x (che potrebbe essere uguale a x o semplicemente maggiore, in quest'ultimo caso non avremo altre possibilità di trovarlo perchè la lista è ordinata e se c'era doveva trovarsi la).
if (corr && (corr->info == x)) //se corr è diverso da null è il campo info di corr è uguale a x
return corr; //Elemento trovato. Restituisce corr.
else
return NULL; //Elemento non trovato. Restituisce NULL.
 
}