Solution for removing duplicates in a doubly linked circular list not working

Question

I've written the function for removing duplicate elements in a doubly linked circular list. However when traversing the list after removing, I am not getting the desired output.

I have used typedef to enclose

#define MAX 10

typedef struct node {
    int data;
    struct node *next, *prev;
} NODE;

NODE *rem(NODE *head) {
    NODE *node = head;
    int hash[MAX] = { 0 };
    while (node != NULL) {
        hash[node->data]++;
        node = node->next;
    }
    node = head;
    NODE *node2 = head->next;
    while (node2 != NULL) {
        if (hash[node2->data] != 1) {
            NODE *r = node2;
            node->next = node2->next;
            node2->next->prev = node;
            free(r);
            hash[node->data]--;
        }
        node = node2;
        node2 = node2->next;
    }
    return head;
}

Using the debugger shows segmentation fault in line: hash[node->data]++; I have created a hash array to keep count of duplicate elements and keep removing the elements until the count of each element is 1. But traversing the list after the function does not give any output.

Answer 1

There are multiple problems in your code:

• the values in the data member of all nodes must be inthe range 0 to MAX-1. You should at least verify this to avoid writing outside the array hash. The name MAX suggest the array should have a length of MAX + 1, but testing the actual values is a useful precaution.
• if the list is circular, testing for a null next member is incorrect: you should test if the current node has circled back to the head of the list instead.

Here is a modified version that works for both circular and null terminated lists:

typedef struct node {
    int data;
    struct node *next, *prev;
} NODE;

// remove duplicates in the doubly linked list.
// works with circular lists and null terminated lists
NODE *rem(NODE *head) {
    NODE *node = head;
    while (node != NULL) {
        NODE *next = node->next;
        while (next != NULL && next != head) {
            if (next->data == node->data) {
                // next is a duplicate of node: detach and free it
                NODE *r = next;
                if (next->next)
                    next->next->prev = next->prev;
                next = next->prev->next = next->next;
                free(r);
            } else {
                next = next->next;
            }
        }
        node = node->next;
        if (node == head)
            break;
    }
    return head;
}