如何对链表重新排序？

Question

我正在尝试做一个关于链表的作业，不幸的是，我不能在网上发布我的代码。但是一般的问题是这样的：

我有一个有机体的链表: list ->斑马->土狼->狮子->草

但我希望这个列表按顺序显示(食物链)：斑马->狮子-> ->斑马->草

另外，我可能会在列表中添加一个生物体，比如

list.add("T-Rex");

所以我想要的结果应该是orderedList -> T-Rex ->狮子->土狼->斑马->草

如何添加有机体，然后以显示层次结构的方式对它们进行排序？我能放下来的有机体数量有限，所以我知道该把它们放在哪里。例如，我知道如果我把霸王龙，它将永远在狮子之上，土狼将总是早于草…以此类推..我一直试图在YouTube和谷歌上寻找教程，但他们大多是按字母顺序对数字或字符串进行排序，我认为这对我的问题没有真正的帮助。

我非常感谢任何帮助，因为这是我第一次处理链表。

Answer 1

您可以使用

add(int index, E element);

它将在此列表中的指定位置插入指定的元素，并移动当前位于该位置的元素。因此，当您知道元素的位置时，您可以在所需位置添加新元素。

list.add(0,"T-Rex");

Answer 2

您可以使用某种层次级别值e.g: T-Rex - 1, Lion - 2, ...映射列表中的每个动物。然后，您可以将所有值放入LinkedList并使用自定义比较器进行排序，或者作为优先级队列的替代方法。

因此，您将在列表中对层次结构进行排序。示例：

class Organism {
    String name;
    int level;

    public Organism(String name, int level) {
         ...
    }
}
PrioriQueue q = new PriorityQueue(...custom_comparator...);
q.add(...add_all_organism_here....)

Answer 3

我会这样做：

创建实现可比较的类有机体，并具有特定于您的类的自定义自然排序。

public class Organism implements Comparable<Organism> {
    private Integer hierarchy;
    private String name;

    public Organism (String nameArg, Integer hierarchyArg) {
         name = nameArg;
         hierarchy = hierarchyArg;
    }

    public Integer getHierarchy() {
        return hierarchy;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Organism a) 
    {
        return this.getHierarchy().compareTo( a.getHierarchy() );
    }
}

现在我可以按任何顺序添加到列表中：

//Put a big gap between the numbers so if you need later you can add more organisms in between 
list.add(new Organism("T-Rex", 1000));
list.add(new Organism("Zebra", 10));
list.add(new Organism("Lion", 500));
list.add(new Organism("Hyena", 200));

然后，您可以使用Java对它们进行排序：

// Java old way of sorting. It will modify the 'list' itself
Collections.sort(list); 

//Java 8+ way of sorting. It does not modify the 'list' but create a new one.
List<String> sortedList = list.stream().sorted().collect(Collectors.toList());

可比接口的文档：https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html

祝好运!