Order a linked list alphabetically by name

Question

I am having an issue organizing a linked list alphabetically. I am reading the names in from a text file and storing them into a linked list. The problem I am having is how to sort them alphabetically. If anybody could point me in the right direction that would be amazing. The idea is to get the value of the first 3 letters in each name and compare them to the first 3 in the next name. But where would I compare the letters together?

Here is the LinkedListNode class:

public class LinkedListNode
{

    private String data;
    private LinkedListNode next;


    public LinkedListNode(String data)
    {
        this.data = data;
        this.next = null;
    }

    public String getData()
    {
        return data;
    }

    public LinkedListNode getNext()
    {
        return next;
    }

    public void setNext(LinkedListNode n)
    {
        next = n;
    }
}

Here is the LinkedList file with the main method:

import java.io.*;
import java.util.Scanner;

public class LinkedList {

    public LinkedListNode head;
    String fname;

    public static void main(String[] args) throws FileNotFoundException{
            Scanner scan = new Scanner(new File("Names.txt"));
            LinkedList l = new LinkedList();    
            int i = 1;
            while(scan.hasNext()) {
                String s = scan.nextLine();
                l.insertBack(s);
                i++;
            }
            System.out.print(l.showList());
        }


    public LinkedList() {
        this.head = null;
    }

    public void insertBack(String data){

        if(head == null){
            head = new LinkedListNode(data);
        }else{
            LinkedListNode newNode = new LinkedListNode(data);
            LinkedListNode current = head;
            while(current.getNext() != null){
                current = current.getNext();
            }
            current.setNext(newNode);
        }
    }

    public String showList(){
        int i = 0, j;
        String retStr = "List nodes:\n";
        LinkedListNode current = head;
        while(current != null){
            i++;
            retStr += "Node " + i + ": " + current.getData() + "\n";
            current = current.getNext();

        }

        return retStr;
    }
}

Answer 1

To do easy comparisons, your nodes should implement Comparable. The base Java libraries tend to rely upon this for easy sorting.

The Comaprable interface will require you to implement compareTo (see below).

public int <LinkedListNode> compareTo(LinkedListNode n){
  //Case insensitively compare the first 3 characters of the two nodes
  String myHead = data.substring(0,3).toLowerCase();
  String comparableHead = n.data.substring(0,3).toLowerCase();

  return (myHead.compareTo(comparableHead));

}

If you use a standard List structure like, ArrayList, the Collections.sort(list) will be able to use this method to order your list.

And here's an insertion sort based "insert" function for your runTime, using this comparable.

public void insert(String data){
    LinkedListNode newNode = new LinkedListNode(data);
    if(head == null){
        head = newNode;
    }else{
        LinkedListNode current = head;
        LinkedListNode prev;

        //This is missing some key edge cases, but it inserts properly in the general case.  You'll have to add to it to handle things like running off the list, or this needing to be inserted before the head.
        while(current.getNext() != null){
            if(current.compareTo(newNode)<0){
              newNode.setNext(current);
              prev.setNext(newNode);
              break;
            }
            prev = current;
            current = current.getNext();

        }

    }
}

Answer 2

Try using Collections.sort(list)

Also, for comparing, you can use compareTo function under Comparable Interface

Answer 3

Some pseudo code for you:

OUTER:
for word in file
    node = head
    while node.next
        if word > node.word
             node.next
        else
             Node temp = new Node(word)
             temp.next = word.next
             node.next = temp
             continue OUTER
    node.next = new Node(word)

This is an as-you-go insertion sort. After every insert the file will be sorted. Or you could use other sorting algorithms after you read all of the data

if it's if word > node.word this part you're having trouble with, the String#compareTo method will be useful