Questions on linked lists

[Erik Max Francis]

Dave Benjamin wrote:

> That said, what would be an example of a legitimate need for a custom
> linked
> list data structure in Python? I can't say I've come across one yet.
> Do
> linked lists outperform native Python lists at certain operations?

Yes.  Python lists are (computer science) vectors, which means they're
dynamically resizeable arrays.  It's inexpensive to index into the list
[O(1)] and add to the list [amortized O(1)], but it's expensive to
insert or delete from the list [O(n)].  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.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ A good indignation brings out all one's powers.
\__/ Ralph Waldo Emerson
    Esperanto reference / http://www.alcyone.com/max/lang/esperanto/
 An Esperanto reference for English speakers.