How to change the function such that it guarantees a linear time worst case runtime.

philip1999 (36)
1
2
3
4
5
6
7
 
     struct Node
	{
		T data;
		Node *next;
	};
    Node *front;
	Node *back;

The below is a function that removes the first occurence of x in a linked list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
    bool remove_first(const T &x)
	{
		Node *p, *tmp;
		T dummy;

		if (front == nullptr)
			return false;
		if (front->data == x)
		{
			pop_front(dummy);
			return true;
		}
		p = front;
		while (p->next != nullptr)
		{
			if (x == p->next->data)
			{
				tmp = p->next;
				p->next = tmp->next;
				if (tmp == back)
					back = p;
				delete tmp;
				return true;
			}
			p = p->next;
		}
		return false;
	}

Now, I have a function that searches for all the occurences of the element throughout the list and then deletes.
1
2
3
4
5
6
7
 
    int slow(const T &x)
	{
		int i = 0;
		while (remove_first(x))
			i++;
		return n;
	}

Now how can I change this function such that it must guarantee linear time worst case runtime ("fast").

Can anyone please help me with this.
Repeater (3046)
Looks like each time you remove one, you then start again at the very beginning of the list in your search for the next one, and you will examine the same nodes over and over again.

Don't do that.

Your remove_first function could provide to the caller the node after the one that was removed, and could accept a node to beging searching at. Then, each time remove_first returns, you call it again with that start position node value so you don't start at the beginning of the list again.
philip1999 (36)
@Repeater Can please explain with the code. That would be more helpful for me to understand.
homy18 (31)
Topic archived. No new replies allowed.