Help With Recursively Sorted Linked List

[Rachel Green]

The method I have right now is sorting the list but doing it backwards. I want it to print alphabetically. I've tried changing parts of the code but I end up just making it unable to compile.

Current code:

/**
   The LinkedList1 class implements a Linked list.
*/

class LinkedList1
{
    
    private class Node
    {
        String value;   
        Node next;      
        
        /**
           Constructor.            
           @param val The element to store in the node.
           @param n The reference to the successor node.
        */
        
        Node(String val, Node n)
        {
            value = val;
            next = n;
        } 
        
        /**
           Constructor. 
           @param val The element to store in the node.
        */
        
        Node(String val)
        {
           // Call the other (sister) constructor.
           this(val, null);            
        }
    }	
	 
    private static Node first;  // list head
    private static Node last;   // last element in list
	     
    /**
       Constructor.
    */
    
    public LinkedList1()
    {
        first = null;
        last = null;        
    }
    
    /**
       The isEmpty method checks to see 
		 if the list is empty.
		 @return true if list is empty, 
		 false otherwise.
    */
    
    public boolean isEmpty()
    {        
        return first == null;       
    }
    
    /**
       The size method returns the length of the list.
       @return The number of elements in the list.
    */
    
    public int size()
    {
       int count = 0;
       Node p = first;     
		 while (p != null)
       {
           // There is an element at p
           count ++;
           p = p.next;
       }
       return count;
    }
    
    /**
       The add method adds an element to
		 the end of the list.
       @param e The value to add to the
		 end of the list.       
    */
    
    public void add(String e)
    {
      if (isEmpty()) 
      {
          first = new Node(e);
          last = first;
      }
      else
      {
          // Add to end of existing list
          last.next = new Node(e);
          last = last.next;
      }      
    }
    
    /**
       The add method adds an element at a position.
       @param e The element to add to the list.
       @param index The position at which to add 
		 the element.
       @exception IndexOutOfBoundsException When 
		 index is out of bounds.  
    */
    
    public void add(int index, String e)
    {
         if (index < 0  || index > size()) 
         {
             String message = String.valueOf(index);
             throw new IndexOutOfBoundsException(message);
         }
         
         // Index is at least 0
         if (index == 0)
         {
             // New element goes at beginning
             first = new Node(e, first);
             if (last == null)
                 last = first;
             return;
         }
         
         // Set a reference pred to point to the node that
         // will be the predecessor of the new node
         Node pred = first;        
         for (int k = 1; k <= index - 1; k++)        
         {
            pred = pred.next;           
         }
         
         // Splice in a node containing the new element
         pred.next = new Node(e, pred.next);  
         
         // Is there a new last element ?
         if (pred.next.next == null)
             last = pred.next;         
    }
    
    
    public static Node reverse(Node curr, Node prev) {
 
        /* If last node mark it head*/
        if (curr.next == null) {
            first = curr;
 
            /* Update next to prev node */
            curr.next = prev;
            return null;
        }
 
        /* Save curr->next node for recursive call */
        Node next1 = curr.next;
 
        /* and update next ..*/
        curr.next = prev;
 
        reverse(next1, curr);
        return first;
    }
    
    /**
       The toString method computes the string
       representation of the list.
       @return The string form of the list.
    */
    
    public String toString()
    {
      StringBuilder strBuilder = new StringBuilder();
      
      // Use p to walk down the linked list
      Node p = first;
      while (p != null)
      {
         strBuilder.append(p.value + "\n"); 
         p = p.next;
      }      
      return strBuilder.toString(); 
    }
    
    /**
       The remove method removes the element at an index.
       @param index The index of the element to remove. 
       @return The element removed.  
       @exception IndexOutOfBoundsException When index is 
                  out of bounds.     
    */
    
    public String remove(int index)
    {
       if (index < 0 || index >= size())
       {  
           String message = String.valueOf(index);
           throw new IndexOutOfBoundsException(message);
       }
       
       String element;  // The element to return     
       if (index == 0)
       {
          // Removal of first item in the list
          element = first.value;    
          first = first.next;
          if (first == null)
              last = null;             
       }
       else
       {
          // To remove an element other than the first,
          // find the predecessor of the element to
          // be removed.
          Node pred = first;
          
          // Move pred forward index - 1 times
          for (int k = 1; k <= index -1; k++)
              pred = pred.next;
          
          // Store the value to return
          element = pred.next.value;
          
          // Route link around the node to be removed
          pred.next = pred.next.next;  
          
          // Check if pred is now last
          if (pred.next == null)
              last = pred;              
       }
       return element;        
    }  
    
    /**
       The remove method removes an element.
       @param element The element to remove.
       @return true if the remove succeeded, 
		 false otherwise.
    */
    
