>> difference. Certainly nothing becomes O(n) instead of O(1). For
>> (length), example, there's just an extra check at each step -- no need
>> for hare-and-tortoise.
>
> Could you elaborate on this last sentence (I don't see it)?
You're right, it does need hare-and-tortoise. My bad.
Hare-and-tortoise is still O(n), but let's see what the factor is.
For a non-circular list, the hare will perform an extra traversal, and the
tortoise a half-traversal. Thus (lenght) will take 150% more to complete.
OK, I support your comment. Circularity checks make common list operations
150% slower for catching a hypothetical bug that no one has seen happen.
It's a pretty bad trade-off. People working with circular lists know what
they're doing and can implement hare-and-tortoise themselves.
Best,
Dan Muresan
http://alumnus.caltech.edu/~muresan
Received on Mon Oct 02 2006 - 07:21:49 UTC