I need to implement a non-blocking wait free Queue which needs to be linearizable. is this possible with an ArrayList if that ArrayList is declared to be volatile?

If I'm reading you right, sure, inserting into a dynamic array at a random point is O(n).

 

http://en.wikipedia.org/wiki/Dynamic_array

I need to implement a non-blocking wait free Queue which needs to be linearizable.

 

That's quite the sentence there. I'm having a bit of trouble wading through your jargon.

 

You want a queue to communicate between threads (I assume?) and want for it to be atomic in some manner? Do you mean thread-safe?

 

Non-blocking is a term I'm most familiar with in the context of I/O. Do you mean you want it to be lock-free?

 

If I'm reading this right, you want a lock-free queue which is thread safe. If that's the case, what you're asking for is pretty much impossible. A queue used for interthread communication will generally need a combination of a lock and a condition.