[Tutor] Linked List
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:
> 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
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.
More information about the Tutor