Recursively traverse linked list -- help!

[Paul Rubin]

Gustavo Niemeyer <niemeyer at conectiva.com> writes:
> > Sure, granted that you keep track of the middle link of your list, so
> > that you don't have to traverse up to that point. But even if keep track
> > of it you'll have to be doing pretty large lists before the linked list
> > will outperform the builtin list.
> 
> Agreed.
> 
> It's also nice to remember why we use python in the first place. If I
> had to write a linked list to keep billions of records with a very specific
> and performance dependent algorithm, I would probably write a python module
> in C. And if the whole application is dependent on performance, I wouldn't
> use any high level language to develop it.

By "middle" I didn't mean the geometric middle, but the usual case of
wanting to insert a new node after an existing node that you already
have a handle on. 

Yes, the lists have to be pretty large for implementing linked lists
in Python to beat Python's built-in vectors.  But that's only because
interpreting Python code is so abysmally slow, which is a Python
implementation artifact.  If and when faster Python implementations
(i.e. with real compilers) become available, the crossover point will
probably become a lot lower.  Even as it is, though, your measurement
only went up to 20,000 nodes; I'd be interested in the timing at a
million nodes.