Python list memory reallocation issue

Question

If I am using C-Python or jython (in Python 2.7), and for list ([]) data structure, if I continue to add new elements, will there be memory reallocation issue like how Java ArrayList have (since Java ArrayList requires continuous memory space, if current pre-allocated space is full, it needs re-allocate new larger continuous large memory space, and move existing elements to the new allocated space)?

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29

regards, Lin

Answer 1

The basic story, at least for the main Python, is that a list contains pointers to objects elsewhere in memory. The list is created with a certain free space (eg. for 8 pointers). When that fills up, it allocates more memory, and so on. Whether it moves the pointers from one block of memory to another, is a detail that most users ignore. In practice we just append/extend a list as needed and don't worry about memory use.

Why does creating a list from a list make it larger?

I assume jython uses the same approach, but you'd have to dig into its code to see how that translates to Java.

I mostly answer numpy questions. This is a numerical package that creates fixed sized multidimensional arrays. If a user needs to build such an array incrementally, we often recommend that they start with a list and append values. At the end they create the array. Appending to a list is much cheaper than rebuilding an array multiple times.

Answer 2

Internally python lists are Array of pointers as mentioned by hpaulj

The next question then is how can you extend the an Array in C as explained in the answer. Which explains this can be done using realloc function in C.

This lead me to look in to the behavior of realloc which mentions

The function may move the memory block to a new location (whose address is returned by the function).

From this my understanding is the array object is extended if contiguous memory is available, else memory block (containing the Array object not List object) is copied to newly allocated memory block with greater size.

This is my understanding, corrections are welcome if I am wrong.