Delete k lasts occurences of a list element

Question

Currently I am working on a function which deletes the number of lasts occurrences of a list element I choose. I passed to realize a function to delete the last occurrence of a list element and I was wondering how to program my last function.

The function which delete last occurrence of a specific element :

void DeleteLastOccurence(int x, List *l)
{
    List *p = l;
    List *m = NULL;
    while(*p != NULL)
    {
        if((**p).number == x)
        {
            m = p;
        }
        p = &(**p).next;
    }
    if(m != NULL)
    {
        depile(m);
    }
}

My List structure :

typedef struct Block
{
    int number;
    struct Block *next;
} Block;

typedef Block *List;

depile subfunction, which removes the first element of the list in parameter :

void depile(List *L)
{
    List tmp = *L ;
    *L = Lnext(*L) ;
    free(tmp) ;
}

and Lnext subfunction, returns a new List corresponding to the one in parameter without its first element :

Liste Lnext(List l)
{
    return l->next;
}

I test my current function with the list [2;1;1;2;4;4;4;4] and x = 2 and I get [2;1;1;4;4;4; 4].

screen of my terminal :

I think I need to add an integer k to delete the k lasts occurrences of the element.

In my last function, with the same list, x = 4 and k = 3, I should get the list [2;1;1;2;4].

So I would like to know if I could just modify this function a bit to get the final version?

for example, previously I realize a function which delete first occurrence of a list element :

void DeleteFirstOccurence(int x, Liste *l)
{
    if(isEmpty(*l))
    {
        return;
    }
    else
    {
        if(x == firstElement(*l))
        {
            depile(l);
        }
        else
        {
            DeleteFirstOccurence(x, &(*l)->suivant);
        }
    }
}

with FirstElement and isEmpty subfunctions :

int FirstElement(List l)
{
    return l->number ; 
}
bool isEmpty(List l)
{
    return l == NULL ;
}

and by using it, I was able to implement the function that eliminates the first k occurrences :

void DeleteKfirstsOccurrences(int x, int k, List *l)
{
    if(isEmpty(*l))
    {
        return;
    }
    else
    {
        for(int i = 0; i < k; ++i)
        {
            if(x == FirstElement(*l))
            {
                depile(l);
            }
            else
            {
                DeleteFirstOccurence(x, &(*l)->next);
            }
        }
    }
}

DeleteFirstOccurence with x = 0 and list [4;2;0] and DeleteKFirstsOccurences with x = 5, k = 5 and list = 2 1 1 2 4 4 4 4:

if it would be possible to perform a similar process on my first function to get the desired result, knowing that the structure is not the same and that I personally did not succeed.

P.S : In my different functions, if k > number of occurrence of x in list, delete all occurrences.

Thank you for your time and your different suggestions,

Sincerely.

(Sorry for my English level, I don't usually write so much)

Answer 1

Looking at your code i can see that you are not working with a list, but rather a linked list.

If i understand your problem correctly you want to delete n amount of occurrences of an x element.

To do that you would need to parse your list to find all of the elements you want to delete, you can either store them or just store where you need to start to delete n of them, for example:

int countInstances(int element, List l) {
    List * temp = l;
    int counter = 0;
    while (temp) {
        if (temp.number == element)
            counter ++
        temp = temp.next;
    }
    return counter;
}

If you have lets say a list [0,1,1,3,3,3,3,3] and you wanted to delete the last 4 occurrences of the number 3, using the above function you can see that you have 5 instances of the number 3, since you want to delete the final 4 you need to ignore 1 and delete all the rest.

It would be helpful to have a standard delete function when working with linked lists, e.g

void linked_delete(int index, linkedList &list)

You can find more information here

Edit:

I just realized the counter function is wrong since it ignores the final element, assuming that the final next in your list is NULL or nullptr the new one should work.

Answer 2

it's probably not very optimized, but it works by putting the function in a for loop :

void DeleteKLastOccurences(int x, int k, List *l)
{
    for(int i = 0; i < k; i++)
    {
        DeleteLastOccurence(x, l);
    }
}

After that, there is surely something better.