insertion sort on linked list

Question

//I wrote java code for insertion method on doubly linked list but there is a infinite loop //when I run it. I'm trying to find a bug, but have not found so far. any suggestions? //it is calling a helper function

 public IntList insertionSort ( ) {
    DListNode soFar = null;
    for (DListNode p=myHead; p!=null; p=p.myNext) {
        soFar = insert (p, soFar);
    }
    return new IntList (soFar);
}


// values will be in decreasing order.
private DListNode insert (DListNode p, DListNode head) {
    DListNode q=new DListNode(p.myItem);
    if(head==null){
        head=q;
        return head;
    }
    if(q.myItem>=head.myItem){
        DListNode te=head;
        q.myNext=te;
        te.myPrev=q;
        q=head;
        return head;
    }
    DListNode a;
    boolean found=false;
    for(a=head; a!=null;){
        if(a.myItem<q.myItem){
            found=true;
            break;
        }
        else{
            a=a.myNext;
        }
}
    if(found==false){
        DListNode temp=myTail;
        temp.myNext=q;
        q.myPrev=temp;
        myTail=q;
        return head;
    }
    if(found==true){
    DListNode t;
    t=a.myPrev;
    a.myPrev=q;
    t.myNext=q;
    q.myPrev=t;
    q.myNext=a;
}
    return head;

}

Answer 1

Your code is a bit hard to read through but I noticed a few problems

First: handling the case where you are inserting a number at the head of the list:

if(q.myItem>=head.myItem){
        DListNode te=head;
        q.myNext=te;
        te.myPrev=q;
        q=head;
        return head;
    }

specifically the line q=head; and the return. q=head can be removed, and it should return q not head because q is the new head. I think what you meant to do was head=q; return head;. The current code will essentially add the new node on the front but never return the updated head so they will "fall off the edge" in a way.

Second: I am assuming myTail is some node reference you are keeping like myHead to the original list. I don't think you want to be using it like you are for the sorted list you are constructing. When you loop through looking for the place to insert in the new list, use that to determine the tail reference and use that instead.

DListNode lastCompared = null;
for(a=head; a!=null; a=a.myNext) {
    lastCompared = a;
    if(a.myItem<q.myItem) {
        break;
        }
    }
if( a )
    {
    // insert node before a
    ...
    }
else
    {
    // smallest value yet, throw on the end
    lastCompared.myNext = q;
    q.myPrev = lastCompared;
    return head;
    }

Finally make sure myPrev and myNext are being properly initialized to null in the constructor for DListNode.

disclaimer I didn't get a chance to test the code I added here, but hopefully it at least gets you thinking about the solution.

---

A couple stylistic notes (just a sidenote):

1. the repeated if->return format is not the cleanest in my opinion. I generally try and limit the exit points in functions
2. There are a lot of intermediate variables being used and the names are super ambiguous. At the very least try and use some more descriptive variable names.
3. comments are always a good idea. Just make sure they don't just explain what the code is doing - instead try and convey thought process and what is trying to be accomplished.