Creating a sorted link list out of a normal linked list

Tags: , , ,



As I’ve just started programming a few months back a lot of new information is coming and I’m having trouble catching up.So here I have created what I thought was a sorted linked list.Turns out it is not sorted

public boolean insert(Person person) {
    Node n = new Node(person); 
    Node p = head;

    if(p == null) {
        head = n;
        size++;
        return true;
    } else {

        Node temp = p;
        int comparison;
        while(temp.next != null) {
            comparison = temp.person.name.compareTo(person.name);
            if(comparison == 0){
                return false;
            }
            temp = temp.next;
        }
        temp.next = n;
        size++;
        return true;
    }

}

The method works,it inserts the persons,but they arent sorted like they should be.What part of the code do I need to change/remove in order to make it sort.

Thanks!

Answer

You should insert like this:

static boolean insert(Person person) {
        Node newNode = new Node(person);

        if (head == null) {
            head = newNode;
            size++;
            return true;
        }

        Node current = head;
        Node prev = null;
        int comparison;

        while (current != null) {
            comparison = person.name.compareTo(current.person.name);
            if (comparison == 0) {
                return false;
            } else if (comparison > 0) { /// greater than

                if (current.next == null) { // check if reach tail of the linked list add and break
                    current.next = newNode;
                    break;
                }
            } else { // less then
                if (prev == null) { // check if it should be first then put and break
                    Node oldHead = head;
                    head = newNode;
                    head.next = oldHead;
                    break;
                }
                prev.next = newNode;
                newNode.next = current;
                break;
            }
            prev = current;
            current = current.next;
        }
        size++;
        return true;
    }


Source: stackoverflow