    public boolean remove(String element)
    {
       if (isEmpty()) 
           return false;      
      
       if (element.equals(first.value))
       {
          // Removal of first item in the list
          first = first.next;
          if (first == null)
              last = null;       
          return true;
       }
      
      // Find the predecessor of the element to remove
      Node pred = first;
      while (pred.next != null && 
             !pred.next.value.equals(element))
      {
          pred = pred.next;
      }

      // pred.next == null OR pred.next.value is element
      if (pred.next == null)
          return false;
      
      // pred.next.value  is element
      pred.next = pred.next.next;    
      
      // Check if pred is now last
      if (pred.next == null)
          last = pred;
      
      return true;       
    }
    

// This is the method that isn't working right 

    private static Node order(Node node, String value) {
    if (node == null) { 
        return first;
    }
    int temp = node.value.compareTo(value);
    if (temp > 0) { 
        Node newNode = first;
        newNode.next = node;
        return newNode;
    }
    node.next = order(node.next, value);
    return node;
}
    
    public static void main(String [] args)
    {
        LinkedList1 ll = new LinkedList1();
        ll.add("Amy");
        ll.add("Bobby");
        ll.add("Charlie");
        ll.add("Danielle");
        ll.add("Edward");
        System.out.println("The members of the list are:");
        System.out.println(ll);
        System.out.println("Reversed linked list:");
        ll.reverse(first, null);
        System.out.println(ll);
        System.out.println("Sorted linked list:");
        ll.order(null, null); //Not sure how to call it
        System.out.println(ll);
    }
}

Current output:

The members of the list are:
Amy
Bobby
Charlie
Danielle
Edward

Reversed linked list:
Edward
Danielle
Charlie
Bobby
Amy

Sorted linked list:
Edward
Danielle
Charlie
Bobby
Amy

[Rachel Green]

UPDATE: I just realized the sort method isn't actually doing anything. The print call below is just printing the list as it appears after the reverse method (which does work). So I'm back to square 1 with the sorting. I want to take what's in the linked list and recursively add those names to a new, sorted list.

[Junilu Lacar]

It's kind of hard to read your code and figure out what you're trying to do with sorting.  Can you describe in plain English this recursive sorting algorithm you are trying to implement? Does it have a name?

[Campbell Ritchie]

Please read this, which will tell you there are problems with sorting linked lists.

[Rachel Green]

It looks like I wasn't very clear in what I'm trying to do, so I'm very sorry about that. Basically, I was given the code you see above and I have been tasked with creating a method that takes the linked list and sorts it into another list, using recursion. I need to create a method that goes through the existing linked list and copies the elements into a new linked list, in alphabetical order. I hope that helps clear up the confusion!

[Knute Snortum]

You have to use recursion?  Or was that just a suggestion?  Either way, it would be best to write out an algorithm that will loop through the unsorted list and create a new sorted list.

Algorithms (in case you don't know) are step by step instructions that given a certain input will always produce the correct output.  You input is the unsorted list.  Your output is the sorted list.  Each step should be simple, unambiguous, and not use any Java terms.

[Rachel Green]

Knute Snortum wrote:You have to use recursion?  Or was that just a suggestion?  Either way, it would be best to write out an algorithm that will loop through the unsorted list and create a new sorted list.

Algorithms (in case you don't know) are step by step instructions that given a certain input will always produce the correct output.  You input is the unsorted list.  Your output is the sorted list.  Each step should be simple, unambiguous, and not use any Java terms.

This is exactly what I need. I do have to use recursion and this is very new to me. I just can't figure out how to get started.

[Stephan van Hulst]

A simple way to do this is to interpret the sort() method as "sort all the nodes after this one, and then insert this one at the right location in the following nodes". It's essentially an insertion sort, but with a linked list.

[Junilu Lacar]

A recursive method/function has the following basic elements:

1. The base case, also known as the degenerate case, of which there should be at least one. There could be more than one. A degenerate case defines the condition(s) under which the recursion stops.

2. The recursive cases or the conditions under which recursion occurs.

You need to identify all possible cases/scenarios that your method must operate under and determine whether each scenario is a degenerate case or a recursive case. Then you need to structure your logic so that each one is handled appropriately.  

Your implementation doesn't clearly indicate to me that you understand whether or not you've covered all the possible cases. If you do, then you're still not understanding what to do in each particular case.

Hint: From what I can tell, your code does cover all cases, both degenerate and recursive. You're not doing the right thing in the degenerate cases though.

We'll try to help you think this through. List out the degenerate and recursive cases and match each case to the line number(s) in your implementation. Then, explain in plain English what you're doing to handle each case. Don't explain the code you wrote. In fact, ignore the code you wrote because it's incorrect. Explain the algorithm at a high level. What should you do in each case. Try to explain it in terms of other list operations.