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.
There are multiple problems in your code:
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.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;
}