1. Member Join Date
Apr 2012
Posts
25
Rep Power
0 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;
String sortType = args;
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.  Reply With Quote

2. 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  Reply With Quote

3. Member Join Date
Apr 2012
Posts
25
Rep Power
0 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.  Reply With Quote

4. AN21XX Join Date
Mar 2012
Location
Munich
Posts
297
Rep Power
8 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 01:45 PM.  Reply With Quote

Tags for this Thread

linked list, sorting  Posting Permissions

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