How to delete all the occurrences of a particular node in a list in linear time

I wrote a function that removes all occurrences of x (if any) in given list (calling object). Returns number of matches found/deleted and the relative order of undeleted elements is unchanged.

int remove_all(const T &x)
{
    int n = 0;

    while (remove_first(x))
        n++;
    return n;
}

But, now I want to make this function such that it must guarantee linear time worst case runtime (hence, "fast").

How could I change the above function to the linear time?