Yes. I suppose that probability to get such bad random distribution which makes SL search to be linear is similar to probability of moving all oxygen atoms to only one side of your room.
Even against an adversary? (Asking because I don't know the data structure too well.)
If the adversary find a bug in your system, such as not so random "random generator", then it can bring it down. But if the random generator is reasonable, then you can expect it to behave properly on all inputs.