[Tutor] Linked List

Kent Johnson kent37 at tds.net
Sun Mar 6 01:29:22 CET 2005


Stéphane Brunet wrote:
> Kent Johnson wrote:
> 
>>
>> What Jacob is saying is, one common way to deal with this is to make a 
>> copy of the list and iterate over that while changing the original 
>> list. Your sample would look like this:
> 
> 
> Hi,
> 
> And what if the list is *really* big ? Don't you loose much speed/memory 
> while making a copy ?

Well, you do need double the memory and it does take time to copy the list. Whether it is too much 
will depend on the specific requirements.

If you use a linked list instead of a built-in list you will more than double the memory 
requirements immediately. In a linked list, for each data item you store a reference to the data, a 
reference to the next node and the overhead of the node class instance. The built-in list just has a 
single reference for each item and a single instance overhead.

The time to traverse a linked list may well be much greater than for a builtin list. Builtins are 
fast, often faster than anything you can write yourself in Python.

In Python often the simple solution works best. Don't dismiss it until you try it :-)

Alternatives for filtering a list are
- use a list comprehension to build a new list. This is often the best solution. It copies the 
elements being kept, but it avoids having to shift list elements when one element is deleted.
- work from the back of the list - it is safe to iterate a list in reverse and delete elements as 
you go.

I don't think either of these meet the OP's requirements, though. As I understand it, he wants to 
iterate a list, changing the list as he goes, while the list is also being modified by another thread.

A naive linked list will not satisfy these requirements either - some sort of synchronization will 
be needed to avoid, for example, one thread linking a new item onto an item that is being deleted by 
the other thread.

Kent



More information about the Tutor mailing list