Java:遍历并将元素插入排序链表的最佳方法是什么？

Question

由于链表头部和尾部的插入和删除频繁，所以我选择使用Java API中的链表。并且链表会按照降序排列，即 100,98,97,95,90

LinkedList<MyObject> mylinkedlist = new LinkedList<MyObject>();

Myobject new_value = new MyObject(96);

有时我必须将元素插入到这个链表中(而不是在头部和尾部)。因为链表必须是降序的，所以我必须从头开始按降序或者从尾部升序遍历链表，然后将其插入到正确的位置。指数。

我想出了如下尝试

  int i;
  for(int i=0; i<mylinkedlist.size(); i++)
  {
      if(mylinkedlist.get(num).getInt() <= new_value.getInt()){
         break;
      }
  }

   mylinkedlist.add(i,new_value)

我只能说我上面的代码非常糟糕。但是，有没有办法优化我的代码并避免使用 break同时，还要避免遍历整个链表，因为它可能会超长？

如果可以提供代码示例，我们将不胜感激。谢谢。

更新:对于没有正确表达我的问题表示诚挚的歉意。我的问题应该是鉴于链表当前包含 100,98,97,95,90 ，如果我想插入一个新的不同值，例如 96 。应该如何检测链表的索引，使得新值 96可以插入其中，同时保留链表的降序吗？

在此问题中，保留 (1) 列表的降序和 (2) 列表中元素的唯一性非常重要。

Answer 1

您应该考虑使用其他数据结构，如 TreeSet .

此类实现 SortedSet 并使用自然排序或创建时提供的比较器。然后你只需要添加对象，它就会自动排序。

使用自然排序

在 MyObject 类中:

public int compareTo(MyObject o) {
    return this.getInt() - o.getInt()
}

使用树集:

SortedSet<MyObject> objectSet = new TreeSet<MyObject>();
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

使用比较器

如果您不想修改 MyObject 类(例如):

class MyObjectComp implements Comparator<MyObject> {

    @Override
    public int compare(MyObject o1, MyObject o2) {
        return o1.getInt() - o2.getInt();
    }

}

SortedSet<MyObject> objectSet = new TreeSet<MyObject>(new MyObjectComp());
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

降序集

对于降序集合，可以使用TreeSet的descendingSet方法:

SortedSet<MyObject> objectSet = new TreeSet<MyObject>(new MyObjectComp()).descendingSet();
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

有关Java中排序结构的更多信息，您可以阅读this question .