# List Sorting method.

Printable View

• 02-23-2010, 05:51 PM
bit_bit
List Sorting method.
hi there.
i've started doing a java library with all the data structures necessary for future software i have in plan to do. i have some trouble with sorting a Linked List and i can't seem to understand where is the problem.

here's the code i've written. a big thanks if you can help, if not, thank you anyway :)

Code:

```public class LinkedList<U extends Comparable<U>> {     private Node head;          // this node points to the first element of the list.     private Node tail;          // this node points to the last element of the list.     /**     * The constructor of a linked list.     *     * @param element the first element of the list.     */     public LinkedList(U element){         head = new Node(element);         tail = head;     }// end of constructor.     /**     * The constructor of an empty linked list.     */     public LinkedList(){         head = null;         tail = null;     }// end of constructor.     /**     * A method that adds an element in the list, at the given position.     * If the given position is bigger than the number of elements of the list then the method simply adds the element in the end of the list.     *     * @param toAdd the element that we want to add.     * @param position the position in wich the elements must be added.     */     public void add(U toAdd, int position){         int l = length();         if(position >= l) add(toAdd);         else{             Node t = head;             for(int i = 0; i < position - 1; i++)                 t = t.next;             t.next = new Node(toAdd, t.next);         }// end of else.     }// end of method.     /**     * A method that creates a copy of the list, sorts it and returns it.     *     * @return a sorted copy of the original list.     */     public void sort(){         LinkedList<U> l1 = this;         LinkedList<U> l2 = l1.split();         if(l1.length() > 1) l1.sort();         if(l2.length() > 1) l2.sort();         Node t1 = l1.head;         Node t2 = l2.head;         int l = l1.length() + l2.length();         for(int i = 0; i < l; i++){             if(t1 != null && t2 != null){                 if(t1.elem.compareTo(t2.elem) <= 0){                     t1 = t1.next;                 }// end of if.                 else{                     l1.add(t2.elem, i);                     t2 = t2.next;                 }// end of else.             }// end of if.             else if(t1 != null){                 t1 = t1.next;             }// end of else-if.             else{                 l1.add(t2.elem, i);                 t2 = t2.next;             }// end of else.         }// end of cicle.     }// end of method.     /**     * A method that splits the linked list in two and returns the other list.     *     * @return the other half of the linked list.     */     private LinkedList<U> split(){         LinkedList<U> ris = new LinkedList();         int l = length();         if(l > 1){             Node n = head;             for(int i = 0; i < (l / 2) - 1; i++, n = n.next);             ris.head = n.next;             ris.tail = tail;             tail = n;             n.next = null;         }// end of if.         return ris;     }// end of method.     /**     * A method that calculates the length of a linked list.     *     * @return the length of the linked list.     */     public int length(){         int ris = 0;         for(Node tmp = head; tmp != null; tmp = tmp.next) ris++;         return ris;     }// end of method. /* other methods are in here, but they are tested and are ok */     /**     * The inner class of the linked list.     * This class creates and manipulates the nodes of the linked list.     */     private class Node{         U elem;         Node next;         /**         * The constructor of the node of the linked list.         *         * @param el the element that the node must contain.         * @param n the pointer to the next node.         */         Node(U el, Node n){             elem = el;             next = n;         }// end of constructor.         /**         * The constructor of the node of the linked list.         *         * @param el the element that the node must contain.         */         Node(U el){             this(el, null);         }// end of constructor.     }// end of subclass. }// end of class.```
The test was made with Integer objects (the list was made by the numbers 50, 20, 25, 24 and the result of the sort was 50, 24, 25, 20).

thank you in advance.
bit_bit
• 02-24-2010, 12:44 PM
bit_bit
nobody can help? or maybe the way i want to do the sorting is not clear enough? i really need to understand the reason why it does not work. if there's something you do not understand in the code please ask me.