CODEWITHSUNDEEP
crandomlinked-list
user561838
user561838

Reputation: 331

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.

Upvotes: 2

Views: 5254

Answers (2)

Jonathan Leffler
Jonathan Leffler

Reputation: 753615

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à...

Upvotes: 1

Michael Shmalko
Michael Shmalko

Reputation: 710

Solution that does not require extra space. Although note that rand() is called random number of times for each node assignment:

struct Node
{
    Node* next;
};

int main()
{   
    Node nodes[1000];
    Node* pNext = NULL; 
    Node* pHead = NULL; 
    Node* pTail = NULL;
    int i = 0;
    // reset .next to NULL
    memset(nodes, 0, sizeof(nodes));
    srand ( time(NULL) );
    pHead = &nodes[ rand() % (1000)];           
    pTail = pHead;
    // need only 999 runs as one node is already assigned
    for (i = 0; i < 999; ++i)
    {   
        pTail->next = pTail;
        while ((pNext = &nodes[ rand() % (1000)]) && pNext->next);
        pTail->next = pNext;
        pTail = pNext;
    }
    // pTail->next = pHead; // uncomment if you need circular list
}

Upvotes: 0

Related Questions