Questions on linked lists

Greg Ewing (using ckea25d02 at
Wed Apr 2 03:02:58 CEST 2003

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

More information about the Python-list mailing list