array, list, performance...

[Michael Chermside]

Here is my understanding of it:

    li = [x0, x1, x2, ...]

    li[n]          element access is O(1)
    li.append(x)   appending is O(1)
                   (actually, it SOMETIMES takes O(len(li)) as it
                    resizes the list. But if you grow a list by
                    continually appending, the amortized time is
                    linear (ie, constant amortized time per element)
    li.insert(0)   prepending is O(len(li))
                   (so grow the list from the end!)
    del li[0]      deleting from the front (or middle) is O(len(li))
    li.pop()       deleting from the end is O(1)
    li[n] = x      assignment to the middle is O(len(li))
    len(li)        determining length is O(1)
    li.index(x)    search is O(len(li)) (NOT efficient)
    li.sort()      sort is O(len(li)*ln(len(li)))
                   (I believe it uses quicksort, but if a python
                    function has to be executed for the compare
                    that may take some time.)

It's really just your basic auto-growing array, but with a bunch of 
clever things done to speed up common cases, and I don't know those well 
enough to comment on them.

-- Michael Chermside