CODEWITHSUNDEEP
javacollectionsarraylistsorting
John K
John K

Reputation: 11

If a sorted Collection of an ArrayList expands past its initial size, does it become unsorted?

I have an ArrayList that I sort initially. When I add to it, I do:

Index = Collections.binarySearch(Data.fileList, fileEntry, FileData.COMPARE_BY_FNAME);

if (Index >=0)
  fileEntry = Data.fileList.get(Index)  // get the object that matches
else
  Data.fileList.add ((Index+1)*-1, fileEntry)  // add the new object

which adds the entry into the correct location so I don't have to sort again (I believe).

When the ArrayList gets big I end up with duplicate entries, so I assume it is no longer sorted.

I think that when the ArrayList gets past its initial size and is expanded, that my collection is no longer sorted.

Q1) Is this true? Q2) Is there a way to tell if the collection is no longer sorted? Is there a way to tell if the ArrayList has been expanded? Or do I have to do a sort after every insert? Q3) The ArrayList.size() returns the number of elements in the list. Is there a way to tell the capacity of the list?

Thanks. -J

Upvotes: 1

Views: 164

Answers (4)

Matt
Matt

Reputation: 11805

The resizing has nothing to do with it. Sort order is not part of the List contract. A list is simply an ordered collection. The order is up to who is adding the elements. When an ArrayList resizes, it simply re-allocates the underlying array, and copies the existing data over to the new array in the same order.

As mentioned above, you should be using a SortedSet (specifically TreeSet) if you want to keep things sorted as you add them. If you want to allow duplicates the TreeBag class in commons-collections is a good option.

Upvotes: 0

Platinum Azure
Platinum Azure

Reputation: 46193

If you want a collection that is always sorted, ArrayList is not the tool you really want to use. There are collections which specialize in remaining sorted.

If you want to allow duplicates, PriorityQueue is your best bet. If you are okay with ignoring duplicates, TreeSet might be a better option.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1501646

When the ArrayList gets big I end up with duplicate entries, so I assume it is no longer sorted.

It stays sorted for as long as you keep adding things in the right location. It's not really clear what you mean by "duplicate entries" here - but there's nothing about expanding an ArrayList which will reorder it.

On the other hand, using a sorted collection to start with (as suggested by Óscar López) would make your life simpler.

Upvotes: 1

Óscar López
Óscar López

Reputation: 236034

Consider using a data structure that guarantees sorted insertion, like a TreeSet. Other than that, I'm guessing that the problem is in your algorithm for sorted insertion in an ArrayList, and it is not related to the fact that the ArrayList is growing.

Upvotes: 4

Related Questions