# Sorting a Linked List

Printable View

• 03-21-2012, 08:03 AM
nweid1
Sorting a Linked List
I had to make a Linked List program for my programming class. It works and every time a number is inserted it is put at the beginning of the list. Now my teacher wants us to take our Linked List program and sort the numbers in ascending order. I am totally lost on how to do this. Can anyone point me in the right direction?
Here is my code for the list:

Code:

```public class SortedList {         private DoubleNode head = null;         private int listLength;         public static void main(String[] args) {                 SortedList list = new SortedList();                 list.insert(6);                 list.insert(7);                                 System.out.println(list.toString());                         }                 public void insert(double value) {                 head = new DoubleNode(value, head);                 listLength++;                         }                 public String toString() {                 String answer = "[ ";                 for (DoubleNode current = head; current != null; current = current                                 .getLink()) {                         answer += current.getData() + " ";                 }                 answer += "]";                 return answer;         }                 public int find(double value) {                 if (listLength == 0)                         return -1;                                 int pos = 1;                 for (DoubleNode current = head; current != null; current = current.getLink()) {                         if (current.getData() == value)                                 return pos;                         pos++;                 }                 return -1;         }         public int size() {                 return listLength;         }         public boolean removeAt(int index) {                 if (index < 1 || index > listLength)                         return false;                                 if (index == 1) {                         if (head != null) {                                 head = head.getLink();                                 listLength--;                         }                         return true;                 }                                 DoubleNode current = head;                 for (int i = 1; i < (index - 1); i++) {                         if (current.getLink() == null)                                 return false;                         current = current.getLink();                 }                 current.setLink(current.getLink().getLink());                 listLength--;                 return true;         }         }```
and here is my code for the node given by my teacher:

Code:

```// File: DoubleNode.java based on the DoubleNode class by Michael Main /************************************************************************** * DoubleNode provides a node for a linked list with double data in each node. * * @note *  Lists of nodes can be made of any length, limited only by the amount of *  free memory in the heap. * * @author Michael Main *  shortened by Beth Katz and Stephanie Elzer to be only the basics * * @version *  February 2007 ***************************************************************************/ public class DoubleNode {   // Invariant of the DoubleNode class:   //  1. The node's double data is in the instance variable data.   //  2. For the final node of a list, the link part is null.   //      Otherwise, the link part is a reference to the next node of the list.   private double data;   private DoubleNode link;      /**   * Initialize a node with a specified initial data and link to the next   * node. Note that the initialLink may be the null reference, which   * indicates that the new node has nothing after it.   * @param initialData   *  the initial data of this new node   * @param initialLink   *  a reference to the node after this new node--this reference may be   *  null to indicate that there is no node after this new node.   * @postcondition   *  This node contains the specified data and link to the next node.   **/    public DoubleNode(double initialData, DoubleNode initialLink)   {       data = initialData;       link = initialLink;   }       /**   * Accessor method to get the data from this node.    * @param - none   * @return   *  the data from this node   **/   public double getData( )    {       return data;   }       /**   * Accessor method to get a reference to the next node after this node.   * @param - none   * @return   *  a reference to the node after this node (or the null reference if   *  there is nothing after this node)   **/   public DoubleNode getLink( )   {       return link;                                                }     /**   * Modification method to set the data in this node.    * @param newData   *  the new data to place in this node   * @postcondition   *  The data of this node has been set to newData.   **/   public void setData(double newData)    {       data = newData;   }                                                                    /**   * Modification method to set the link to the next node after this node.   * @param newLink   *  a reference to the node that should appear after this node in the   *  linked list (or the null reference if there is no node after this node)   * @postcondition   *  The link to the node after this node has been set to newLink. Any other   *  node (that used to be in this link) is no longer connected to this node.   **/   public void setLink(DoubleNode newLink)   {                          link = newLink;   }  }```
• 03-21-2012, 01:43 PM
Norm
Re: Sorting a Linked List
Are the numbers to be inserted in sorted order
or do you want to sort an existing list (after is has been created)?
• 03-21-2012, 02:08 PM
Norm
Re: Sorting a Linked List
Cross posted at Sorting a Linked List
• 03-21-2012, 02:43 PM
DarrylBurke
Re: Sorting a Linked List