How to optimize $O(N)$ insertion time in a custom Java Singly Linked List used as a Priority Queue?

Your insertWithPriority is linear with List-size, because you iterate the list. Therefore, inserting N elements can be expected to be quadratic, and that is exactly what you measure. To optimize this code, you have to get the complexity of insertWithPriority down. Iteration of the whole list is not an option. So how can you go about this?

You want to maintain a sorted list by inserting a new element into the right position. If you use a linked list, insertion itself is O(1) but you can only find the right position by O(N) iteration¹. If you use an array-based list, you can O(logN) find the right index to insert the element using binary search, but the actual insertion is O(N), so that will not do. Neither of these simple datastructures can provide you with a sublinear insert operation.

There are a variety of tree-based datastructures that will allow you to have O(logN) insertions while maintaining order. A simple binary tree comes to mind, though that is not a good datastructure both in practice and in theory. B-Trees, Red-Black-Trees and Skip-lists are some examples of advancements on the binary tree idea. You will have to use one of those if you want to maintain an ordered list. With one of those, you will get O(NlogN) runtime for your benchmarks.

But the real trick of implementing a priority-queue is understanding that you do not need to maintain a fully sorted list at all times. It is sufficient for a queue to support only the following operations in addition to insert:

head - get the first element
pop - remove the first element

All three of those operations are sublinear on a datastructure called "Heap" or "Priority Queue". head is O(1), pop and insert are O(logN). Thus you will observe O(NlogN) in your benchmark. This datastructure is explained in depth elsewhere, so I will only give the gist here: The "Heap" is a tree with the invariant that parent-nodes hold bigger values than the children. You get nice and simple implementations for all three operations if you follow this. Additionally, there is a nice trick to implement the whole tree on top of an array. This doesn't give you any theoretical big-O-gains, but practical gains. There are also advanced versions of the heap that push insert down to O(1), see https://en.wikipedia.org/w/index.php?title=Priorityqueue&section=8#Summaryofrunningtimes.

^{1 LinkedLists also interact very poorly with garbage-collection and CPU-caches. This is why they are always slow in practice and people blanket-advice not to use them, but that is not relevant to the discussion of algorithmic complexity.}