Putting Character Nodes in Alphabetical Order within a Linked List

Question

I have been trying to figure out how to do this for a while now and I just can't figure out what I'm doing wrong. What I need to do is create a linked list using characters, and display the list in alphabetical order.

Main Program:

public static void main(String[] args) {

    String n = null;
    char newChar = ' ';
    KeyboardReader reader = new KeyboardReader();

    Node start = null;
    Node last = null;
    Node temp = null;

            do{
                System.out.print("Enter a letter: ");
                newChar = reader.readChar();

                temp = new Node(newChar);

                if (start == null)
                     start = temp;
                if (last != null){ 
                    last.nodeptr = temp;
                }
                last = temp;

                System.out.print("Linked list: ");
                printList(start);

                System.out.print("Would you like to enter another letter (y/n)? ");
                n = reader.readLine();
                addLine();

            }while(n.compareTo("y") == 0);

            System.out.println("The following will output a linked list created in alphabetical order.");
            addLine();

            start = null;
            last = null;
            temp = null;

            do{
                System.out.print("Enter a letter: ");
                newChar = reader.readChar();

                temp = new Node(newChar);

                if(start == null){
                    start = temp;
                    last = temp;
                }

                //~~ CAUSING ISSUES ~~
                //if(last != null)
                    //last.nodeptr = temp;


                //insert before
                if(temp.letter < start.letter){
                    temp.nodeptr = start;
                    start = temp;   
                }

                //insert at middle or end
                else{
                    if(last.letter < temp.letter){
                        last.nodeptr = temp;
                        temp = last;
                    }
                    if(last.letter > temp.letter){
                        temp.nodeptr = last;
                        last = temp;
                    }
                }

                //For testing purposes
                /*else{
                    if(temp.letter > start.letter){
                        if(start.nodeptr != null){
                            while(temp.letter > start.nodeptr.letter){
                                temp.nodeptr = start;
                                start = temp;
                            }
                        }
                    }
                    else if(temp.letter < last.letter){
                        if(last.nodeptr != null){
                            while(temp.letter < last.nodeptr.letter){
                                last.nodeptr = temp;
                                last = temp;
                            }
                        }
                    }
                }
                */

                System.out.print("Linked list: ");
                printList(start);

                System.out.print("Would you like to enter another letter (y/n)? ");
                n = reader.readLine();
                addLine();

            }while(n.compareTo("y") == 0);
}    

Current Output(as is with commented out stuff):

Enter a letter: m  
Linked list: m  
Would you like to enter another letter (y/n)? y  

Enter a letter: o  
Linked list: mo  
Would you like to enter another letter (y/n)? y  

Enter a letter: n  
Linked list: mon  
Would you like to enter another letter (y/n)? y  

Enter a letter: e   
Linked list: mone  
Would you like to enter another letter (y/n)? y  

Enter a letter: y  
Linked list: money  
Would you like to enter another letter (y/n)? n  

The following will output a linked list created in alphabetical order.  

Enter a letter: m  
Linked list: m  
Would you like to enter another letter (y/n)? y  

Enter a letter: o  
Linked list: mo  
Would you like to enter another letter (y/n)? y  

Enter a letter: n  
Linked list: mn  
Would you like to enter another letter (y/n)? n     

I figured out the first part of the program, which was just to insert as the user input each character. However, now I have to put it in alphabetical order and I think I pinpointed my issue, which I believe is due to the Last node. I commented it out in the program and it runs, however not correctly. If I leave it un-commented, it makes a loop and basically breaks the program.

If someone could help me fix the code up and make it work 100%, it would be greatly appreciated!

Answer 1

There are basically four cases to consider when you're adding a new character to your list:

1. If the list is empty, the new character becomes both the head and the tail of the list.
2. If the new character precedes the node at the head of the list, then it becomes the head of the list and points to the old head of the list.
3. If the new character occurs after the node at the tail of the list, then it becomes the tail of the list and the old tail node points to it.
4. If none of these are true, then the node goes somewhere in the middle of the list.

Cases 1 and 2 look correct as you have them:

if(start == null){
    start = temp;
    last = temp;
}

//insert before
if(temp.letter < start.letter){
    temp.nodeptr = start;
    start = temp;   
}

Case 3 has a slight bug:

if(last.letter < temp.letter){
    last.nodeptr = temp;
    temp = last;
}

Instead of temp = last, I think you want last = temp here, as temp is supposed to take its place as the last node in the list. This is why, when you type "N" after having entered "M" and "O", the "O" has disappeared.

Case 4 is the one you're going to need to do some work on. Because the new node could go anywhere in the list, and the list could have any number of elements, you're not going to be able to do it with just a series of if statements as you've done so far. Instead, you'll need to use a loop to traverse the list and find the appropriate place to insert the new node. Is this enough to get you going?