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" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Dongsheng Ruan schreef: >> "Roel Schroeven" <[EMAIL PROTECTED]> wrote in message >> news:[EMAIL PROTECTED] >>> 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 -- http://mail.python.org/mailman/listinfo/python-list
