Questions on linked lists

[Greg Ewing (using news.cis.dfn.de)]

Erik Max Francis wrote:
> A linked list, although it's
> expensive to index [O(n)], is very inexpensive to insert or delete
> objects at _any_ location [O(1) for either].
> 
> If you find you need a data structure where you are doing a lot more
> inserting and deleting than indexing, then a linked list might well make
> a great deal more sense.

Be careful, though -- chances are, in Python you'd
need quite a large list before the overhead of the
Python operations needed to create a node and insert
it became less than the C-speed operation of inserting
into a Python list.

The O(x) statements above are true, but there are
some pretty hefty constant factors involved here!

-- 
Greg Ewing, Computer Science Dept,
University of Canterbury,	
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg