[theaustinseven]

The insert is still an N operation since N in this case is the number of nodes in the list. It would only be O(1) if the list was of constant size(and even that would be misleading). The worst case is still infinity, because you are concerned with a single insert operation, and not that there are some making progress. We are merely concerned with the progress that a given insert operation makes, and there could potentially be an infinite loop. You can reduce the probability of this happening by shortening the loop between repeating the CAS operation.

Otherwise I think it would be awesome to see profiling results, I suspect that the garbage collection time can be reduced significantly. I have recently been implementing a locking thread-safe queue, and I think it would be interesting to compare the differences in speed and garbage produced, just to get a better idea of the pros and cons. I suspect if you shortened the retry loop you have, your implementation would be faster.

When I said flawed, I meant that it was not really enforcing order on insertion, but for many applications, this doesn't matter that much. Close enough is often good enough(and the probability of this going wrong is fairly small, except in extreme cases).