How to change the function to the linear time.

[philip1999]

I have the following 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?

[Duthomhas]

The problem with remove_first(x) is that it has to search from the beginning of the list every time you call it, right?

What could you do to avoid starting at the beginning of the list each time?