clinked-listsingly-linked-listshufflefisher-yates-shuffle

Why am I losing a node when shuffling a linked list?


I have been working on a project. Part of the project needs a shuffled linked list. This function is an implementation of the fisher-yates shuffling algorithm. It puts the linked list into an array. Then it shuffles it. Then relinks it.

After some testing I have found that sometimes when I shuffle a linked list, I lose a node somewhere. I have done some testing with ubsan and asan. They both show nothing. I used to have a issue with this function causing a segfault later on. The segfault was causing by not relinking the linked list correctly. More specifically the last node before shuffling in the linked list was not relinked correctly. I fixed that somewhat by making the list circular before shuffling it.

Here is the code used for shuffling along with the swap and relink functions:

linked_node* shuffle(linked_node* head) {
    int count = 0;
    linked_node* count_head = head;
    while (count_head != NULL) {
        count++;
        count_head = count_head->next;
    }

    #ifdef DEBUG 
        fprintf(stderr, "count: %i\r\n", count);
    #endif

    linked_node** array = malloc(count * sizeof(linked_node*));

    int i = 0;

    linked_node* add_head = head;

    for (i = 0; i < count; i++) {
        array[i] = add_head;
        add_head = add_head->next;
    }
    
    //made circluar to prevent segfault with the last node
    array[count - 1]->next = head;

    srand48(time(NULL));



    for (int j = count - 1; j > 0; j--) {
        int random = lrand48() % (j+1);

        array_swap(&array[j], &array[random]);
    }

    for (int k = 0; k > count - 1; k++) {
        relink(array[k], array[k + 1]);
    }

    linked_node* new_head = array[0];

    //made circular for ease of use later
    array[count - 1]->next = new_head;

    free(array);

    return new_head;
}

static inline void relink(linked_node* prev, linked_node* next) {
    if (prev != NULL && next != NULL) {
        prev->next = next;
    }
}

void array_swap(linked_node** a, linked_node** b) {
    linked_node* temp = *a;
    *a = *b;
    *b = temp;
}

Solution

  • There is a typo in this for loop

    for (int k = 0; k > count - 1; k++) {
                    ^^^^^^^^^^^^^
        relink(array[k], array[k + 1]);
    }
    

    It seems you mean

    for (int k = 0; k < count - 1; k++) {
                    ^^^^^^^^^^^^^
        relink(array[k], array[k + 1]);
    }
    

    Also this statement

    //made circluar to prevent segfault with the last node
    array[count - 1]->next = head;
    

    is redundant and actually does not have an effect. Remove it.

    This statement

    //made circular for ease of use later
    array[count - 1]->next = new_head;
    

    could be substituted for this statement

    array[count - 1]->next = NULL;