2

I need to maintain a list of objects in a multi-threaded environment. I have read about CopyOnWriteArrayList and it seemed to be an option to go for. The problem is, I needed to sort the list, too. I cannot use Collections.sort() for CopyOnWriteArrayList as it doesn't support the set() operation. I have found few ways to sort the CopyOnWriteArrayList. But performance-wise, they don't look to be good.

My question: is there an alternative data-structure which will come handy in this situation? Basically, I need to keep a sorted list in an multi-threaded environment. A list adapter will use that data structure. So, it should have provide methods like "get(position)".

I recently read about another data structure ConcurrentSkipListSet. Can anyone explain what are the pros and cons of it? Will it be a good fit for my problem?

Hungry Coder
  • 1,800
  • 17
  • 22
  • A `Set` maintains a collection of unique objects. In the case of a `SortedSet` the equality condition is defined as `a.compareTo(b) == 0` and the `Set` maintains the invariant that no two objects in the set are equal. If this suits your purpose then a `ConcurentSkipListSet` is perfect. If it does not then using `Collections.sort` and manual synchronisation will be _very_ slow - you will need your own data structure. – Boris the Spider Aug 19 '14 at 18:52
  • You haven't yet explained what makes CopyOnWriteArrayList the right option to go for in your multi-threaded environment. Without that information, it is difficult to suggest an alternative data structure. – Chan Aug 19 '14 at 19:42
  • @BoristheSpider Thanks! I can always override the equals() method in my object to make it suitable for the set, so that won't be a problem I think. I tried to use `ConcurentSkipListSet`. Now, there is a new problem. As this is a SortedSet, it doesn't provide a `.get(position)` method which is required when I want to use the data-structure in my list adapter. Looks like I would need to write a custom data-structure of my own. – Hungry Coder Aug 20 '14 at 13:55
  • @Chan I mentioned the requirement. I am working in a multi-threaded environment. I need to maintain a list of objects which are sortable. Whenever any object is inserted in the list, I should be able to sort the list. `CopyOnWriteArrayList` looked close to meet the requirements except the issue with sorting. – Hungry Coder Aug 20 '14 at 14:01
  • Yes, a `Set` is not indexed. Also it does not use `equals`, as I pointed out - it uses `compareTo`. A `SortedSet` is **very** different to a `List`. You should be able to write a simple wrapper over an `ArrayList` that uses a `ReentrantReadWriteLock` and a variant on an Insertion Sort to achieve `O(n)` `add` (amortised). If you need faster performance than that you are going to have to look at more advanced tree/heap structures. – Boris the Spider Aug 20 '14 at 15:08

2 Answers2

1

I know that you ask about performance, and I am not sure on how well my method does on that, but here's what I use:

List arrayList = Arrays.asList(cowArrayList.toArray());
Collections.sort(arrayList, new MyComparator());
cowArrayList.clear();
cowArrayList.addAll(arrayList);
Daniël van den Berg
  • 2,197
  • 1
  • 20
  • 45
  • Since Collections.sort(List) creates a temporary array, you can save a bit of memory (and time) by skipping that step and using an array directly: `Object[] arr = cowArrayList.toArray(); Arrays.sort(arr);` And if you can use Java 8, then just do `cowArrayList.sort(comparator);` – Klitos Kyriacou Jul 19 '16 at 17:03
-1

Solution 1: If you want to sort the list during insertion of every element, you can do a binary search and add the element at a sorted location every time. The assumption is that the list is always sorted. Please have a look at http://www.javacreed.com/sorting-a-copyonwritearraylist/.

Alex Vincent
  • 41
  • 1
  • 1
  • 5
  • The solution you referenced is not thread safe thus useless if we need a thread safe list implementation – MounirReg Jun 30 '15 at 07:27