Best list implementation for ordered objects in Java?

Question

The situation I have is that I currently have a LinkedList of 'Appointment' objects which have the following attributes:

'patient' 'date' 'type'

The only functionality required is to loop through this LinkedList and display each appointment in order of 'date'. So, each time a new Appointment is created (using a method called 'addAppointment' in the same class as the LinkedList of appointments), the method will sort the linked list using a Comparator.

However, I was wondering if this is bad practice and if there is a better way to do this? I never need to get the 'Appointment' object by its index and so would it be better practice to use a Priority Queue?

possible duplicate of [A good Sorted List for Java](http://stackoverflow.com/questions/2661065/a-good-sorted-list-for-java) — Elliott Frisch, Mar 19 '14 at 20:29
I also forgot to add that the attributes may need to be modified, like if an appointment changes date or type. — user2969720, Mar 19 '14 at 20:30
@ElliottFrisch In this case, the elements are all going to be distinguishable, and I think `SortedSet` makes the most sense. — chrylis -cautiouslyoptimistic-, Mar 19 '14 at 20:30
@chrylis I don't disagree, but that's an interface. I assume you mean [TreeSet](http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html). — Elliott Frisch, Mar 19 '14 at 20:32

score 1 · Accepted Answer · answered Mar 19 '14 at 20:38

1

I would disagree with everyone here so far and say go ahead and use a simple ArrayList. Your main use case is just to loop through the list and display it in order, right? You can sort an array list by using the Collections.sort() method, which will sort any list of objects implementing Comparable. So just implement Comparable in your Appointment object (only need to provide a .compareTo() method...the API explains this well, or the Java Trail on Collections) and your sorting will then be painless and easy. My experience is this is better performing than an object like TreeSet or a LinkedList.

Now those would be better performing if you were always inserting into the middle of the list a lot, but you seem to mostly be reading this list from what you said, so go for the ArrayList.

answered Mar 19 '14 at 20:38

Scott Shipp

2,241
1
13
20

This very good method indeed for sets of objects that you need to sort for example only a few times per program run. The problem with `TreeMap` or similar containers is that they pretty much sort the list every time you add a new entry there. – The amateur programmer Mar 19 '14 at 20:50
I do need to sort the list every time I add a new entry because the application requires new Appointment objects to be created in run-time and then added to the list. – user2969720 Mar 20 '14 at 06:51
ArrayList may not be best then. TreeSet may be better. It may also be meaningless. Adding to a TreeSet does maintain sorted order, but I would consider how often the list is simply read versus how often items get added. If there are enough additions, you may see better performance with TreeSet, once you get enough items (we're talking a lot). Sorting with Collections.sort() is O(n log n). Adding to a TreeSet is O(log n). By the way if you do use TreeSet, watch out how you implement hashcode and equals. If you only compare items on date, two items with same date will overwrite each other. – Scott Shipp Mar 20 '14 at 17:46

score 0 · Answer 2 · answered Mar 19 '14 at 20:30

Generally speaking, use an ArrayList when you need random access and a LinkedList when there will be lots of inserts and removes. If you need a data structure that stays sorted, PriorityQueue is an option, but it's really intended for the scenario where you're just pulling the top element off sequentially. If you're needing to repeatedly iterate over the elements, use a SortedSet.

If a field involved in the element's ordering changes after it's inserted into any sorted collection, you should remove and re-add the element (preferably removing before modification).

A `SortedSet` will be fine as long as "duplicates" are not allowed however — fge, Mar 19 '14 at 20:32

score 0 · Answer 3 · answered Mar 19 '14 at 20:32

Use a PriorityQueue

Write a compareTo method for your Appoitnment object that specifies the natural ordering according to date.

PriorityQueue<Appointment> schedule = new PriorityQueue<Appoitnment>();
Appointment a1 = new Appointment();
Appointment a2 = new Appointment();
schedule.add(a1);
schedule.add(a2);

// Iteratively removes the earliest appointment remaining in the schedule
while (schedule.peek != null) {
  System.out.println(schedule.poll().toString());
}

Best list implementation for ordered objects in Java?

3 Answers3