Java Linked List Sorting

Question

So the app reads from an external file a bunch of strings, each on a separate line.

For example:

and
cake
here

It is not arranged in any particular order. I need to read these letters and put them into linked list and finally sort them.

I need help on doing that:

Here is the current code:

import java.util.*;
import java.io.*;
public class LinkedList
{
  static File dataInpt;
  static Scanner inFile;
  public static void main(String[] args) throws IOException
  {
    dataInpt=new File("C:\\lldata.txt");
    inFile=new Scanner(dataInpt);
    Node first = insertInOrder();
    printList(first);
  }
  public static Node getNode(Object element)
  {
    Node temp=new Node();
    temp.value=element;
    temp.next=null;
    return temp;
  }
  public static void printList(Node head)
  {
    Node ptr; //not pointing anywhere
    for(ptr=head;ptr!=null;ptr=ptr.next)
      System.out.println(ptr.value);
    System.out.println();
  }
  public static Node insertInOrder()
  {
    Node first=getNode(inFile.next());
    Node current=first,previous=null;
    Node last=first;
    int count=0;
    while (inFile.hasNext())
    {
      if (previous!=null
          && ((String)current.value).compareTo((String)previous.value) > 0)
      {
        last.next=previous;
        previous=last;
      }
      if (previous!=null
          && ((String)current.value).compareTo((String)previous.value) < 0)
      {
        current.next=last;
        last=current;
      }
      previous=current;
      current=getNode(inFile.next());
    }
    return last;
  }
}

But that gives an infinite loop with "Cat".

Here is the data file:

Lol
Cake
Gel
Hi
Gee
Age
Rage
Tim
Where
And
Kite
Jam
Nickel
Cat
Ran
Jug
Here

Answer 1

Okay, self-study. Split the reading and inserting. Though old and new code both have 14 lines of code, it makes it more intelligable.

public static Node insertInOrder() {
    Node first = null;
    while (inFile.hasNext()) {
        String value = inFile.next().toString();
        first = insert(first, value);
    }
    return first;
}

/**
 * Insert in a sub-list, yielding a changed sub-list.
 * @param node the sub-list.
 * @param value
 * @return the new sub-list (the head node might have been changed).
 */
private static Node insert(Node node, String value) {
    if (node == null) { // End of list
        return getNode(value);
    }
    int comparison = node.value.compareTo(value);
    if (comparison >= 0) { // Or > 0 for stable sort.
        Node newNode = getNode(value); // Insert in front.
        newNode.next = node;
        return newNode;
    }
    node.next = insert(node.next, value); // Insert in the rest.
    return node;
}

This uses recursion (nested "rerunning"), calling insert inside insert. This works like a loop, or work delegation to a clone, or like a mathematical inductive proof.

---

Iterative alternative

also simplified a bit.

private static void Node insert(Node list, String value) {
    Node node = list;
    Node previous = null;
    for (;;) {
        if (node == null || node.value.compareTo(value) >= 0) {
            Node newNode = getNode(value);
            newNode.next = node;
            if (previous == null)
                list = newNode;
            else
                previous.next = newNode;
            break;
        }
        // Insert in the rest:
        previous = node;
        node = node.next;
    }
    return list;
}

Answer 2

Ok, I don't remember exactly school theory about insertion sort, but here is somehow a mix of what I think it is and your code: import java.io.File; import java.io.IOException; import java.util.Scanner;

public class LinkedList {
    public static class Node {
        public String value;
        public Node next;
    }

    static File dataInpt;
    static Scanner inFile;

    public static void main(String[] args) throws IOException {
        inFile = new Scanner("Lol\r\n" + "Cake\r\n" + "Gel\r\n" + "Hi\r\n" + "Gee\r\n" + "Age\r\n" + "Rage\r\n" + "Tim\r\n" + "Where\r\n"
                + "And\r\n" + "Kite\r\n" + "Jam\r\n" + "Nickel\r\n" + "Cat\r\n" + "Ran\r\n" + "Jug\r\n" + "Here");
        Node first = insertInOrder();
        printList(first);
    }

    public static Node getNode(String element) {
        Node temp = new Node();
        temp.value = element;
        temp.next = null;
        return temp;
    }

    public static void printList(Node head) {
        Node ptr; // not pointing anywhere
        for (ptr = head; ptr != null; ptr = ptr.next) {
            System.out.println(ptr.value);
        }
        System.out.println();
    }

    public static Node insertInOrder() {
        Node current = getNode(inFile.next());
        Node first = current, last = current;
        while (inFile.hasNext()) {
            if (first != null && current.value.compareTo(first.value) < 0) {
                current.next = first;
                first = current;
            } else if (last != null && current.value.compareTo(last.value) > 0) {
                last.next = current;
                last = current;
            } else {
                Node temp = first;
                while (current.value.compareTo(temp.value) < 0) {
                    temp = temp.next;
                }
                current.next = temp.next;
                temp.next = current;
            }
            current = getNode(inFile.next());
        }
        return first;
    }
}

And it works like a charm. Of course this far from optimal, both in terms of performance and code reuse.

Answer 3

In relatively simple code like that in your question, a good exercise to understanding it is to work through a few interations of your loop, inspecting the values of all your local variable to see the effect of your code. You can even do it by hand if the code is simple. If it is too difficult to do by hand, your code is probably too complicated. If you can't follow it, how can you know if you are doing what you intend. For example, I could be wrong, but this appears the be the state at the top of each iteration of the loop. It starts falling apart on the third time through, and by the fourth you have a severe problem as your list becomes disjointed.

1)last = first = Lol, current = previous = null
  Lol->null
2)last = first = previous = Lol, current = Cake
  Lol->Lol
3)first = Lol, last = Cake, previous = Cake, current = Gel 
  Cake->Lol->Lol 
4)first = Lol, last = Cake, previous = Cake, current = Hi
  Cake->Gel, Lol->Lol

Answer 4

Quite honestly, if I were running the course, I would consider the correct answer to be:

List<String> list = new LinkedList<String>();
// read in lines and: list.add(word);
Collections.sort(list);

Answer 5

public static Node insertInOrder()
{
    Node first=getNode(inFile.next());
    Node current=first,previous=null;
    Node last=first;
    int count=0;
    while (inFile.hasNext())
    {
        if (previous!=null
            && ((String)current.value).compareTo((String)previous.value) > 0)
        {
            last.next=previous;
            previous=last;
        }
        if (previous!=null
            && ((String)current.value).compareTo((String)previous.value) < 0)
        {
            current.next=last;
            last=current;
        }
        previous=current;
        current=getNode(inFile.next());
    }
    return last;
}

First of all, you never do anything with the last line read from the file, so that's not ever inserted. You have to read the line and create the new Node before relinking next pointers.

Then, if last and previous refer to the same Node and the data of current is larger than that of previous,

if (previous!=null
    && ((String)current.value).compareTo((String)previous.value) > 0)
{
    last.next=previous;
    previous=last;
}

You set last.next = last, breaking the list. From the code (in particular the absence of a sort(Node) function), it seems as though you want to sort the list as it is created. But you only ever compare each new Node with one other, so that doesn't maintain order.

For each new node, you have to find the node after which it has to be inserted, scanning from the front of the list, and modify current.next and the predecessor's next.