Menu
I want to use data structure that needs to be sorted every now and again. The size of the data structure will hardly exceed 1000 items.
Which one is better - ArrayList or LinkedList?
Which sorting algorithm is better to use?
239
ArrayList provides constant time for search operation, so it is better to use ArrayList if searching is more frequent operation than add and remove operation. The LinkedList provides constant time for add and remove operations. So it is better to use LinkedList for manipulation.
LinkedList is faster than ArrayList while inserting and deleting elements, but it is slow while fetching each element.
Merge sort is one of the most famous divide-and-conquer sorting algorithms. This algorithm can be used to sort values in any traversable data structure (i.e., a linked list).
In most cases, List<T> is more useful. LinkedList<T> will have less cost when adding/removing items in the middle of the list, whereas List<T> can only cheaply add/remove at the end of the list.
Up to Java 7, it made no difference because Collections.sort would dump the content of the list into an array.
With Java 8, using an ArrayList should be slightly faster because Collections.sort will call List.sort and ArrayList has a specialised version that sorts the backing array directly, saving a copy.
So bottom line is ArrayList is better as it gives a similar or better performance depending on the version of Java.
170
If you're going to be using java.util.Collections.sort(List) then it really doesn't matter.
If the The list will get dumped into an array for purposes of sorting anyway. List does not implement RandomAccess, then it will be dumped to a List
(Thanks for keeping me honest Ralph. Looks like I confused the implementations of sort and shuffle. They're close enough to the same thing right?)
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
