confused about resizing array in Python

[Dongsheng Ruan]

This seems to be  clever to use reference for list.

Is it unique to Python?

How about the traditional programming languages like C, Pascal or C++?

"Roel Schroeven" <rschroev_nospam_ml at fastmail.fm> wrote in message 
news:qx9xh.325276$Ko7.6479988 at phobos.telenet-ops.be...
> 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