Queues - Is Infinity all right?

[logistix at cathoderaymission.net]

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote in message news:<7xr81reorq.fsf at ruckus.brouhaha.com>...
> Peter Hansen <peter at engcorp.com> writes:
> > Checking the source, Queue is implemented as a sophisticated wrapper
> > around a standard Python list [].  That means adding an item is 
> > amortized O(1), while removing one is O(n).
> 
> Why is removing one O(n)?  That should be easy to fix, if true.

A list is an array of pointers to py_objects, not a linked list.  So
removing element x from a list of size y requires something like:

for z in range(x,y):
    l[z] = l[z+1]

But since you're only copying the pointers and not the underlying
objects, it's a pretty quick O(n)