Data structure for java

Sup /prog/, I need to an indexed data structure that supports these methods:


void addLast(S stuff);     // insertion's like a queue
void removeLast();         // removes last link
void removeIfHas(S stuff); // removes link if has target stuff
S getStuff(int index);     // retrieves stuff given the index

I can do this with a (Doubly/Double) Linked List, but the search/retrieval is O(n). Is a HashTable a better structure?

Thanks

>>1
A hashtable doesn't meet your requirements (no intrinsic integer indexing, and even if you use a TreeMap or something you still can't addLast, removeLast).

Probably what is best is just a simple ArrayList. O(1) addLast, removeLast and getStuff, O(n) removeIfHas.

If O(n) removeIfHas is unacceptable (my guess is you will be fine), you can write a custom data structure that uses a map to index into a linked list which will give you O(1) amortized for all operations- this seems beyond you so I advise the first approach.