插入到排序链表- Java

Question

我需要维护一个排序的数据结构，可以从中删除和添加项。为此，我决定选择一个链表。每个数据项包含一个字母和一些数字，例如:A1480, a1488, b1297, c3119这些都需要按顺序维护。我已经为它编写了代码，它首先在已经排序的链表中找到位置，其中需要添加新项目，然后将项目添加到正确的位置，从而维护排序的链表。它的工作，但有些项目是错位的，我不知道如何修复我的代码。我知道最后一个循环有问题，但我不确定是什么问题。

    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", ""));
}

下面的代码输出如下:

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

，你可以看到开始和结束之间的一些值是错位的，但开始和结束值是正确的。请帮忙

Answer 1

试着这样做::将最后一个while条件更改为::

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

你目前正在做的是，你正在增加你的i，除非你达到tempInt的值小于varInt，这就是为什么A1517被插入到A1488之前。你应该增加你的i，直到tempInt的值小于' varInt '，这样你就达到了当前元素所能达到的最大位置。我希望我能说清楚。

工作代码Ideone link:: http://ideone.com/ZafWEO

此外，最好在访问链表项之前检查i的值。那么，条件应该是这样的::

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

Answer 2

看一下为什么Java中没有SortedList ?

如果你的值是唯一的，你可以只使用TreeSet。一般来说，如果你想要一个排序的集合，你可能不想从LinkedList开始。

Answer 3

为什么不使用Comparable呢?

滚动到底部查看实现的类

这就是你问题的答案:

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;
        }
    }
}

比较链表排序示例:

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());
    }
}

和SuperRosie.java类实现自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);
        }
    };
}

Answer 4

根据性能问题，我建议另一种性能解决方案。

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;
}