clinked-listdoubly-linked-listcircular-list

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


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.


Solution

  • There are multiple problems in your code:

    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;
    }