Sorting a Double-Link-List

[whoadiz]

hey guys.. basically i'm writing a program that will let the user enter an int and the program will insert that that value in to a double-link-list(dll) along with calculating the sqr root value of it in that same node and it's inserted to the node by increasing int value then displaying the data.

I got most of it except the insert method that I made is acting odd and I can't figure out why it's doing that. Basically it will let me insert the first int to the dll, but if I enter a value that's GREATER than it there is an error.

Please enter an int: 3
 [ 3 ] 1.73
Please enter an int: 8
Exception in thread "main" java.lang.NullPointerException
	at Project3.Dll.insert(Dll.java:56)
	at Project3.dllDrive.main(dllDrive.java:8)

However, when I enter a second value that's less than my first, the program runs. Except it keeps the first value at the end of the dll and won't sort.

Please enter an int: 5
 [ 5 ] 2.24
Please enter an int: 2
 [ 2 ] 1.41 [ 5 ] 2.24
Please enter an int: 9
 [ 2 ] 1.41 [ 9 ] 3.00 [ 5 ] 2.24
Please enter an int: 4
 [ 2 ] 1.41 [ 9 ] 3.00 [ 4 ] 2.00 [ 5 ] 2.24
Please enter an int: 1
 [ 1 ] 1.00 [ 2 ] 1.41 [ 9 ] 3.00 [ 4 ] 2.00 [ 5 ] 2.24

Here is my code.. any help/insight as to why my program is doing this is greatly appreciated! :)

class Dll{
      private Node front;
   
       public Dll(){
         front = null;
      }
	int length = 0;

	public boolean isEmpty(){
		return front == null;
	}
   

       public void print(){
         DecimalFormat twoDec = new DecimalFormat("###.00");
         Node p = front;

         while(p != null){
            System.out.print(" [ " + p.getNumber() + " ] " + twoDec.format(p.getRoot()));
            p = p.getRight();
         }
		System.out.println("");
      }
   

       public int read(){
         Scanner scan = new Scanner(System.in);
         int num = 0;
         System.out.print("Please enter an int: ");
         num = scan.nextInt();
         return num;
      }
   
   /*
   Creates a node that contains n and its sqr root, inserts it in to the dll
   */
	public void insert(int n){
	Node temp = new Node(n);
      		// insert in front if empty
	if (isEmpty()){
		front = temp;
	} 
	else {
		Node p = null;
		Node q = front;
		// insert in order of int
		if (temp.getNumber() < q.getNumber()){
			temp.setRight(q);
			q.setLeft(temp);
			front = temp;
		} else if (temp.getNumber() > q.getNumber()) {
			while (q != null && q.getRight() != null){
				p = q;
				q = q.getRight();
			}
			p.setRight(temp);
			temp.setLeft(p);
			temp.setRight(q);
			q.setLeft(temp);
			}
		}
	}
}

import java.lang.*;

class Node {
	private Node left;
	private int number;
	private double root;
 	private Node right;

  	public Node() {
		left = null;
		number = 0;
		root = 0.0;
		right = null;
  	}

   public Node(int x) {
		left = null;
		number = x;
		root = Math.sqrt(x);
		right = null;
   }

    // primary constructor
	public Node(int x, Node l, Node r) {
		left = l;
		number = x;
		root = Math.sqrt(x);
		right = r;
	}

    // accessor method
	public int getNumber() {
		return number;
	}
	 
	public double getRoot(){
		return root;
	}

	public Node getLeft() {
		return left;
	}
	 
	public Node getRight() {
	 	return right;
	}
		

	// mutator method
	public void setNum(int x){
		number = x;
	}

	public void setLeft(Node leftNode) {
		left = leftNode;
	}
	 
	public void setRight(Node rightNode) {
	 	right = rightNode;
	}
} // end of class Node

public class dllDrive {
	public static void main(String [] args){
		Dll numbers = new Dll();
		int num;
		int i = 0;
		for (i = 0; i < 5; i++){
		num = numbers.read();
		numbers.insert(num);
		numbers.print();
		}
}
}

[sid78669]

OK, I think I might have the answer, in line 52-55:

while (q != null && q.getRight() != null){
				p = q;
				q = q.getRight();
			}

when you do q!=null: if q is null then you cannot acccess q.getRight(), this is a memory violation. instead just trim it down to:

while (q != null){
				p = q;
				q = q.getRight();
			}

