user561838 user561838 - 3 months ago 25
C Question

randomize linked list in C

Suppose I have a reserved space in memory in a C program, for a linked list containing 1000 items. Each item contains nothing but a reference for next item in the list (last points to the first one). But now they are all set to null, it's just reserved space.

Next I have a

rand()
function which gives me a random number from 1 to 1000. My question is, is there any simple way how to randomize this list using this function in following way: When I start at first element, I will traverse the whole list, that is, there wont be circles in the list smaller than the whole list.

Answer

From your description, you have an array of 1000 nodes all zeroed. For sake of argument, that array is named node_array, and the link field is called next. You also have a pointer called head that can point to one of the nodes.

You can allocate an array of 1000 integers:

enum { NUM_ITEMS = 1000 };
int mapper[NUM_ITEMS];

You can initialize the list so each number appears once:

for (int i = 0; i < NUM_ITEMS; i++)
    mapper[i] = i;

You can shuffle the list. (I should really check in Knuth (The Art of Computer Programming) or Bentley (Programming Pearls or More Programming Pearls), but I think the correct algorithms for random shuffling require a different random number generator — one that generates a random number in the range [n..m) — rather than one that just generates a number in the range 0..999).

for (int i = 0; i < NUM_ITEMS; i++)
{
    int j = rand();
    int t = mapper[j];
    mapper[j] = mapper[i];
    mapper[i] = t;
}

You can now thread through the array of nodes, linking them in the sequence in the mapper array. Because there were no duplicates in the array, there are no cycles in the list.

head = &node_array[mapper[0]];

for (i = 1; i < NUM_ITEMS; i++)
{
    head->next = head;
    head = &node_array[mapper[i]];
}

Et voilà...