Question about scientific calculations in Python

[Bengt Richter]

On Tue, 12 Mar 2002 22:15:43 -0700, "Andrew Dalke" <dalke at dalkescientific.com> wrote:
[... good optimization advice, nicely elaborating the idea of precomputing ...]
>If your lists are really long (O(100,000) or more?) then you might find
>that the append starts taking too long -- append is asymptotically O(n**n)
whoa! can that be true? I hope not. It is very cheap to tie a singly linked
list into a circle and point to the last node when pointing to the list as a whole.
Then append cost should be independent of length (other than indirect effects
from memory allocation hiccups). Note that accessing the first element is just
one indirection from the last, so a simple adjustment to the base pointer after
an append makes it into a prepend.

If it's doubly linked, appending should already be constant time.

Regards,
Bengt Richter