Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By Sierra

Thread: sorting linked list?

  1. #1
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default sorting linked list?

    I need to create my own linked list containing random integers and then sort them using an 'insertion' method, i.e. create a temporary linked list and individually add each integer from the original linked list into that one, sorting them during that process.

    The size is received from the console, and the integer VALUES cannot be larger than the size. So if the size is 100, the list will contain 100 integers will be\ between 1 and 100.

    Java Code:
    import java.util.Random;
    
    class intNode {
        public int value;
        public int next;
        public intNode nextNode;
    
        public intNode(int x) {	
            value = x;
    	next = 0;
        }
    
        public void printNode() {
            System.out.print("(" + value + ", " + next + ") ");
        }
    }
    
    class intList {
    	public intNode first;
    	public int size;
    
    	public intList(int x){
    		first = null;
    		size = x;
            }
    
    	public void createList(){
    		Random rand = new Random();
    		for(int i = size; i > 0; i--){
    			int r = rand.nextInt(size);
    			insertFirst(r);
    		}
    	}
    
    	public boolean isEmpty() {
    		return first == null;
    	}
    
    	public void insertFirst(int x) {
    		intNode node = new intNode(x);
    		node.nextNode = first;
    		first = node;
    		if(first.nextNode != null){
    			first.next = first.nextNode.value;
    		}
    	}
    
    	public void insert(int val, int pos){
    		intNode node = new intNode(val);
    		intNode current = first;
    		for(int i = 0; i < pos; i++){
    			current = current.nextNode;
    		}
    		node.next = current.next;
    		current.next = node.value;
    		node.nextNode = current.nextNode;
    		current.nextNode = node;
    	}
    
    	public int getpos(int x){
    		intNode current = first;
    		int i = 0;
    		while(current.next <= x  && current.nextNode != null){
                current = current.nextNode;
    			i++;
            }
    		return i;
    	}
    
    	public intNode deleteFirst() {
    		intNode temp = first;
    		first = first.nextNode;
    		return temp;
    	}
    
    	public void printList() {
    		intNode current = first;
    		System.out.print("List: ");
    		while(current != null) {
    			current.printNode();
    			current = current.nextNode;
    		}
    		System.out.println("");
    	}
    }
    
    class llmain{
    	private static intList sort(intList a){
    		intList temp = new intList(a.size);
    		if(a.first != null){
    			temp.first = a.first;
    			a.deleteFirst();
    		}
    		while(a.first != null){
    			int x = a.first.value;
    			if(x < temp.first.value){
    				temp.insertFirst(x);
    			}
    			else{
    				int pos = temp.getpos(x);
    				temp.insert(x, pos);
    			}
    			a.deleteFirst();
    		}
    		return temp;
    	}
    	
        public static void main(String[] args) {
    		String in = args[0];
    		String sortType = args[1];
    		System.out.println("Sort " + Integer.parseInt(in) + " values using " + sortType);
    		intList list = new intList(Integer.parseInt(in));
    		list.createList();
    		list.printList();
    		sort(list);
    		list.printList();
        }
    }
    The problem is with my sort method. i.e. after main executes list.printList(), the list is printed to the console, but then it just hangs.

    Any advice is much appreciated.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: sorting linked list?

    Does it really have to be an insertion sort method? There are way more efficient methods to build a sorted list for those numbers ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default Re: sorting linked list?

    This is an assignment in which I have to implement a number of sorting methods, and insertion is one of them.

  4. #4
    Sierra is offline AN21XX
    Join Date
    Mar 2012
    Location
    Munich
    Posts
    297
    Rep Power
    3

    Default Re: sorting linked list?

    I guess
    temp.first = a.first;
    is incorrect... you should NEVER just assign objects from lists to other lists, always create a NEW object. Here you have the same object now unintentionally in two different lists and that is probably causing your error.
    In fact your approach seems a little confus and very error prone to me. Why do you not use ArrayList for your purpose?
    Last edited by Sierra; 05-11-2012 at 02:45 PM.
    cherrychives likes this.
    I like likes!

Similar Threads

  1. Sorting a Linked List
    By nweid1 in forum New To Java
    Replies: 3
    Last Post: 03-21-2012, 02:43 PM
  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

Tags for this Thread

Posting Permissions

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