Java Data Structure -

i'm looking data structure act queue can hava first in first out behaviour, ideally able see if element exists in queue in constant time can hashmap, rather linear time linkedlist.

i thought linkedhashmap might job, although make iterator , take , remove first element of iteration produce sort of poll() method, i'm wondering if there better way.

many in advance

often when want behaviour of 2 collections need maintain 2 collections. simple approach have queue , hashset, , perform add both , remove hashmap when remove queue.

an alternative use linkedhashset. retains order elements added , can remove first/oldest element each time.

a third option use queue. while might o(1) lookup time, may find fast enough meet requirements searching every element. might faster expect. i.e. 1000 elements should less 10 micro-seconds.

edit: agree 2 collections best when don't know length.

however show brute force search can fast too. slowest object 1 not there. (as has compare every element)

queue<point> points = new arrayblockingqueue<point>(1024); for(int i=0;i<1000;i++)   points.add(new point(i,i)); point missing = new point(-1, -1); int runs = 100 * 1000; long start = system.nanotime(); for(int i=0;i< runs;i++)     points.contains(missing); long time = system.nanotime() - start; system.out.printf("average contains() took %.1f us%n", time/runs/1000.0); 

prints

average contains() took 5.1 

you may need test data type times of equals() , sizes of queue can vary, may surprise can in 10 micro-seconds , may fast enough.