LINKED LISTS?

[Gordon McMillan]

Robin Becker <robin at jessikat.demon.co.uk> wrote:
>
>In article <391d592e$0$13925 at wodc7nh6.news.uu.net>, Gordon 
McMillan
><gmcm at hypernet.com> writes

>>In practice, linked lists are O(really big 1). That is, for most 
usage, 
>>Python's supposedly O(n) lists will outperform them. 

>well it may be true for a lot of things, but it's certainly not true for
>insertion and deletion intensive eg

[snip]

>produces
>n=    10, t=0.0000181000
>n=   100, t=0.0000225000
>n=  1000, t=0.0000681000
>n= 10000, t=0.0006784000

>which is clearly not O(1)

OK, now create a Python linked list implementation which is faster 
than 0.000678.

>... arguing that making accesses O(1) is 'the
>right thing to do' will get short shrift from the complexity experts 
who
>will want to know about the overall usage.

Huh?