[SciPy-user] How to start with SciPy and NumPy
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