Inserting into sorted linked list - Java

Question

I need to maintain a sorted data structure from which items can be deleted and added. For that I decided to choose a linked list. Each data item contains a letter and some numbers such as these: A1480, A1488, B1297, C3119 These need to be maintained in order. I have written code for it which first finds the position into the already sorted linked list where the new item needs to be added and then adds the item to its correct position, therefore maintaining the sorted linked list. It works but some items are misplaced and I am not sure how to fix my code. I do know that there is something wrong with the last loop but i am not sure what it is.

 public static void main(String[] args) {
 list = new LinkedList<String>();
 add("C3138");
 add("C3119");
 add("A1488");
 add("A1480");
 add("A1517");
 add("B1297");
 add("C2597");
 add("B1356");
 add("C9000");
 add("C3517");
 add("C3729");
 add("C1729");
 add("B1729");
}
 public static void add(String value) {
 // Integer value form the string passed into the method
 int valueInt = getInt(value);
 // If linked list is empty, add value and return from method
 if (list.size() == 0) {
 list.add(value);
 return;
 }
 // Compare this item to be added to the first item
 int firstNode = getInt(list.get(0));
 if (list.get(0).charAt(0) > value.charAt(0) 
 || (list.get(0).charAt(0) == value.charAt(0) && firstNode > valueInt)){
 list.add(0, value);
 return;
 }
 // Compare this item to the last item
 int lastNode = getInt(list.get(list.size() - 1));
 if (list.get(list.size() - 1).charAt(0) < value.charAt(0) || 
 (list.get(list.size() - 1).charAt(0) == value.charAt(0) && lastNode < valueInt)) {
 list.add(list.size(), value);
 return;
 }
 // add the inbetween items
 int i = 1;
 int tempInt = getInt(list.get(i));
 while ((list.get(i).charAt(0) < value.charAt(0)
 || ((list.get(i).charAt(0) == value.charAt(0)) && (valueInt < tempInt)) && i < list.size())) {
 tempInt = getInt(list.get(i));
 i++;
 }
 list.add(i, value);
} 
 public static int getInt(String item) {
 return Integer.parseInt(item.replaceAll("\\D", ""));
}

This code below gives me output of:

[A1480, A1517, A1488, B1729, B1297, B1356, C1729, C3729, C3517, C2597, C3119, C3138, C9000]

and as you can see that some values in between start and finish are misplaced but start and end values are correct. Please help

• user007: Try this :: (list.get(i).charAt(0) < value.charAt(0) || ((list.get(i).charAt(0) == value.charAt(0)) && (valueInt > tempInt)) && i < list.size()) I got a bit confused earlier.. :P Just changed the sign of your comparison valueInt > tempInt
• celticminstrel: Using .get() on a LinkedList... that's going to be slow if the list gets big...

Answer 1

Try doing this :: Change your last while condition to this::

(list.get(i).charAt(0) < value.charAt(0) || ((list.get(i).charAt(0) == value.charAt(0)) && (valueInt > tempInt)) && i < list.size())

