Recursively traverse linked list -- help!

[Gustavo Niemeyer]

> Fair enough! Actually if I pit the LinkedList against the builtin list
> in the case you're talking about (where you never have to do any work to
> find the insertpoint) the LinkedList will come out as a winner already
> at 5000 - 10000 inserts.

Hey!! That's not fair:

> inserts at start of LinkedList
> 20000 0.457922101021
[...]
> inserts in middle of builtin list
> 20000 0.787240982056

You're comparing oranges and bananas here... ;-)

I've repeated your test (using time.clock() instead of time.time()).
Here is the result:

inserts at start of LinkedList
00000 -> 10000  0.64
10000 -> 20000  0.64
20000 -> 30000  0.66

inserts at start of builtin list
00000 -> 10000  0.07
10000 -> 20000  0.07
20000 -> 30000  0.07

inserts in middle of LinkedList
00000 -> 10000  448.46
10000 -> 20000  1365.52
20000 -> 30000  (too long)

inserts in middle of builtin list
00000 -> 10000  0.34
10000 -> 20000  1.04
20000 -> 30000  1.62

This means at least two things: first, the list builtin object is
written in C; and second, the builtin list is not just a dumb array
asking for more memory at every insert.

--
Gustavo Niemeyer

[ 2AAC 7928 0FBF 0299 5EB5  60E2 2253 B29A 6664 3A0C ]