Pop a list from beginning ? and memory saving...

[James T. Dennis]

Shagshag13 <shagshag13 at yahoo.fr> wrote:

> I had a huge list containing consuming data, as i only need a one pass in a
> for statement,
> i'm wondering if by doing this with a pop i could save memory ? (as i think
> that python
> free it after the pop...)
> and is there a way to pop from the beginning  of the list ? (i think i could
> use reverse but
> i don't know if this memory consuming)

 The problem with l.pop(0) is that it will run at O(n) time
 (linearly proportional to the list's size).

 From what I gather the underlying C structure of a list allows
 things to be appended and popped (from the end) in constant time.
 So the obvious answer would be to build the list in reverse order
 and then pop() them all off the end with a simple:

	while len(l):
		i=l.pop()
		# ...

 If that's not feasible (you can't build the list in reverse order)
 then you might try profiling list.reverse() (it might be implemented
 as an inplace reversal in the underlying C or Java.  If so the reverse()
 method will be O(n) and the processing will be O(1) for each item
 for a total of 2 * O(n).  That may not be ideal but it's much better
 than ~ O(n) * 1/2 * 0(n) (which is the roughly the result of the 
 original approach where each iteration takes O(n)).

 So, the critical question is:

	Is the list's reverse() method done in place and does it
	run in linear time (or better?  if so, how)?