progy_rock progy_rock - 2 months ago 5
Java Question

Why can't I sort a user defined LinkedList with this java code?

I created a program in JAVA to add elements to a

LinkedList
and sort the elements while adding them. The swap technique I'm using in case of sorting is similar to that used while adding a node to the beginning of the LinkedList. The technique works in the latter case but fails to run in the former. I don't understand why this is not working. Below is my code for your reference.

//Node class
class Node{
int d; Node link;
Node(int d){
this.d = d;
link = null;
}
}//Node

//LinkedList class
class LL{
Node start;
LL(){
start = null;
}

//method to add and sort the nodes
//in ascending order of the values of 'd' of the nodes
void insert(Node nd){
if(start==null){
start = nd;
}
else{
Node temp = start;
while(temp!=null){
if(nd.d<=temp.d){
Node t2 = temp;
temp = nd;
nd.link = t2;
break;
}
temp = temp.link;
}
}
}//insert

//method to display nodes of the LinkedList
void display(){
Node temp = start;
do{
System.out.print(temp.d + " ");
temp = temp.link;
}while(temp!=null);
}//display
}//LL

//Main class
class LL_Test{
public static void main(String[] args){
LL myLL = new LL();
myLL.insert(new Node(5));
myLL.insert(new Node(2));
myLL.insert(new Node(7));
myLL.insert(new Node(6));
myLL.insert(new Node(1));
myLL.display();
}//main
}//LL_Test


Expected output:
1 2 5 6 7


Obtained output:
5

Answer

You never actually add a element except the first to the list. (temp = nd; does not set the link of the previous node to nd). You need to keep track of the previous node and add the new one after the element before the first one larger than the one you want to

void insert(Node nd) {
    Node temp = start;
    Node previous = null;

    while (temp != null && temp.d < nd.d) {
        previous = temp;
        temp = temp.link;
    }

    // insert node
    if (previous == null) {
        // insert at start
        nd.link = start;
        start = nd;
    } else {
        // insert somewhere in the middle
        nd.link = temp;
        previous.link = nd;
    }
}//insert