java- sort linked list of strings based on their assigned integer values

If you can afford to waste CPU in repeated calculations of the distance, then you could use the JDK sorting methods with a Comparator implementation which would figure the distance from any 2 strings and compare them. This is the simplest.

If you would prefer calculating only once the distance for each string (presuming this is costly), then you either:

a) construct a new collection of tuples (string and distance), and sort the tuples by the distance (again with a comparator, or by making the tuple class comparable).

b) or you can try to cache the distances in a hashmap of strings-to-distance which the comparator would rely on.

The first option is to create a comparator and then sort the collection. I would do something like:

  public static void main(String... arg) {
        LinkedList<String> someStringList = new LinkedList<>();

        someStringList.add("2");
        someStringList.add("1");

        System.out.println(someStringList);

        Collections.sort(someStringList, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return theNodesDistance(s1).compareTo(theNodesDistance(s2));
            }

        });
        System.out.println(someStringList);

    }
    public static Integer theNodesDistance(String str){
        return Integer.parseInt(str); // here return the distance
    }

Another option is to create a class Node with an id and distance:

public class Node implements Comparable<Node> {

    String id;
    Integer distance;

    public Node(String id) {
        this.id = id;
        this.distance = theNodesDistance(id);
    }

    @Override
    public int compareTo(Node node) {
        return this.distance.compareTo(node.distance);
    }

    public String toString() {
        return id;
    }

    public Integer theNodesDistance(String str){
        return Integer.parseInt(str);
    }
}

Then, sort your list doing:

LinkedList<Node> nodes = new LinkedList<>();

nodes.add(new Node("2"));
nodes.add(new Node("1"));

System.out.println(nodes);

Collections.sort(nodes);
System.out.println(nodes);

Finally, you can use a PriorityQueue which organizes the elements whenever you insert a new node. I mean, you can remove each node in order.

Queue<Node> nodes = new PriorityQueue<>();
nodes.add(new Node("10"));
nodes.add(new Node("3"));
nodes.add(new Node("2"));
nodes.add(new Node("1"));
nodes.add(new Node("4"));

System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());

In this case, the output will be:

1
2
3
4
10

You can use TreeMap.. Following is a normal demonstration -

    TreeMap<Integer, String> tmap = new TreeMap<Integer, String>(); 
/*Adding elements to TreeMap*/
 tmap.put(1, "Data1"); 
tmap.put(23, "Data2"); 
tmap.put(70, "Data3"); 
tmap.put(4, "Data4"); 
tmap.put(2, "Data5"); 
/* Display content using Iterator*/ 
Set set = tmap.entrySet();
 Iterator iterator = set.iterator();
 while(iterator.hasNext()) { 
Map.Entry mentry = (Map.Entry)iterator.next();
 System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
 System.out.println(mentry.getValue()); 
} 

The output ::

key is: 1 & Value is: Data1 
key is: 2 & Value is: Data5 
key is: 4 & Value is: Data4 
key is: 23 & Value is: Data2 
key is: 70 & Value is: Data3

You can use sort algo. like selectionsort, bubblesort... This is insertionsort

double temp;
for(int i = 1;i<yourList.size();i++)
{
temp = thenodedistance(yourlist.get(i));
int j = i;
    while(j>0&&thenodedistance(yourlist.get(j-1))> temp)
    {
        yourlist.add(j,yourlist.remove(j-1);
        j--;
    }
    yourlist.add(j,yourliste.remove(i));
}

this way you can sort your list (did not try the code....)

What about having a Node class?

class Node{
   String str;
   int distance;
   public Node(String str){
       this.str = str;
       this.distance = theNodesDistance(str);
   }
}

Then you can override a Comparator. I suggest you to use a PriorityQueue instead of a LinkedList so your inserts to the ordered list can be more efficient (O(logn)). In this case you dont really need to call a sort or heapify function since the priority queue always keeps the nodes in order.

PriorityQueue que = new PriorityQueue(new Comparator<Node>(){
     public int compare(Node n1, Node n2){
          if(n1.distance < n2. distance) return -1;
          else if(n1.distance > n2.distance) return 1;
          return 0;
     }
});

You can add to the que as follows:

for(each str){
    que.add(new Node(str));
}