Fastest way to remove a specific element from a queue

Hello, I need to remove a specific element from a queue, I've found two ways so far and I'm wondering which one is the fastest; also if I have another function that accesses the queue, can one these ways be dangerous? Thanks!

1) Copy the queue in a list, check the list for the element, remove the element, use the list to create a new queue.

Code (CSharp):

1. public void RemoveJob(Job job)
2.     {
3.         List<Job> jobList = new List<Job>(jobQueue);
4.         if (jobList.Contains(job) == true)
5.         {
6.             jobList.Remove(job);
7.             jobQueue = new Queue<Job>(jobList);
8.             return;
9.         }
10.     }

2) Check the queue for the element, create a new queue without the element.

Code (CSharp):

1. public void RemoveJob(Job job)
2.     {
3.         if (jobQueue.Contains(job) == true)
4.         {
5.             jobQueue = new Queue<Job>(jobQueue.Where(p => p != job));
6.             return;
7.         }
8.     }

 

Can't you just use a LinkedList<T> instead of a Queue<T> ?

 

The

.Contains(x)

takes time proportional to the length of the queue or list.

The

.Remove(x)

basically redoes the exact same search, with a little extra work if a match is found. Just try to remove the item without a search first.

In some languages and libraries, this kind of operation would throw an exception or error if you tried to remove something and it was never found. In such cases, it's faster to simply use a try/catch block to catch the error you expect may happen, than to perform extra work to avoid the situation.

And since Queue class has no

.Remove(x)

I also suggest you use a more suitable List which can add at one end, remove(x), and quickly remove at the other end. (Thanks Tortuap.) Excessive structure conversions are very costly.

 

Gonna do some research about LinkedList, thanks.

What about the second solution, is it better than the first one? It doesn't have to search the list twice and doesn't convert the queue either, but it has to check each element.

 

Of course it's searching twice:

.Contains(x)

and then

.Where(...)

. And of course it's converting-- it is converting from a Queue with unknown contents to a whole new copy of the Queue with filtered contents.

If you think it's rare for this function to be called with a job that is in the list, then checking up front will save you a lot of time doing the filtering for no benefit. But the function is called

RemoveJob()

so I would think that 99+% of the time, the caller is already expecting job to be present. Just run the filter without searching first!

 

I meant it doesn't convert the list to a queue and then back, or does it do that internally?

It's not guaranteed that the job is in the queue, because a character could take the job from the queue and the player could cancel the job while the character hasn't started the job yet.