# Deleting the first element of a list

Bruce Dawson bruce_deletethis_dawson at cygnus-software.com
Thu Oct 3 06:26:58 CEST 2002

```Peter Hansen wrote:

> Erik Max Francis wrote:
>
>> JB wrote:
...
>> quantitative information about where the bottlenecks truly are.  This
>> concept is especially powerful in a high-level language like Python; the
>> very choice of using Python means that you're willing to trade raw speed
>> for flexibility.  If you're overconcerned with squeezing every last bit
>> of CPU power right from the start, then Python (or any other high-level
>> language) was probably not a good choice of languages.
>
>
> Well stated, although a note about changing algorithms generally
> providing the most significant speedups might be in order.  Even
> with Python, picking a better algorithm can produce huge gains.
> (This does not, of course, apply to a small idiomatic choice such

Highly applicable to this thread. Deleting the first item of a Python
list or C++ vector is an O(n) operation - proportional to the number of
items in the list. If you do that for every item in the list it is
O(n^2) - proportional to the square.

The thing about O(n^2), and any complexity higher than that, is that
there are many values of N that are small enough for N items to easily
fit into memory, but large enough to make the program run for days and
days and days and days.

O(n^2) is bad, unless you know that n will always be small.

So, if performance is a problem, the OP should consider reworking the
code. For instance, if the original code was:

while myList:
# Do Something with the first element
del myList[0]

Then it should be much better to go:

myList.reverse()
while myList:
# Do Something with the last element
del myList[len(myList)-1]

This changes it from O(n^2) to O(n), which could make it run thousands
of times faster.

Premature optimization is the root of all evil, but O(n^2) is pretty
darned evil too!

Of course, the OP's code may not be so easily reworked as my simple example.

```