Rest of your code seems to be in order. I have done a similar linked list in C++ and DLL have a kind of general design.

Give it a shot and shoot me the output.

[sid78669]

OK, I think I made a mistake in my reply, instead of

while (q != null){
				p = q;
				q = q.getRight();
			}

do

while (q.getRight() != null){
				p = q;
				q = q.getRight();
			}

you need to check if this is the last element :p
My bad!

[whoadiz]

Well... it seems to be doing the exact same thing unfortunately :(

Please enter an int: 4
 [ 4 ] 2.00
Please enter an int: 6
Exception in thread "main" java.lang.NullPointerException
	at Project3.Dll.insert(Dll.java:56)
	at Project3.dllDrive.main(dllDrive.java:8)

Please enter an int: 6
 [ 6 ] 2.45
Please enter an int: 4
 [ 4 ] 2.00 [ 6 ] 2.45
Please enter an int: 5
 [ 4 ] 2.00 [ 5 ] 2.24 [ 6 ] 2.45
Please enter an int: 1
 [ 1 ] 1.00 [ 4 ] 2.00 [ 5 ] 2.24 [ 6 ] 2.45
Please enter an int: 9
 [ 1 ] 1.00 [ 4 ] 2.00 [ 5 ] 2.24 [ 9 ] 3.00 [ 6 ] 2.45

[sid78669]

OK, seems like you are just looping the whole list till you get at the end. And I overlooked it in the first go. try this:

Node p = null;
		Node q = front;
		// insert in order of int
		if (temp.getNumber() < q.getNumber()){
			temp.setRight(q);
			q.setLeft(temp);
			front = temp;
		} else if (temp.getNumber() > q.getNumber()) {
			while (q != null && q.getRight() != null){
				p = q;
				if(p.getNumber() < temp.getNumber()){
					break;
				} else {
				q = q.getRight();
				}
			}
			p.setRight(temp);
			temp.setLeft(p);
			temp.setRight(q);
			q.setLeft(temp);
			}
		}

The problem is occuring when its trying to do p.setRight(). this is possible if p is a null pointer when the setRight is done.

[whoadiz]

Ok when I did what you suggested, it basically just doesn't add any int that has a greater value than my initial int. Which isn't exactly what I wanted to do..
I figured out that the problem was because i tried to walk down a single node when there is only 1 value so I made this adjustment

public void insert(int n){
	Node temp = new Node(n);
      		// insert in front if empty
	if (isEmpty()){
		front = temp;
	} 
	else {
		Node p = null;
		Node q = front;
		// insert in order of int
		if (temp.getNumber() < q.getNumber()){
			temp.setRight(q);
			q.setLeft(temp);
			front = temp;
		} else if (temp.getNumber() > q.getNumber()){
			q.setRight(temp);
			temp.setLeft(q);
			q = temp;
		} else if (temp.getNumber() > q.getNumber()) {
			while (q!= null && q.getRight() != null){
				p = q;
				q = q.getRight();
			}
			p.setRight(temp);
			temp.setLeft(p);
			temp.setRight(q);
			q.setLeft(temp);
			}
		}
	}

However, a new problem comes up now where it will reset to 2 nodes every time i insert an int value that is greater than my original int but it will let me insert nodes with values less than my original.

Please enter an int: 4
 [ 4 ] 2.00
Please enter an int: 7
 [ 4 ] 2.00 [ 7 ] 2.65
Please enter an int: 6
 [ 4 ] 2.00 [ 6 ] 2.45
Please enter an int: 8
 [ 4 ] 2.00 [ 8 ] 2.83
Please enter an int: 2
 [ 2 ] 1.41 [ 4 ] 2.00 [ 8 ] 2.83

[sid78669]

well, try to remove the two elseif into just one as they are both the same thing. instead, try to do something like

else if (temp.getNumber() > q.getNumber()){
	if(q.getRight().getNumber() < temp.getNumber()){		
	q.setRight(temp);
			temp.setLeft(q);
			q = temp;
		} else {
while (q!= null && q.getRight() != null){
				p = q;
				q = q.getRight();
			}
			p.setRight(temp);
			temp.setLeft(p);
			temp.setRight(q);
			q.setLeft(temp);
			}
		}

What you want to do is, if temp'number is bigger than q, check if q.right has a smaller number than temp. if it does, then put temp between q and q.right. otherwise check to see if q.next.number if bigger than temp or not and so on.