What you are currently doing is that you are incrementing your i unless you hit a value of tempInt which is smaller than varInt, which is why A1517 gets inserted before A1488. You shall increment your i until the value of tempInt is smaller than `varInt so that you reach the largest position the current element could achieve. I hope I could make it clear.

The working code Ideone link :: http://ideone.com/ZafWEO

Further, it would be better to check the value to i before accessing the linkedlist items. So, the condition shall look like this ::

(i < list.size() && (list.get(i).charAt(0) < value.charAt(0) || ((list.get(i).charAt(0) == value.charAt(0)) && (valueInt > tempInt)))

Answer 2

Take a look at Why is there no SortedList in Java?

If your values are unique, you can just use TreeSet. Generally, if you want a sorted collection, you probably don't want to start with LinkedList.

• Rosie: I have never used a treeSet before but from what I have researched, it implements Set interface, so it can't have more than one same element but my program can have copies. And also this problem is a subproblem of what I am doing. I need to sort Objects according to different attributes
• pvg: It's hard to tell exactly what your needs are from the information provided try one of the solutions in the other SO question. The easiest thing is probably to use an ArrayList and simply sort it when you need it to be sorted after you've added data. Sorting a nearly-sorted list is extremely fast. You can also implement the method you're trying to implement with Collections.binarySearch which will give you an insertion index if it does not find the element. But again, chances are you can get away with simply sorting as needed.

Answer 3

Why don't you use Comparable?

Scroll to bottom to see the class implemented Comparable

This is answer to your question:

private static LinkedList<SuperRosie> list;
public static void main(String[] args) {
 // TODO Auto-generated method stub
 list = new LinkedList<SuperRosie>();
 add("C3138");
 add("C3119");
 add("A1488");
 add("A1480");
 add("A1517");
 add("B1297");
 add("C2597");
 add("B1356");
 add("C9000");
 add("C3517");
 add("C3729");
 add("C1729");
 add("B1729");
 for (int i = 0; i < list.size(); i++)
 System.out.println(list.get(i).getValue());
}
private static void add(String value) {
 SuperRosie myNewRs = new SuperRosie(value);
 int listSize = list.size();
 // If linked list is empty, add value and return from method
 if (listSize == 0) {
 list.add(myNewRs);
 return;
 }
 // Compare this item to be added to the first item
 SuperRosie element = list.getFirst();
 if (myNewRs.compareTo(element) <= 0) {
 list.addFirst(myNewRs);
 return;
 }else{
 if(listSize == 1){
 list.addLast(myNewRs);
 return;
 }
 }
 // Compare this item to the last item
 element = list.getLast();
 if (myNewRs.compareTo(element) >= 0) {
 list.addLast(myNewRs);
 return;
 }else{
 if(listSize == 1){
 list.addFirst(myNewRs);
 return;
 }
 }
 // add the inbetween items
 int compare = 0;
 for (int i = 1; i < listSize; i++) {
 element = list.get(i);
 compare = myNewRs.compareTo(element);
 if (compare <= 0) {
 list.add(i, myNewRs);
 break;
 }
 }
}

Example to Sort comparable Linked List:

public class Main {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 LinkedList<SuperRosie> list = new LinkedList<SuperRosie>();
 list.add(new SuperRosie("C3138"));
 list.add(new SuperRosie("C3119"));
 list.add(new SuperRosie("A1488"));
 list.add(new SuperRosie("A1480"));
 list.add(new SuperRosie("A1517"));
 list.add(new SuperRosie("B1297"));
 list.add(new SuperRosie("C2597"));
 list.add(new SuperRosie("B1356"));
 list.add(new SuperRosie("C9000"));
 list.add(new SuperRosie("C3517"));
 list.add(new SuperRosie("C3729"));
 list.add(new SuperRosie("C1729"));
 list.add(new SuperRosie("B1729"));
 Collections.sort(list);
 for(SuperRosie rs : list)
 System.out.println(rs.getValue());
 }
}

And SuperRosie.java class implements from Comparable

public class SuperRosie implements Comparable<SuperRosie> {
 private String value;
 public SuperRosie(String value) {
 this.value = value;
 }
 public String getValue() {
 return value;
 }
 @Override
 public int compareTo(SuperRosie arg0) {
 int compareFirst = this.value.charAt(0) - arg0.value.charAt(0);
 return compareFirst == 0 ? (Integer.parseInt(this.value.replaceAll(
 "\\D", "")) - Integer
 .parseInt(arg0.value.replaceAll("\\D", ""))) : compareFirst;
 }
 public static Comparator<SuperRosie> FruitNameComparator = new Comparator<SuperRosie>() {
 public int compare(SuperRosie rosie1, SuperRosie rosie2) {
 String rosieValue1 = rosie1.value.toUpperCase();
 String rosieValue2 = rosie2.value.toUpperCase();
 // ascending order
 return rosieValue1.compareTo(rosieValue2);
 // descending order
 //return rosieValue2.compareTo(rosieValue1);
 }
 };
}

• M. Shaw: Sorted insertion should be much faster than appending and then sorting in large data sets.

Answer 4

According to the performance problems, I suggest another performance solution.

private static LinkedList<String> list;
public static void main(String[] args) {
 list = new LinkedList<>();
 add("C3138");
 add("C3119");
 add("A1488");
 add("A1480");
 add("A1517");
 add("B1297");
 add("C2597");
 add("B1356");
 add("C9000");
 add("C3517");
 add("C3729");
 add("C1729");
 add("B1729");
 for (int i = 0; i < list.size(); i++)
 System.out.println(list.get(i));
}
private static void add(String value){
 // don't check empty array, check to add in the first, last element.
 // Each case, it works but when array has more than 1 element, 
 // so the above check are useless, run will cost memory, steps,....
 // So don't, please do just the following
 int insertIndex = 0;
 for(String element : list){
 if(compare(value, element) <= 0){ // or whatever compare way you want
 break;
 }else{
 insertIndex+=1;
 }
 }
 list.add(insertIndex, value);
}
private static int compare(String value1, String value2){
 int compareFirst = value1.charAt(0) - value2.charAt(0);
 return compareFirst == 0 ? (Integer.parseInt(value1.replaceAll(
 "\\D", "")) - Integer
 .parseInt(value2.replaceAll("\\D", ""))) : compareFirst;
}