Eliminate all the occurrences of repeated elements

Question

I'm trying to eliminate all the occurrences of repeated elements in a linked list. For example, if I have: 1-2-3-2-4-2-4, I want to eliminate all the occurrences of 2 and 4 and get: 1-3

I use a function called eliminateRepeated that iterates and counts the occurrences; if the count is bigger than 1, the program calls the function eliminateAllTheOc. But I get this:1-3-2-4. The last occurrence is not eliminated. If I call the function eliminateAllOc separately with the value 4 for example, it works fine and returns 1-2-3-2-2.

typedef struct{
    int num;
}t_dataL;

typedef struct s_nodeL{
    t_dataL dataL;
    struct s_nodeL *next;
}t_nodeL;

typedef t_nodeL *t_list;

int elimnateAllTheOc(t_list *l, t_dataL *d, int(*cmp)(const void*, const void*)){
    if(!*l) return 0;
    t_nodeL *aux;
    while(*l){
        if(cmp(&(*l)->dataL, d) == 0){
            aux = *l;
            *l = (*l)->next;
            free(aux);
        }
        else l = &(*l)->next;
    }
    return 1;
}

int eliminateRepeated(t_list *l, int(*cmp)(const void*, const void*)){
    t_list *plec, *ini = l;
    t_nodeL *aux;
    int n = 0;
    while (*l){
        plec = ini;
        while(*plec){
            if(cmp(&(*l)->dataL, &(*plec)->dataL) == 0) n++;
            plec = &(*plec)->next;
        }
        if(n > 1) eliminateAllTheOc(ini, &(*l)->dataL, cmp);
        else l = &(*l)->next;
        n = 0;
    }
    return 1;
}

How can I eliminate all occurrences of a repeated element?

Perhaps it's time you learn [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/)? — Some programmer dude, Jul 11 '17 at 06:25
As for a possible alternative solution, how about instead of removing nodes from the current list you create a *new* list where you make a copy of all nodes that doesn't have a duplicate? Then "delete" the old list, and reassign so the "new" list becomes the "old" list. — Some programmer dude, Jul 11 '17 at 06:28
The posted code doesn't compile. That should be fixed as the first step. Then create a minimal example, i.e. provide a main function that initializes a simple list and show how you call your function. And finally described the actual result of that minimal example. — Support Ukraine, Jul 11 '17 at 07:08
Provide [Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve). — cse, Jul 11 '17 at 07:24
See [Is it a good idea to `typedef` pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) — the short answer is "No". — Jonathan Leffler, Jul 11 '17 at 15:05

Support Ukraine · Accepted Answer · 2017-07-11T08:06:19.620

First you must fix the wrong function name, i.e.

int elimnateAllTheOc(...  ->  int eliminateAllTheOc(
                                      ^

Then you must fix the undefined behavior that your code has. The problem is that you pass a pointer to the compare value, i.e. t_dataL *d. This is a pointer to data inside a list element that you are going free. So once you free the element, dereferencing d is undefined behavior.

Example

Consider a very simple list:

1 -> 1

In this case you want to remove both elements. You call eliminateAllTheOc with a pointer-to-pointer to the first element and for compare value you pass a pointer to dataL in the first element.

In the first loop you free the first element. Thereby d is no longer pointing to a valid object. Consequently in your next loop you have undefined behavior when doing *d.

If you want to pass a pointer to the compare value, you must make sure that the pointer points to a valid object all the time. You could do that by making a copy:

    if(n > 1)
    {
        t_dataL tmp = (*l)->dataL;
        eliminateAllTheOc(ini, &tmp, cmp);
    }
    else l = &(*l)->next;

I doubt this solves all problems with the code but fixing this UB is a first important step.

Eliminate all the occurrences of repeated elements

1 Answers1