Selecting a random node from a list in C

Question

I have a list and I want to randomly select a node from it. As it's not an array I don't know in advance its length. Is there a way to select a node randomly (with uniform distribution) without having to scan the whole list (in the worst case) twice (i.e. to get its length and to reach the selected node after having randomly selected its position)?

Here's the code I use for my list:

struct mynode {
    in_addr_t paddr;
    struct mynode *prev, *next;
};

struct mylist {
    struct mynode *first, *last;
    char *name;
};

Answer 1

As advised in the comments by joop and Ilja Everilä, I implemented the reservoir sampling in C.

struct mynode *select_mynode(struct mylist *list) {
    struct mynode *list_iter = list->first; // An iterator to scan the list
    struct mynode *sel_node = list_iter; // The node that will be selected
    int count = 2; // Temporary size of the list
    srand((unsigned int) time(NULL)); // Seed
    // Select a random element in O(n)
    while (list_iter->next != NULL) {
        if (rand() % count == (count - 1))
            sel_node = list_iter->next;
        list_iter = list_iter->next;
        count++;
    }
    return sel_node;
}

Note: for further information about random selection, see here.