如何重新排序链表?

huangapple 未分类评论46阅读模式
英文:

How do I reorder a linked list?

问题

我正在尝试完成一个关于链表的任务,不幸的是,我不能在网上发布我的代码。但是一般的问题是这样的:

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

但我希望链表按顺序显示(食物链):
orderedList -> 狮子 -> 鬣狗 -> 斑马 -> 草

另外,我可能会向链表中添加一个有机体,比如:

list.add("T-Rex");

那么我期望的结果应该是
orderedList -> T-Rex -> 狮子 -> 鬣狗 -> 斑马 -> 草

如何添加有机体,然后以这样的方式对它们进行排序,以显示层次结构?我可以放下有限数量的有机体,所以我知道应该把它们放在哪里。例如,我知道如果我放置 T-Rex,它将始终位于狮子之上,鬣狗将始终早于草...等等。我一直在尝试在YouTube和Google上找教程,但它们大多是对数字或字符串按字母顺序进行排序,这在我看来并没有真正解决我的问题。

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

英文:

I'm trying to do an assignment about Linked List, unfortunately, I cannot post my code online. But the general problem goes like this:

I have a linked list of organisms:
list -> Zebra -> Hyena -> Lion -> grass

But I want the list to display in order (food chain):
orderedList -> Lion -> Hyena -> Zebra -> grass

Also, I may add an organism to the list like

list.add("T-Rex");

So then my desired outcome should be
orderedList -> T-Rex -> Lion -> Hyena -> Zebra -> grass

How do add organisms and then order them in such a way that it displays a hierarchy? There is a limited number of organism I can put down, so I know exactly where to put them. For example, I knew that if I put T-Rex, it will always be on top of the Lion, Hyena will always be earlier than Grass... and so on.. I've been trying to find tutorials on YouTube and Google but they were mostly sorting numbers or Strings alphabetically, which I don't think really helps my problem.

I would appreciate any help since this is my first time dealing linked list.

答案1

得分: 0

你可以使用

add(int index, E element);

它会将指定的元素插入到列表的指定位置,并移动当前位于该位置的元素。因此,您可以根据元素的位置在所需位置添加新元素。

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

You may use

add(int index, E element);

It inserts the specified element at the specified position in this list and shifts the element currently at that position. So as you know the positions of elements you can add new on at the desired position.

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

答案2

得分: 0

你可以将列表中的每个动物映射到某种层次值,例如:T-Rex - 1,狮子 - 2,...。然后,您可以将所有值放入链表中,并使用自定义比较器进行排序,或者作为替代,使用优先队列。

结果就是,您将在列表中获得一个有序的层次结构。
示例:

class Organism {
    String name;
    int level;

    public Organism(String name, int level) {
         ...
    }
}
PriorityQueue<Organism> q = new PriorityQueue<>(...自定义比较器...);
q.add(...在此处添加所有生物...);
英文:

You can map every animal in your list with some kind of hierarchy level value, e.g: T-Rex - 1, Lion - 2, .... Then you can put all values to the LinkedList and sort with custom Comparator, or as an alternative to the Priority Queue.

As a result, you will have ordered a hierarchy in your list.
Example:

class Organism {
    String name;
    int level;

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

答案3

得分: 0

以下是翻译好的内容:

我会这样做:

创建一个实现了 Comparable 接口的 Organism 类,并具有特定于该类的自定义自然排序。

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

现在,我可以以任何顺序将其添加到列表中:

// 在数字之间留下一个较大的间隔,这样以后如果需要,您可以在其中添加更多的生物
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 旧的排序方式。它会修改 'list' 本身
Collections.sort(list); 

// Java 8+ 排序方式。它不会修改 'list',而是创建一个新列表。
List<String> sortedList = list.stream().sorted().collect(Collectors.toList());

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

祝你好运!

英文:

I would do it this way:

Create class Organism which implement Comparable and have a custom natural ordering specific for your class.

public class Organism implements Comparable&lt;Organism&gt; {
    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() );
    }
}

Now I can add in the list in any order:

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

And then you can use Java to sort them:

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

//Java 8+ way of sorting. It does not modify the &#39;list&#39; but create a new one.
List&lt;String&gt; sortedList = list.stream().sorted().collect(Collectors.toList());

Documentation for Comparable interface:
https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html

Good luck!

huangapple
  • 本文由 发表于 2020年4月10日 14:42:51
  • 转载请务必保留本文链接:https://java.coder-hub.com/61135246.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定