Questions on linked lists

[Paul Rudin]

>>>>> "EMF" == Erik Max Francis <max at alcyone.com> writes:

 EMF> 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?

 EMF> Yes.  Python lists are (computer science) vectors, which means
 EMF> they're dynamically resizeable arrays.  It's inexpensive to
 EMF> index into the list [O(1)] and add to the list [amortized O(1)],
 EMF> but it's expensive to insert or delete from the list [O(n)].  A
 EMF> linked list, although it's expensive to index [O(n)], is very
 EMF> inexpensive to insert or delete objects at _any_ location [O(1)
 EMF> for either].

Another thing to bear in mind if that a lot of indexing is not random
- much code iterates over the elements of a list in sequence. In this
circumstance the you obviously don't have to traverse down from the
head of a linked list for each element access.


-- 
Sorry, wrong ZIP CODE!!