Questions on linked lists
Greg Ewing (using news.cis.dfn.de)
ckea25d02 at sneakemail.com
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