Complexity question on Python 3 lists

[Stefan Behnel]

Ian Kelly, 15.02.2012 19:43:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
> 
> I believe the behavior in CPython is that if the array is full, the
> capacity is doubled

But only up to a certain limit. After that, it grows in constant steps.
Otherwise, your memory would be bound to explode on an append even though
your list uses only half of it (or one third, in case it needs to copy).


>, but I'm not certain, and that would be an
> implementation detail in any case.

Absolutely.

Stefan