# List Sorting method.

• 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).