Results 1 to 4 of 4
  1. #1
    nweid1 is offline Member
    Join Date
    Dec 2011
    Posts
    14
    Rep Power
    0

    Default 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:

    Java 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:

    Java 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;
       }  
    }
    Last edited by nweid1; 03-21-2012 at 08:07 AM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,883
    Rep Power
    25

    Default 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)?
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,883
    Rep Power
    25

    Default Re: Sorting a Linked List

    Cross posted at Sorting a Linked List
    If you don't understand my response, don't ignore it, ask a question.

  4. #4
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,458
    Rep Power
    20

    Default Re: Sorting a Linked List

    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

Similar Threads

  1. Linked List, Array List time complexity
    By Rick99771977 in forum New To Java
    Replies: 4
    Last Post: 08-18-2011, 06:37 AM
  2. Replies: 4
    Last Post: 02-21-2011, 10:34 AM
  3. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-27-2010, 12:15 AM
  4. Need help with sorting a linked list
    By SteroidalPsycho in forum New To Java
    Replies: 0
    Last Post: 05-04-2010, 02:15 AM
  5. Sorting a linked list
    By Hayzam in forum New To Java
    Replies: 4
    Last Post: 01-18-2009, 01:07 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •