Is a volatile ArrayList linearizable?

[S8G Legend]

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?

[Pangloss]

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

[bascule]

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.