wood burning stoves 2.0*
The moose likes Java in General and the fly likes Ordering in ArrayList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Ordering in ArrayList" Watch "Ordering in ArrayList" New topic
Author

Ordering in ArrayList

Mark Herschberg
Sheriff

Joined: Dec 04, 2000
Posts: 6037
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

Joined: Aug 03, 2002
Posts: 7729
I don't know for certain, but perhaps the listIterator() method of ArrayList will provide the iterator you need.


Ask a Meaningful Question and HowToAskQuestionsOnJavaRanch
Getting someone to think and try something out is much more useful than just telling them the answer.
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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.


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451
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


Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Mark Herschberg
Sheriff

Joined: Dec 04, 2000
Posts: 6037
Thank you to everyone for your responses.
--Mark
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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

Joined: Jan 30, 2002
Posts: 3451
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Ordering in ArrayList
 
Similar Threads
Union of two arrays without using a temporary array?
Iterator Pattern
Collection addAll method Strange Behavior
Question on HashSet