List objects are implemented as
arrays. They are optimized for fast
fixed-length operations and incur O(n)
memory movement costs for pop(0) and
insert(0, v) operations which change
both the size and position of the
underlying data representation.
See also:
http://docs.python.org/library/collections.html#collections.deque
Btw, I find it interesting that the Python tutorial on data structures recommends using pop(0) to simulate a queue but does not mention O(n) or the deque option.
http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues