Questions on linked lists
Paul_Rudin at scientia.com
Wed Apr 2 10:49:23 CEST 2003
>>>>> "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!!
More information about the Python-list