O(n^2) is bad - can it be fixed?

[Courageous]

>My assumption was that he's running on a box where realloc eventually puts
>giant things into their own mmap'ed segment.  This kind of programming can
>definitely kill you across platforms, though, and, e.g., Win95 isn't so slick
>with just one list growing forever.

*shrug*. I have a suitable replacement for Python's list that has the following
properties:

	insert-at-head: O[1] amortized
	append-at-tail: O[1] amortized
	random-access: O[1] guaranteed

This is a hybridized vector preallocation strategy that uses both tail _and_
head preallocation. In order to "preallocate at the head" I actually have to
keep a "virtual zero point" in the array, but Python dispatch overhead being
what it is, no Python program would ever notice, and it's only add/compare
in any case.

I'd offer it as a _complete_ replacement for Python's list, except that I never
really felt like filling out the tuple support and implementing sorting (the last
of which intimidated me well and good, sample sort's a bitch). :-)

C//