CODEWITHSUNDEEP
java
Johann
Johann

Reputation: 29867

Fastest way to find an item in a sorted ArrayList

In Java, I have an ArrayList with a list of objects. Each object has a date field that is just a long data type. The ArrayList is sorted by the date field. I want to insert a new object into the ArrayList so that it appears in the correct position with regard to its date. The only solution I can see is to iterate through all the items and compare the date field of the object being inserted to the objects being iterated on and then insert it once I reach the correct position. This will be a performance issue if I have to insert a lot of records.

What are some possible ways to improve this performance? Maybe an ArrayList is not the best solution?

Upvotes: 2

Views: 2138

Answers (4)

MSKashef
MSKashef

Reputation: 406

first you should sort ArrayList Using:

ArrayList<Integer> arr = new ArrayList<>();
...
Collections.sort(arr);

Then Your Answer is:

int index = Collections.binarySearch(arr , 5);

Upvotes: 1

Jan Zyka
Jan Zyka

Reputation: 17898

I would consider using TreeSet and make your item Comparable. Then you get everything out of the box.

If this is not possible I would search for the index via Collections.binarySearch(...).

EDIT: Make sure performance is an issue before you start optimizing

Upvotes: 1

Marko Topolnik
Marko Topolnik

Reputation: 200158

Whether or not binary search + O(n) insertion is bad for you depends on at least these things:

  • size of the list,
  • access pattern (mostly insert or mostly read),
  • space considerations (ArrayList is far more compact than the alternatives).

Given the existence of these factors and their quite complex interactions you should not switch over to a binary search tree-based solution until you find out how bad your current design is—through measurements. The switch might even make things worse for you.

Upvotes: 1

Evan Bechtol
Evan Bechtol

Reputation: 2865

I would say that you are correct in making the statement:

Maybe an ArrayList is not the best solution

Personally, I think that a tree structure would be better suited for this. Specifically Binary Search Tree, which is sorted on the object's date time. Once you have the tree created, you can use binary search which would take O(log n) time.

Upvotes: 3

Related Questions