Ordering java linked list alphabetically (dictionary-like)

Question

I've been working for hours trying to order a linked list of strings alphabetically (dictionary-like). The given string is lowercase only. For example, input of: "hello my name is albert" will be sorted in the list as: Node 1: albert, Node 2: hello, Node 3: is, etc..

My code so far reads a string like the example above and insert it as nodes - unordered.

I've searched in the web for ways to sort a linked list alphabetically with good performance, and I found Merge Sort can be usefull. I've changed the merge sort to work for string using compareTo() but my code returns nullPointerException error in the following line:

if(firstList._word.compareTo(secondList._word) < 0){

I'm looking for help to fix the following code or another way for sorting a linked list alphabetically (without Collection.sort)

My full code is (after trying to add the merge sort to work with my code):

public class TextList
{
    public WordNode _head;

    public TextList() 
    {
    _head = null;
    }

    public TextList (String text)
    {
        this._head = new WordNode();
        int lastIndex = 0;
        boolean foundSpace = false;
        String newString;
        WordNode prev,next;
        if (text.length() == 0) {
            this._head._word = null;
            this._head._next = null;
        }
        else {
        for (int i=0;i<text.length();i++)
        {
                if (text.charAt(i) == ' ') {
               newString = text.substring(lastIndex,i);
               insertNode(newString);
               // Update indexes
                lastIndex = i;
                // set to true when the string has a space
                foundSpace = true;  
        }
    }
        if (!foundSpace) {
            //If we didnt find any space, set the given word
            _head.setWord(text);
            _head.setNext(null);

        }
        else {
            //Insert last word
            String lastString = text.substring(lastIndex,text.length());
            WordNode lastNode = new WordNode(_head._word,_head._next);
            _head.setNext(new WordNode(lastString,lastNode));

        }

        sortList(_head);

    }
}

      private void insertNode(String word)
      {
      //Create a new node and put the curret node in it
      WordNode newWord = new WordNode(_head._word,_head.getNext());
      //Set the new information in the head
      _head._word = word;
      _head.setNext(newWord);
    }

private WordNode sortList(WordNode start) {
        if (start == null || start._next == null) return start;
        WordNode fast = start;
        WordNode slow = start;
        // get in middle of the list :
        while (fast._next!= null && fast._next._next !=null){
            slow = slow._next; fast = fast._next._next;
        }
        fast = slow._next;
        slow._next=null;
        return mergeSortedList(sortList(start),sortList(fast));
        }

        private WordNode mergeSortedList(WordNode firstList,WordNode secondList){
            WordNode returnNode = new WordNode("",null);
            WordNode trackingPointer = returnNode;
            while(firstList!=null && secondList!=null){
                if(firstList._word.compareTo(secondList._word) < 0){
                    trackingPointer._next = firstList; firstList=firstList._next;
                }
                else {
                    trackingPointer._next = secondList; secondList=secondList._next
                    ;}
                trackingPointer = trackingPointer._next;
            }
            if (firstList!=null) trackingPointer._next = firstList;
            else if (secondList!=null) trackingPointer._next = secondList;
            return returnNode._next;
            }

        public String toString() {
            String result = "";
            while(_head.getNext() != null){
                _head = _head.getNext();
                result += _head._word + ", ";
            }
            return "List: " + result;
}


    public static void main(String[] args) {
        TextList str = new TextList("a b c d e a b");
        System.out.println(str.toString());
    }

}

Answer 1

If you don't wanna to have a huge code who gets every first letter of the word and sort them, do it with Collection.sort()

I don't know what is the proplem on Collection.sort() so use it

Here is a short code, that does exactually this what you want to:

String test = "hello my name is albert";
test = test.replaceAll(" ", "\n");
String[] te = test.split("\n");
List<String> stlist = new ArrayList<String>();
for(String st : te) {
    stlist.add(st);
}
Collections.sort(stlist);

Answer 2

In the past i have made a method to sort strings alphabetically in an array as school HW, so umm here it is:

    private void sortStringsAlphabetically(){
    for (int all = 0; all < names.length; all++) {
        for (int i = all + 1; i < names.length; i++) {
            if (names[all].compareTo(names[i]) > 0) {
                String tmp = names[i];
                names[i] = names[all];
                names[all] = tmp;
            }
        }
    }
}

This piece of code works for Arrays and specifically for an array of names. You can tweak it to work with the list, it is very simple especially if we consider the wide range of methods in the List interface and all it's implementations.

Cheers.

Answer 3

Regarding NPE you said it is probably because you are having an null string in head at first and keep adding this in insert method.

this._head = new WordNode();

Also the adding last element is also not proper. Just reuse the insert method like below

insertNode(text.substring(lastIndex,text.length()));

These are the ones I thought having problem when you are converting string to lined list

You can use the below code to handle the first null

private void insertNode(String word) {
    if (this._head == null) {
        this._head = new WordNode(word, null);
    } else {
        WordNode newWord = new WordNode(_head._word, _head.getNext());
        _head._word = word;
        _head.setNext(newWord);
    }
}