[SciPy-user] How to start with SciPy and NumPy

Prabhu Ramachandran prabhu@aero.iitb.ac...
Sun Jan 25 10:05:47 CST 2009

Sturla Molden wrote:
> It is often claimed that Python lists are slower than linked lists for
> appends in the middle. This is not true: While the "insert in the middle"
> is O(1) with a linked list and O(N) with Python lists, reaching the middle
> item is O(1) with Python lists and O(N) with linked lists. For an append
> in the middle you need to to both.

Just a minor point:  Often, when you want to insert something "in the 
middle" of a sequence you want to insert it next to an existing element 
and in that case there isn't an additional O(N) to find the middle 
element that you speak of.  A more common need I have had is to remove 
an existing element located arbitrarily in which case using link lists 
is practical.  However, if the order of elements in the array is not of 
consequence, one can easily devise a simple scheme to remove an element 
in the middle of the array in O(1) operations.


More information about the SciPy-user mailing list