confused about resizing array in Python

[Roel Schroeven]

Dongsheng Ruan schreef:
> "Roel Schroeven" <rschroev_nospam_ml at fastmail.fm> wrote in message 
> news:vc8xh.325172$Au6.6345787 at phobos.telenet-ops.be...
>> Ruan schreef:
>>> Then how about Python's list?
>>>
>>> What is done exactly when list.append is executed?
>>>
>>> For list, is there another larger list initialized and the contents from 
>>> the old list is copied to it together with the new appended list?

>> I'm not sure, but I think each time the list needs to grow, it doubles in 
>> size. That leaves room to add a number of elements before the allocated 
>> space needs to grow again. It's a frequently used approach, since it is 
>> quite efficient and the memory needed is never double the amount of memory 
>> strictly needed for the elements of the list.

 > You mentioned "it doubles in size".
 >
 > Are you saying that a new double sized array is allocated and the
 > contents of the old list is copied there?
 >
 > Then the old list is freed from memory?
 >
 > It seems to be what is called amortized constant.
 >
 > Say the list size is 100, before it is fully used, the append takes
 > O(1) time. But for the 101th element, the time will be O(100+1), and
 > then from then on, it is O(1) again. Like John Machin said in the
 > previous post?
 >
 > But on average, it is O(1). I guess this is the amortized constant.
 > Isn't it?

I think so, more or less, but as I said I'm not entirely sure about how 
Python handles lists.

One thing to keep in mind is that the list (like any other Python data 
structure) doesn't store the objects themselves; it only stores 
references to the objects. If the list needs to be copied, only the 
references are copied; the objects themselves can stay where they are. 
For small objects this doesn't make much difference, but if the objects 
grow larger it gets much more efficient if you only have to move the 
references around.

-- 
If I have been able to see further, it was only because I stood
on the shoulders of giants.  -- Isaac Newton

Roel Schroeven