• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Ordering in ArrayList

 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.)

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
Ranch Hand
Posts: 7729
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know for certain, but perhaps the listIterator() method of ArrayList will provide the iterator you need.
 
Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 3451
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

Here's the get() method:

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
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you to everyone for your responses.
--Mark
 
Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 3451
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic