LINKED LISTS?

[Robin Becker]

In article <391d592e$0$13925 at wodc7nh6.news.uu.net>, Gordon McMillan
<gmcm at hypernet.com> writes
>Courageous <jkraska1 at san.rr.com> wrote:
>
>>I don't get it. The code for python lists is, as plain as
>>the nose on the end of my face, a resizeable vector
>>implementation. Which is all well and good, but where
>>are the linked lists for those of us who want insert,
>>delete, and append to be O(1)?
>
>In practice, linked lists are O(really big 1). That is, for most usage, 
>Python's supposedly O(n) lists will outperform them. Trust me on 
>this. I've optimized a *lot* of C / C++ code by replacing linked lists 
>with (overallocated) realloc-ing vectors. In most cases the speed up 
>is dramatic (even when a linked list appears the correct structure).
>
>- Gordon
>
well it may be true for a lot of things, but it's certainly not true for
insertion and deletion intensive eg

from time import time
def listTest(n,ntests=100000):
        L = range(n)
        h = n/2

        t0 = time()
        for t in xrange(ntests):
                del L[0]
                L.insert(0,0)
                del L[h]
                L.insert(h,t)

        return (time()-t0)/ntests

for n in (10, 100, 1000, 10000):
        print "n=%6d, t=%.10f" % (n, listTest(n))

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); 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.
-- 
Robin Becker