Cool! (was: "dlist" -- beta is ready)

[Russell Turpin]

Courageous wrote:
> There are three items which I will finish soon
> (perhaps sooner if someone asks for them):
> 
> 2. reversing.

Since this is a more symmetric implementation than
the standard list, I wonder if it makes sense just
to reverse the sense, ie, subtract indices from 
the top, rather than add from the bottom. If this
works, then reversing becomes O(1) instead of O(n).
(OTOH, this adds a test to the index operator, and
there likely will not be much need for reverse, 
since dlist supports operations at either end. 
With standard lists, reverse provides a way to 
work at the other end efficiently, as long as you 
can justify the cost of the reverse. So this likely
is a BAD idea.)

OTOH, here's another possible optimization that
symmetry makes possible: If you support
indexing from either end, it is possible to support
O(1) deletes, as long as all other operations are
in the first or last segment of the list. Reallocation 
would occur only when there is an operation that has
deleted spots between it and both ends of the list.
This would change linear scan with selected delete
from an O(n^2) operation to an O(n) operation. On
the other hand, this would also add some complexity
to your current implementation, since it requires
maintenance of a delete list, with first and last
indices. It also adds one more comparison to the 
index operator.

Excited-about-dlist-ly yrs,
Russell