why the list behaves differently in python and Java?

Question

I am learning the scripting language, python. I know Java quite a bit. I am trying to translate one bit of code from Java to python. but they behave erratically (or my understanding could be totally wrong) I have the following code in Java, where I am adding elements to a ArrayList indefinitely. so this causes outofmemory error, which I expect:

import java.util.*;
public class Testing{
public static void main(String[] args){
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(5);
        list.add(4);
        for (int i=0;i<list.size();i++){
            list.add(5);
        }
}
}

now the same code translated in python:

lst = []
lst.append(5)
lst.append(4)
for i in range(len(lst)):
    lst.append(5)
print lst

here I get the output: [5, 4, 5, 5]

from what I see, is the list not passed as a reference to the for loop in python?

similarly here,

>>> l=[1,2,3]
>>> for i in l[:]:
...    l.append(4)
...    print l
... 
[1, 2, 3, 4]
[1, 2, 3, 4, 4]
[1, 2, 3, 4, 4, 4]

in each iteration inside the for loop, I am increasing the list size, so the iteration should go forever correct?

Answer 1

A python for loop evaluates the expression that yields the iterable over which to loop once only. You can manipulate the lst object in the loop without affecting the outcome of what for is looping over. This differs from the Java for construct (which is a very different construct from the Python for statement, which is really a Foreach construct), which evaluates the 3 associated expressions for each iteration.

In your first example, you created a range() result, and once that is created it is not updated for each loop iteration.

In your second example, you created a copy of lst using a full-length slice (lst[:]) for the loop to iterate over. The copy is not re-created for each loop iteration.

There is a caveat here, however. The for loop calls iter() on the object-to-be-iterated-over. For a list object, the resulting list iterator does keep a reference to the original list, as well as an iteration index. Every time the for loop advances the iterator (calling next() on it), the iteration index is incremented and looked up on the original list, until the index is equal to the list length. If you keep adding to the list in the loop, that would create an infinite loop.

You can see this if you do not create a copy of the list to iterate over:

>>> L = [1, 2, 3]
>>> for i in L:
...     L.append(4)
...     print L
...     if len(L) > 30:
...         break
... 
[1, 2, 3, 4]
[1, 2, 3, 4, 4]
[1, 2, 3, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]

Here, the iterator created for L keeps yielding the next element as L is extended in the loop, and if I had not added a length limit in the loop this would have continued forever.

Answer 2

It may be easiest to explain this by translating the for loops into their equivalent while loops.

In Java:

for (int i=0;i<list.size();i++){
    list.add(5);
}

int i=0;
while (i<list.size()) {
    list.add(5);
    ++i;
}

In Python pseudocode:

for i in range(len(lst)):
    lst.append(5)

_r = range(len(lst))
_i = iter(r)
while _i isn't done:
    next(_i)
    lst.append(5)

In practice, you don't really need to understand how iter* and next work, or the details of how the "_i isn't done" part works**; the key is that a for loop creates an iterator, then iterates over it. In your case, it's creating an iterator over a range object (or, in Python 2.x, the list returned by the range function).

But even without knowing that, you can see that your len(lst) is only being evaluated once at the start, to create the iterator, while the Java list.size() equivalent is being evaluated each time through the loop.

---

If you want the equivalent of a Java-style for loop, you have to write the while loop explicitly.

---

* iter creates an iterator over any iterable (a list, a range, even another iterator). An iterator is sort of like a smart object that has a reference to the iterable and a "current position" within it, although under the covers they're rarely implemented that way. Calling next on an iterator effectively returns the value at the current position and advances the iterator to the next one (or the equivalent for however the iterator is actually implemented).

** What actually happens is, in effect, a try:/except StopIteration:, because calling next on an iterator that's done raises StopIteration. Of course it's implemented in C (or Java or .NET or RPython, for other Python implementations), and the C actually uses some special magic code for looping over an iterator that makes it a little faster, but almost nobody ever needs to think about that part.

Answer 3

> is the list not passed as reference to the for-loop in python?

All objects are passed by reference in Python, and in Python everything is an object. (Java primitive values are not, but even plain integer and float values are objects in Python.)

> in each iteration inside for-loop, I am increasing the list size, so the iteration should go forever correct?

You are increasing the size of l, that's correct, but l[:] is evaluated just once and produces a shallow copy of l. That copy isn't changed in the loop, so changes to l inside the loop do not change the set of values that the loop variable will take on.

Change l[:] to just l in that loop, and then you'll see a lot of output.

Answer 4

range(len(lst)) creates the range once, and then iterates over that whereas in java list.size() is evaluated at each iteration