I have to perform an insertion sort in a linked list. Having problems. any help?
It's the same principle as with an array but you update the list pointers instead of shifting the array elements.
If you need more specific answers, you need to ask more specific questions. No one here is going to write the sort for your homework assignment, so post the code you have and what questions you have about it.
I can insert the items into the list but not in a sorting method.
this is what i have so far
public static <T extends Comparable<? super T>>
void insert(LinkedList<T> list, T item)
{
T data = (T)item;
if (data.compareTo(item) <= 0)
list.addLast(item);
}
That is an insert into a list- not an insertion sort - and you are comparing the item to itself, which is probably less than useful.
The insertion sort should do an in-place sort of an existing list.
If all you need to do is insert into an existing sorted list then simply walk the list until you find the correct place and insert the new item.
well the list is empty. so...
here is what i'm thinking of doing
if (list.isEmpty())
list.add(item);
else
list.addLast(item);
but that doesn't insert it in the right place
If the assignment is to implement an insertion sort on a linked list, you need to read your notes on what an insertion sort is. Inserting into a list is not an insertion sort. If that is not the assignment then you need to rephrase the question to clarify what you need to accomplish.
Basically you check to see if the linked list is empty, if it is you add the first item. Then you insert the remaining item in the right place to keep the list sorted in increasing order