Se vuoi questa è un'implementazione abbastanza completa...
Ti basta sostituire la definizione di Info_t, compare e printList...
Notare che puoi utilizzare diverse funzioni come funzione per comparare, perciò puoi usare più criteri per rimuovere, cercare o inserire.
Utilizzando solo insert (sempre con la stessa funzione) avrai una lista ordinata secondo il criterio della funzione.
Il main è solo codice di test.
codice:
#include <stdio.h>
#include <stdlib.h>
 
typedef int Info_t;
typedef struct List_t {
    Info_t info;
    struct List_t *next;
} List_t;
 
typedef List_t *List;
typedef int (*compare_f)(Info_t, Info_t);
 
List cons(List *l, Info_t inf) {
    List tmp = (List)malloc(sizeof(List_t));
    tmp->info = inf;
    tmp->next = (*l);
    (*l) = tmp;
    return tmp;    
}
 
List insert(List *l, Info_t inf, compare_f f) {
    if((*l)==NULL)
        return cons(l, inf);
    List tmp;
    if(f(inf, (*l)->info) <= 0) {
        tmp = (List)malloc(sizeof(List_t));
        tmp->info = inf;
        tmp->next = (*l);
        (*l) = tmp;
        return tmp;
    }    
    tmp = (*l);
    while((tmp->next != NULL) && (f(inf, tmp->info) > 0)) tmp = tmp->next;
    List tmp1 = tmp->next;
    tmp->next = (List)malloc(sizeof(List_t));
    tmp->next->next = tmp1;
    tmp->next->info = inf;
    return (*l);    
}
 
List search(List l, Info_t inf, compare_f f) {
    while(l != NULL) {
        if(f(inf, l->info)==0) {
            return l;
        }
        l = l->next;
    }
    return NULL;
}
 
List rem(List *l, Info_t inf, compare_f f) {
    if((*l) == NULL)
        return NULL;
    List tmp;
    if(f((*l)->info, inf) == 0) {
        tmp = (*l);
        (*l) = (*l)->next;
        free(tmp);
        return (*l);
    }
    tmp = (*l);
    List tmp1;
    while((tmp->next != NULL) && (f(tmp->next->info, inf) != 0)) tmp = tmp->next;
    if(tmp->next != NULL) {
        tmp1 = tmp->next;
        tmp->next = tmp->next->next;
        free(tmp1);
    }
    return (*l);
}
 
void destroy(List l) {
    if(l == NULL)
        return;
    destroy(l->next);
    free(l);
}
 
void printList(List l) {
    while(l != NULL) {
        printf("%d ", l->info);
        l = l->next;
    }
    printf("\n");
}
 
int compare(Info_t a, Info_t b) {
    if(a<b) {
        return -1;
    } else if(a>b) {
        return 1;
    } else {
        return 0;
    }
}
 
int main() {
    List l = NULL;
    cons(&l, 4);
    cons(&l, 3);
    cons(&l, 5);
    cons(&l, 1);
    printList(l);
    destroy(l);
    l = NULL;
    insert(&l, 4, compare);
    insert(&l, 3, compare);
    insert(&l, 5, compare);
    insert(&l, 1, compare);
    printList(l);
    printList(search(l, 4, compare));
    printList(rem(&l, 3, compare));
    destroy(l);
    return 0;
}