I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).
My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have constant access via an index.
Looking over the documentation though, I realized that ArrayLists' additions are considered Amortized Constant Time, since an addition may require a reallocation of the underlying array, which is O(n).
Are Amortized Constant Time and Constant Time effectively the same, or do I need to look at some structure thay doesn't require a full reallocation on every addition?
I'm asking this because array based structures aside (which as far as I know will always have Amortized Constant Time additions), I can't think of anything that will meet the requirements:
- Anything tree based will have at best O(log n) access
- A linked list could potentially have O(1) additions (if a reference to the tail is kept), but a random removal should be at best O(n).
Here's the full question; in case I glazed over some important details:
Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.