asked on

compareTo with linked list.

Hey, Im trying to figure out how to get my compareTo method to work right for my circular doubly linked list. The one I have works fine when I use it on my bubbleSort() method, but it wont work on any other sort I try. The sorts Ive tried are selectionSort(), selectionSortNoSelfSwaping(), and insertionSort(). I get stuck in an infinit loop when I hit the compareTo part of those 3 sorts I mentioned. Well here is the compareTo method im using.
If you need more info about my program ill be on for at least 5 or so hours and can repost more code.
Thanks

public class DLL implements Comparable<Node>//Implementing the comparable interface
{
Node head;
int size;

//all the normal things u have with a circular doubly linked list with dummy head. 
// also have the Node class with all the basic things.


public int compareTo(Node that) 
{		      				
return ((Comparable)this.head).compareTo((Comparable)that.data);
}	

}//end DLL

//The Node class has fields of

Node next;
Node prev;
Object data

Open in new window

Mick Barry

> public class DLL implements Comparable//Implementing the comparable interface

the Node class should implement Comparable, not the DLL class

theldro

ASKER

I put the almost the same code in both of them because I wasnt sure which one was supposed to implement it. This is what it looks like in the Node class.

public class Node implements Comparable<Node>
{
Node next;
Node prev;
Object data;

public int compareTo(Node that) 
{ 
return ((Comparable)data).compareTo((Comparable)that.data);		             
}
}

Open in new window

ASKER CERTIFIED SOLUTION

Mick Barry

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

theldro

ASKER

If the compareTo is ok than I must have 3 bad sorting routines. I thought they were good since they all got into the infinate loop at the compareTo spot. Ill post 2 of them.

public void insertionSort()
			{  Node back = head;

			   if (size < 2)
			      return;
			   back = back.next;           // SECOND entry in the list
			   while ( back != null )      // I.e., end-of-list
			   {  Comparable value = back.data;
			      Node curr = head;        // Start at the front
			      
			      // Find insertion point for value;
			      while (curr != back && value.compareTo(curr.data) >= 0)
			         curr = curr.next;
			      // Propogate values upward, inserting the value from back
			      while (curr != back)
			      {  
			    	 Comparable hold = curr.data;
			         curr.data = value;
			         value = hold;
			         curr = curr.next;
			      }
			      back.data = value;      // Drop final value into place!
			      back = back.next;       // Move sorted boundary up
			   }
			} // end insertSort()





public void selectSort()
{  Node front = head;

   // Nothing to do on an empty list
      if ( front == null )
         return;
      while ( front.next != null )     // skips a one-entry list
      {
         Node       tiny = front,
                    curr = front.next;
         Comparable temp = front.data; // start the swap

         for ( ; curr != null ; curr = curr.next )
         {  if ( tiny.data.compareTo(curr.data) > 0 )
               tiny = curr;
         }
         front.data = tiny.data;       // Finish the swap
         tiny.data = temp;
         front = front.next;           // Advance to the next node
      }
      // The structure is unchanged, so the validity of tail is unchanged.
   }
}

Open in new window

theldro

ASKER

Thanks for the help with all the questions ive had.