First of all, insertion sort on a List
is going to be slow (O(N^2)
) ... no matter how you do it. But you appear to have implemented it as O(N^3)
.
Here is your code ... which will be called N times, to add each list element.
public void insert(Entry e)
{
int i = 0;
for (i = 0; i < list.size(); i++) // HERE #1
{
if(list.get(i).compareTo(e) > 0 ) // HERE #2
{
list.add(i,e); // HERE #3
return;
}
}
list.add(e); // HERE #4
}
At "HERE #1" we iterate up to M times where M is the current (partial) list length; i.e. O(M)
. This is inherent in an insertion sort. However, depending on how you implemented the size()
method, you could have turned the iteration into a O(M^2)
sequence of operations. (The LinkedList.size()
method just returns the value of a size
variable. No problem here. But if size()
counted the elements ... )
At "HERE #2" we have a fetch and a comparison. The comparison (compareTo(...)
) is cheap, but the get(i)
operation on a linked list involves traversing the list from the beginning. That is an O(M)
operation. And since you make the get(i)
call O(M)
times per insert
call, this makes the call O(M^2)
and the sort O(N^3)
.
At "HERE #3" the add(i,e)
repeats the list traversal of the previous get(i)
call. But that's not so bad because you only execute that add(i,e)
call once per insert
call. So the overall complexity is not affected.
At "HERE #4" the add()
operation could be either O(1)
or O(M)
depending on how it is implemented. (For LinkedList.add()
it is O(1)
because the list data structure keeps a reference to the last node of the list.) Either way, overall complexity is not affected.
In short:
The code at #2 definitely make this an
O(N^3)
sort.The code at #1 could also make it
O(N^3)
... but not with the standardLinkedList
class.
So what to do?
One approach is to recode the
insert
operation so that it traverses the list using thenext
andprev
fields, etcetera directly. There should not be calls to any of the "higher level" list operations: size, get(i), add(e) or add(i, e).However, if you are implementing this by extending or wrapping
LinkedList
, this is not an option. Those fields are private.If you are extending or wrapping
LinkedList
, then the solution is to use thelistIterator()
method to give you aListIterator
, and use that for efficient traversal. Theadd
operation on aListIterator
isO(1)
.If (hypothetically) you were looking for the fastest way to sort a (large)
LinkedList
, then the solution is to useCollections.sort
. Under the covers, that method copies the list contents to an array, does anO(NlogN)
sort on the array, and reconstructs the list from the sorted array.