Ordering in ArrayList

[Mark Herschberg]

I want to confirm the following:
(Note: I type in this code by hand, so there may be typos or other silly mistakes, but I think the idea is clear.)

ArrayList list_1 = new ArrayList();
ArrayList list_2 = new ArrayList();
list_1.add("A");
list_1.add("B"); 
list_2.add("X");
list_2.add("Y");
list_2.add("Z");
list_1.addAll(list_2);
Iterator iter = list_1.iterator();
while (iter.hasNext()) {
   iter.next().toString();
}

Is the ordering in the Iterator guaranteed to be: A,B,X,Y,Z. Looking at the Javadocs for ArrayList's addAll(Collection) method, it states:

Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator. The behavior of this operation is undefined if the specified Collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection is this list, and this list is nonempty.)

But I couldn't find any place which described the ordering returned by ArrayList's iterator method. It would be logical to assume that it is the same as the order in the ArrayList, and this seems to be the case, but is it guaranteed?
--Mark

[Barry Gaunt]

I don't know for certain, but perhaps the listIterator() method of ArrayList will provide the iterator you need.

[Thomas Paul]

All List objects are ordered collections and they are guaranteed by contract to return an iterator that returns the elements in "proper sequence". Proper sequence in an ArrayList is the order the items were put into the list. Position is critical in List objects because you can access and change items by position.

[Michael Morris]

Hi Mark,
I think you can safely assume that an ArrayList iterator will return the objects in the same order they were entered. ArrayList is backed by an Object[] array. Here's the code for the addAll() methods:

    public boolean addAll(Collection c) {
modCount++;
int numNew = c.size();
ensureCapacity(size + numNew);
Iterator e = c.iterator();
for (int i=0; i<numNew; i++)
    elementData[size++] = e.next();
return numNew != 0;
    }
    public boolean addAll(int index, Collection c) {
if (index > size || index < 0)
    throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
int numNew = c.size();
ensureCapacity(size + numNew);  // Increments modCount!!
int numMoved = size - index;
if (numMoved > 0)
    System.arraycopy(elementData, index, elementData, index + numNew,
     numMoved);
Iterator e = c.iterator();
for (int i=0; i<numNew; i++)
    elementData[index++] = e.next();
size += numNew;
return numNew != 0;
    }

Here's the get() method:

    public Object get(int index) {
RangeCheck(index);
return elementData[index];
    }

ArrayList.iterator() is implemented in AbstractList and according the the docs for that method:

Returns an iterator over the elements in this list in proper sequence.
This implementation returns a straightforward implementation of the iterator interface, relying on the backing list's size(), get(int), and remove(int) methods.

I went thru the code for the iteraror() method in AbstractList and it does indeed just call get() sequentially and since ArrayList's get() just returns the value in the backing array at the specified index then I think we can safely say that an ArrayList iterator will guarantee the proper order.
Hope this helps,
Michael Morris

[Mark Herschberg]

Thank you to everyone for your responses.
--Mark

[Thomas Paul]

Michael, you need to be careful about relying on the implementation for a piece of code. Even though it works one way today is no guarantee that it will work the same way tomorrow.
In this case we know that the ArrayList iterator will always be in order of the items entered into the ArrayList because that is the requirement of the List interface. The List contract says that items must be returned in proper sequence. The proper sequence must be by order of entry into the List since Lists are positional. By the way, if Lists were not ordered by entry then you couldn't use Lists to simulate stacks and queues.

[Michael Morris]

Hi Thomas,
I agree with what you said. I was merely showing that the current implementation of ArrayList.iterator() does fulfill that contract.
Michael Morris