CODEWITHSUNDEEP
javalinked-listnodescompareto
Billy Pilgrim
Billy Pilgrim

Reputation: 343

Having trouble sorting a linked list in java in different ways, depending on user input

I've got a problem here which I've traced to this method. I can, of course, provide more code if necessary. I have a text file, and each line in the file has a different bike in it. Each line is in the format color::year::price. One bike, for instance could be red::2008::150.

I'm planning to store this information in a linked list, and want to be able to order them by color, year, or price. I do not need to be able to sort again later. I just need to insert them in the correct order from the text file. The user enters a 1, 2, or 3 and I create a new linked list like LinkedList foo = new LinkedList(1);, where 1 means that the nodes should be added such that they're in alphabetical order by color. 2 and 3 sort by the other to variables in respective order. Here's how my general implementation works:

LinkedList color = new LinkedList(1);  //Should sort by color
LinkedList year = new  LinkedList(2);  //"" year
LinkedList price = new LinkedList(3);  //"" price

color.add(new Bike("a::1::1"));
year.add(new Bike("a::1::1"));
price.add(new Bike("a::1::1"));

color.add(new Bike("b::2::2"));
year.add(new Bike("b::2::2"));
price.add(new Bike("b::2::2"));

color.add(new Bike("c::3::3"));
year.add(new Bike("c::3::3"));
price.add(new Bike("c::3::3"));

All three of the above linked lists should have the same data stored in them, and it should display in different orders, however all three display the same order and the last element gets duplicated. They all tend to look something like this:

a::1::1
b::2::2
c::3::3
c::3::3

This is clearly wrong. The last line should not be duplicated and each linked list should produce these values in different orders. Below is my add() code, where the problem seems to be. For the record, a LinkedList object simply contains one node with a null value for both its data and next values.

public void add(Object o){

    Node current = list;
    String currentString = "";
    String oString = o.toString().split("::")[sortOrder - 1];

    while(current.getNext() != null){
        current = current.getNext();
        currentString = current.getData().toString().split("::")[sortOrder - 1];
        //I do the 'sortOrder - 1' bit because when the user enters 1 
        //we should sort by the 0th element, 2 means sort by the 1st element, etc

        if(oString.compareTo(currentString) > 0){
            Node n = new Node(o);
            n.setNext(current.getNext());
            current.setNext(n);
            return;
        }
    }

    current.setNext(new Node(o));
}

Upvotes: 1

Views: 414

Answers (2)

Jeff Bowman
Jeff Bowman

Reputation: 95764

Double-check your conditional in the loop. Remember, x.compareTo(y) ?= 0 is exactly the same as x ?= y, and thus oString.compareTo(currentString) > 0 really means oString > currentString.

Let's say you have items 10 -> 20 -> 30 -> null. You're inserting 25. Your compareTo line will first say "if (25 > 10) create node n after this node". Your list will then be "10 -> 25 -> 20 -> 30 -> null". Instead, what you want to do is to insert the item after current only if newItem > next or next == null.

Hopefully this is a school exercise to create a linked list manually; it makes much more sense to store your list once in an ArrayList and use Collections.sort(list, comparator) to sort the list according to user input.

Upvotes: 1

ranjit
ranjit

Reputation: 158

You may also consider using a Comparator to sort the list the way you want , than modifying the sort logic.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Comparator.html

This way you only need to maintain a single list and can sort and display the list elements the way you want

An example for the usage can be found here : http://www.tutorialspoint.com/java/java_using_comparator.htm

Upvotes: 0

Related Questions