מיון ברשימה מקושרת

הפעולה

public static BinNode insertToSortedList(BinNode <Integer> p, int num){

     BinNode<Integer> tmp = new BinNode<Integer>(num);

     if (p == null){

           return tmp;

     }

     if (num < p.getValue()){

           while (num < p.getValue() && p.getLeft() != null)

                p = p.getLeft();

           if (p.getLeft() == null){

                p.setLeft(tmp);

                tmp.setRight(p);

           }

           else{

                tmp.setLeft(p);

                tmp.setRight(p.getRight());

                p.getRight().setLeft(tmp);

                p.setRight(tmp);

           }

               

     }

     else{

           while (num > p.getValue() && p.getRight() != null)

                p = p.getRight();

           if (p.getRight() == null){

                p.setRight(tmp);

                tmp.setLeft(p);

           }

           else{

                tmp.setRight(p);

                tmp.setLeft(p.getLeft());

                p.getLeft().setRight(tmp);

                p.setLeft(tmp);

           }   

     }

     return p; 

}

 

התוכנית הראשית

 

 

int x;

BinNode <Integer> lst = null;

       

for (int i=0;i<20;i++){

    x = (int)(Math.random()*150)+3;

    lst = insertToSortedList(lst, x);

}