How to sort a linked list?

Question

I have tried it for the whole afternoon. I even started to inspect my intelligence. It's easy but I really dont know how to do. please help me, thanks very very much!!! implement linked list using java and sort it in alphabetical

public class SinglyLinkedList {
private static final int DEFAULT_MAXIMUM = 10;
private SLLNode[] listArray;
private int first = 0; // first element of the list in the array.
private int firstFree = 0; // first free location in the array.

public static void main(String[] args) {
    SinglyLinkedList elementList = new SinglyLinkedList();
    elementList.insert("Hydrogen");
    elementList.insert("Boron");
    elementList.insert("Beryllium");
    elementList.insert("Helium");
    elementList.insert("Lithium");
    elementList.insert("Carbons");

    System.out.println(elementList);
}

public SinglyLinkedList() {
    listArray = new SLLNode[DEFAULT_MAXIMUM];
}

public SinglyLinkedList(int size) {
    listArray = new SLLNode[size];
}

public void insert(String data) {
    inserts(data);
}

private void inserts(String data) {
    SLLNode tempNode = new SLLNode(data);
    listArray[firstFree] = tempNode;
    firstFree++;

    order();
}

private void order() {
    int i = 0;
    /*
     * for (i = 0; i < firstFree - 1; i++) { if(listArray[i].getNext()==-1) {
     * if(listArray[i].comparaTo(listArray[firstFree-1])<0)
     * listArray[firstFree-1].setNext(i); else { i++; if (listArray[firstFree -
     * 1].comparaTo(listArray[i]) > 0 && listArray[firstFree -
     * 1].comparaTo(listArray[listArray[i].getNext()]) < 0) {
     * listArray[i].setNext(firstFree - 1); listArray[firstFree -
     * 1].setNext(listArray[i].getNext()); } else listArray[firstFree -
     * 1].setNext(i); }
     * 
     * } else if (listArray[firstFree - 1].comparaTo(listArray[i]) > 0 &&
     * listArray[firstFree - 1].comparaTo(listArray[listArray[i].getNext()]) < 0) {
     * listArray[i].setNext(firstFree - 1); listArray[firstFree -
     * 1].setNext(listArray[i].getNext()); } else listArray[firstFree -
     * 1].setNext(i); }
     */
    for (i = 0; i < firstFree - 1; i++) {
        if (listArray[i].comparaTo(listArray[first]) < 0)
            first = i;
    }
    SLLNode tempNode = new SLLNode(listArray[first].getData());
    tempNode = listArray[first];
    /*
     * System.out.println("lala"); if(firstFree==1) listArray[first].setNext(0);
     * System.out.println("lala");
     */
    int j = 0;
    if(firstFree==1)
        tempNode.setNext(0);
    if(firstFree==2) {
        listArray[0].setNext(0);
        listArray[1].setNext(1);
    }
    while (tempNode.getNext()!=-1) {
        if (listArray[firstFree - 1].comparaTo(tempNode) > 0
                && listArray[firstFree - 1].comparaTo(listArray[tempNode.getNext()]) < 0) {
            listArray[firstFree - 1].setNext(tempNode.getNext() - 1);
            tempNode.setNext(firstFree-1);
        } else {
            tempNode = listArray[tempNode.getNext()];
        }

    }
    System.out.println("lala");
}

public String toString() {
    StringBuilder tempString = new StringBuilder();
    tempString.append("first = " + first + "\n" + "firstFree = " + firstFree + "\n\n");
    for (int i = 0; i < firstFree; i++) {
        if (listArray[i] != null)
            tempString.append(i + ": " + listArray[i].getData() + "\t" + listArray[i].getNext() + "\n");
    }
    return tempString.toString();
}

/*
 * public SLLIterator getIterator() {
 * 
 * }
 */

private static class SLLNode {
    private String data;
    private int next = -1;

    public SLLNode(String data) {
        this.data = data;
    }

    public SLLNode(String data, int next) {
        this.data = data;
        this.next = next;
    }

    public void setData(String data) {
        this.data = data;
    }

    public String getData() {
        return this.data;
    }

    public void setNext(int next) {
        this.next = next;
    }

    public int getNext() {
        return this.next;
    }

    public String toString() {
        return "loading";
    }

    public int comparaTo(SLLNode tempNode) {
        if (data.compareTo(tempNode.getData()) > 0)
            return 1;
        else if (data.compareTo(tempNode.getData()) < 0)
            return -1;
        else
            return 0;
    }
}}

The main problem is the while loop and the nullPointerException I dont know how to determine whether it's the end of the list

Answer 1

You need to break this into small parts:

1. Find the node after which your new node should go (let's call it before)
2. Find the existing node after that - it's before.next -- call it after. There might not be an after, in which case before.next will be null.
3. Make the new node's next point at after, or be null
4. Make before.next point at the new node

It's important that you understand what variables can be null, and what it means when they are:

• firstNode can be null. This means it's an empty list
• A node's next can be null. This means it's the last element in the list.

Your code must deal with both of these.

Take these one at a time. The first one is probably the most difficult, since the others are really simple.

A linked list doesn't store its elements in an array, and doesn't have a maximum size. The only field your LinkedList needs is Node firstNode. To reach the other elements you follow the next links from the first element. So:

 Node findInsertionPoint(String data) {
     Node node = this.firstNode;
     if(node == null) {
         return null;
     }
     Node nextNode = node.getNext();
     while(nextNode != null && nextNode.getData().compareWith(data) <=0) {
          node = nextNode;
          nextNode = node.getNext();
     }
     return node;
 }

This will return:

• null for an empty list (when firstNode is null)
• the Node after which your new node should go -- that is, the desired before in other cases.

findInsertionPoint() is a testable method in its own right, so test it and make sure it works for a number of cases, before moving on. An empty list. A single-element list. New node should go first. New node should go last. New node is in the middle.

Now you just need to create your new node, and call setNext() with the right value, on both the new node and the before node. If there is no before node, you need to instead set this.firstNode to point to the new node.

---

Note that you are not, here, sorting a linked list - you are inserting an element into the right position in an already-sorted list. One way to sort a linked list is to take its elements one-by-one and insert them into a new list in this way. But there are other more efficient ways, which you will probably encounter later in your studies.