Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Sorting a Linked List

  1. #1
    Junior Member
    Join Date
    Dec 2011
    Posts
    13
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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:

    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 the code for the node given by my teacher:

    // 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; March 21st, 2012 at 02:08 AM.


  2. #2
    Junior Member
    Join Date
    Dec 2011
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting a Linked List

    What kind of sort needs to be implemented?

  3. #3
    Junior Member
    Join Date
    Dec 2011
    Posts
    13
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting a Linked List

    I have to sort the list in ascending order in the "insert" method as it is inserted. So, if I add 6, then 8, the list should print out "6.0 8.0". If i then added 12, the list should print out "6.0 8.0 12.0".

  4. #4
    Junior Member
    Join Date
    Dec 2011
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting a Linked List

    Okay, well the approach i would recommend is iterate over the list until you find the correct position. Then assign the current nodes reference (what is being pointed at) to the reference of the node being inserted then assign the current nodes reference to the inserted node. Just watch for special cases like empty list, insert tail, and item already exists.

    EDIT: after reading over my post, to clear up what i mean it would look like this

    node1->node2

    newNode->node2

    node1->newNode->node2
    Last edited by fryishone; March 21st, 2012 at 03:01 AM.

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,254
    Thanks
    56
    Thanked 2,372 Times in 2,343 Posts

    Default Re: Sorting a Linked List

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

Similar Threads

  1. linked list
    By javasohard in forum What's Wrong With My Code?
    Replies: 1
    Last Post: October 18th, 2011, 03:22 AM
  2. Linked list Schminked list help with Nodes Please
    By Bially in forum Collections and Generics
    Replies: 1
    Last Post: September 29th, 2011, 04:20 PM
  3. [SOLVED] Linked List Help
    By lieles in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 4th, 2011, 10:32 PM
  4. Sorting a doubly linked list
    By snufkin in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 26th, 2010, 12:01 PM
  5. Help with linked list
    By joecool594 in forum Collections and Generics
    Replies: 3
    Last Post: November 28th, 2010, 12:33 PM