Results 1 to 2 of 2
  1. #1
    bit_bit is offline Member
    Join Date
    Feb 2010
    Location
    Italy
    Posts
    4
    Rep Power
    0

    Default 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 :)

    Java 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

  2. #2
    bit_bit is offline Member
    Join Date
    Feb 2010
    Location
    Italy
    Posts
    4
    Rep Power
    0

    Default

    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.

Similar Threads

  1. how do i reverse this method for sorting?Again!
    By PureAwesomeness in forum New To Java
    Replies: 2
    Last Post: 03-09-2009, 01:51 AM
  2. [SOLVED] how do i reverse this method for sorting?
    By PureAwesomeness in forum New To Java
    Replies: 3
    Last Post: 03-08-2009, 10:37 PM
  3. Replies: 5
    Last Post: 02-07-2009, 08:48 AM
  4. Sorting a linked list
    By Hayzam in forum New To Java
    Replies: 4
    Last Post: 01-18-2009, 01:07 AM
  5. Converting array to list and sorting it
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 11:36 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •