ArrayList vs LinkedList Sorting

[Nick Mario]

I have a list that is going to be added to and read from a lot. The list has to remain sorted. So I have 2 questions: 1) Would it be faster to insert an item in its correctly sorted position or to insert it at the end and sort it after? and 2) Would it be better to use a LinkedList or and ArrayList? Thanks so much for the help!

[Jeanne Boyarsky]

Nick,
Good question. My answer before trying it (which is not correct)
A LinkedList is designed to be iterated through in order making sort an inefficient operation. So ArrayList will definitely be faster for your needs here. Also, sorting at the end is going to be faster because it lets the sort algorithm optimize.

Think about it as if I gave you a deck of playing cards. If you had to put the card in position each time you got one, you'd need to look through the cards in your hand each time. If I just told you to sort at the end, you could make piles by suit or number and then sort those.

I was curious how much faster it would be so wrote a program to try it out.

import java.time.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class PlayTest {

	private static final int SIZE = 1_000_000;
	private static final Random random = new Random();

	public static void main(String[] args) {

		Consumer<List<Integer>> sortAtEnd = list -> {
			for (int i = 0; i < SIZE; i++) {
				list.add(random.nextInt());
			}

			Collections.sort(list);
		};
		
		Consumer<List<Integer>> keepSorted = list -> {
			for (int i = 0; i < SIZE; i++) {
				int numberToAdd = random.nextInt();
				int position = Collections.binarySearch(list, numberToAdd);
				// when not found, index is negative
				int index = (position >=0) ?  position : - position - 1;
				list.add(index, numberToAdd);
			}

			Collections.sort(list);
		};

		timeOperation("Inserted sorted into ArrayList", keepSorted, new ArrayList<Integer>());
		timeOperation("Inserted sorted into LinkedList", keepSorted, new LinkedList<Integer>());
		timeOperation("Sort ArrayList at end", sortAtEnd, new ArrayList<Integer>());
		timeOperation("Sort LinkedList at end", sortAtEnd, new LinkedList<Integer>());
		
	}

	private static void timeOperation(String operation, Consumer<List<Integer>> consumer, List<Integer> list) {

		Instant start = Instant.now();

		consumer.accept(list);

		Instant end = Instant.now();
		System.out.println(operation + ": " + Duration.between(start, end));
	}

}

Originaly, I was thinking to test will a million records, but the LinkedList keeping sorted code takes too long. With 100,000 records, the results were:
Inserted sorted into ArrayList: PT0.376S
Inserted sorted into LinkedList: PT1M39.788S
Sort ArrayList at end: PT0.044S
Sort LinkedList at end: PT0.04S

As you can see, the keeping a LinkedList sorted as you go taking the longest at 1 minute, 39 seconds and keeping an ArrayList sorted as you at second longest at .37 seconds.

Sorting both the ArrayList and LinkedList at the end took a similar amount of time so I re-ran the test (for just those two) with a million rows and got:
Sort ArrayList at end: PT0.334S
Sort LinkedList at end: PT0.48S

And with ten million:
Sort ArrayList at end: PT7.249S
Sort LinkedList at end: PT7.049S

They are pretty close. My answer after trying it:
Sorting at the end is going to be faster because it lets the sort algorithm optimize. As far as choosing, an implementation ArrayList is better because it is optimized for getting an element at a specific index. The implementation of the JDK I'm using turns any type of list into an array before sorting so the time to sort at the end is equivalent for ArrayList and LinkedList. However, getting an arbitrary index is going to be faster with ArrayList.

Re-running with 10,000 elements and this code:

		Consumer<List<Integer>> sortAtEnd = list -> {
			for (int i = 0; i < SIZE; i++) {
				list.add(random.nextInt());
				list.get(i /2);
			}

			Collections.sort(list);
		};

Gives a result of:
Sort ArrayList at end: PT0.061S
Sort LinkedList at end: PT4.576S


So you should choose your data structure by your read access pattern. Do you plan to iterate through the elements in order or at different positions.

[Nick Mario]

Awesome explanation, I really appreciate the work you put into that. So basically what I'm making is a program that catalogs comic books. It has a GUI with a list on it with all the books. So when you click on the book, it retrieves the information of that book and displays it somewhere. The user is constantly adding new books to the collection and sometimes removing them.

So from what I gathered from your explanation, the ArrayList offers superior performance relative to a LinkedList. I guess you would use linkedlist if you were consistently adding things to either the front or back of the list. I believe those are constant time operations for a LinkedList. And then if you wanted to iterate through list in order, it would offer good performance as well. So would you say to use ArrayList exclusively?

[Jeanne Boyarsky]

Nick Mario wrote:I guess you would use linkedlist if you were consistently adding things to either the front or back of the list. I believe those are constant time operations for a LinkedList.

Correct

Nick Mario wrote:So would you say to use ArrayList exclusively?

In your program, yes. ArrayList is often the best choice.

You might consider using a HashMap though. That way you can look up the book by key. Or a TreeMap so you can look up by key and sort at the same time.

[Nick Mario]

I just finished a class where we learned about all these data structures and I don't have a great feel for when to use them all. I don't think a hashmap would give much more of a performance gain because basically the way the comics are listed in the JTable is the way they're sorted in the arraylist. So if you click on the first item, it selects the first item in the arraylist. Definitely correct me if I'm wrong. What exactly is a treemap though? I don't think I've ever heard of that. How would I benefit from that compared to an arraylist?

[Jeanne Boyarsky]

Nick,
Givne you have the index, I agree a map wouldn't be faster. A TreeMap is like a HashMap except the keys are sorted.

[Tim Holloway]

There is no optimal one-size-fits-all solution, One of my favorite examples is a major application from back in my mainframe days where I had to produce an ordered collection of 4-character report IDs as part of a larger process to route and output the corresponding reports. The IDs were mostly generated in collating sequence, but right smack in the middle of the list was a clot of stuff that needed to be at the end.

If you dissect the 4 most common sort algorithms, you'll see that Heap and Quick sorts perform horribly on nearly sequential data - their best performance is on mostly random stuff. On the other hand, a bubble sort is bad at handling mostly-random data and it's also bad when the data is mostly in order except for items that are at the wrong end of the list (since they have to be painfully bubbled step by step to the other end).

So for this case, the optimal sort was a Shell-Metzner sort. Like the bubble sort, if data is mostly organized, it doesn't start off by stacking everything in grossly unequal-sized piles (which is why Quick and Heap do so bad there). But since the Shellsort does a binary divide-and-conquer approach to bubbling, data movement of off-end stuff is greatly accelerated.

Another lesson I learned even earlier is a common one to anyone who's loaded an empty database. If you have indexing turned on when you load, the task of continually re-organizing the index(es) as the data loads can be punitive. But if you load without indexes and then create the indexes against the loaded data, that's usually much faster.

Analogously, it might be worthwhile to convert a linked list to an arraylist (or even a simple array*), sorting the data, then constructing an entirely new linked list.

As always, the real optimal approach isn't the one that "looks" optimal, however. When in doubt, benchmark.

===
* I'm assuming no additions or deletions while the sorting is going on, so there's no real need for an ArrayList. Aside from the OOP methods, the only major difference between a straight array and an ArrayList is that an array has a fixed number of slots, but an ArrayList can have slots added and removed (although it's expensive to do frequently).