Removing unique elements in a doubly linked list in C

Question

I need a little help removing unique characters in a doubly linked list in C. So here's the logic I tried implementing: I counted the occurrence of each character in the doubly linked list. If it's occurrence is 1 time, then it is unique element and needs to be deleted. I'll be repeating the process for all elements. But my code in remove_unique_dll() function isn't working properly, please help me fix it. Here's my code-

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
    char data;
    struct node *next;
    struct node *prev;
};

struct node *head, *tail = NULL; //Represent the head and tail of the doubly linked list  
int len;

void addNode(char data)
{
    struct node *newNode = (struct node*) malloc(sizeof(struct node)); //Create new node  
    newNode->data = data;

    if (head == NULL)
    {      //If dll is empty  
        head = tail = newNode;  //Both head and tail will point to newNode  
        head->prev = NULL; //head's previous will point to NULL  
        tail->next = NULL; //tail's next will point to NULL, as it is the last node of the list  
    }
    else
    {
        tail->next = newNode; //newNode will be added after tail such that tail's next points to newNode  
        newNode->prev = tail; //newNode's previous will point to tail  
        tail = newNode;  //newNode will become new tail  
        tail->next = NULL; //As it is last node, tail's next will point to NULL  
    }
}

void remove_unique_dll()
{
    struct node *current = head;
    struct node *next;
    struct node *prev;
    int cnt;

    while (current != NULL)
    {
        next = current->next;
        cnt = 1;

        //printf("!%c ",next->data);

        while (next != NULL)
        {
            if (next->data == current->data)
            {
                cnt += 1;
                next = next->next;
            }
            else
                next = next->next;

            //printf("@%c %d %c\n",next->data,cnt,current->data);
        }

        if (cnt == 1)
        {
            prev = current->prev;
            //printf("@%c %d",prev->data,cnt);

            if (prev == NULL)
            {
                head = next;
            }
            else
            {
                prev->next = next;
            }

            if (next == NULL)
            {
                tail = prev;
            }
            else
            {
                next->prev = prev;
            }

        }
        current = current->next;
        //printf("#%c ",current->data);
    }

    head = current;
}

void display()
{
    struct node *current = head;  //head the global one

    while (current != NULL)
    {
        printf("%c<->", current->data); //Prints each node by incrementing pointer.  
        current = current->next;
    }

    printf("NULL\n");
}

int main()
{
    char s[100];
    int i;

    printf("Enter string: ");
    scanf("%s", s);

    len = strlen(s);
    for (i = 0; i < len; i++)
    {
        addNode(s[i]);
    }

    printf("Doubly linked list: \n");
    display();

    remove_unique_dll();

    printf("Doubly linked list after removing unique elements: \n");
    display();

    return 0;
}

The output is like this-

If you uncomment the printf() statements inside remove_unique_dll() you'll notice that no code below inner while loop is being executed after inner while loop ends. What's the issue here and what's the solution?

Sample input- aacb

Expected output- a<->a<->NULL

Answer 1

Some issues:

• You shouldn't assign head = current at the end, because by then current is NULL

• The next you use in the deletion part is not the successor of current, so this will make wrong links

• As you progress through the list, every value is going to be regarded as unique at some point: when it is the last occurrence, you'll not find a duplicate anymore, as your logic only looks ahead, not backwards.

• When you remove a node, you should free its memory.

• Not a big issue, but there is no reason to really count the number of duplicates. Once you find the first duplicate, there is no reason to look for another.

You should really isolate the different steps of the algorithm in separate functions, so you can debug and test each of those features separately and also better understand your code.

Also, to check for duplicates, you might want to use the following fact: if the first occurrence of a value in a list is the same node as the last occurrence of that value, then you know it is unique. As your list is doubly linked, you can use a backwards traversal to find the last occurrence (and a forward traversal to find the first occurrence).

Here is some suggested code:

struct node* findFirstNode(char data) {
    struct node *current = head;
    while (current != NULL && current->data != data) {
        current = current->next;
    }
    return current;
}

struct node* findLastNode(char data) {
    struct node *current = tail;
    while (current != NULL && current->data != data) {
        current = current->prev;
    }
    return current;
}

void removeNode(struct node *current) {
    if (current->prev == NULL) {
        head = current->next;
    } else {
        current->prev->next = current->next;
    }
    if (current->next == NULL) {
        tail = current->prev;
    } else {
        current->next->prev = current->prev;
    }
    free(current);
}

void remove_unique_dll() {  
    struct node *current = head;
    struct node *next;

    while (current != NULL)
    {
        next = current->next;
        if (findFirstNode(current->data) == findLastNode(current->data)) {
            removeNode(current);
        }
        current = next;
    }
}