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

使用 TreeSet：

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 的降序集方法：

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

有关 Java 中排序结构的更多信息，您可以阅读此问题。

Answer 2

如果您必须使用列表，则可以使用标准 API 实现相同的结果：Collections.binarySearch方法完全提供了您正在寻找的功能。

因此，代码将类似于以下内容：

private static void insert(List<MyObject> items, MyObject newValue) {
int insertionPoint =
Collections.binarySearch(items, 
newValue, 
// reversed comparator is used because the items are in DESC order
Comparator.comparingInt(MyObject::getInt).reversed());
// if newValue is not in the list, insertionPoint will be negative, see javadoc
int i = (insertionPoint < 0) ? -insertionPoint - 1 : insertionPoint;
// add it at i, even if duplicate (?)
items.add(i, newValue);
}

这并没有真正优化解决方案，只是稍微清理了一下，消除了中断并重用了标准 API。javadoc 给出了一些关于其效率的细节：

此方法以 log(n) 时间运行"随机访问"列表(提供近恒定时间的位置访问)。如果指定的列表未实现 RandomAccess 接口并且很大，则此方法将执行基于迭代器的二叉搜索，该搜索执行 O(n) 链接遍历和 O(log n) 元素比较。

如果列表变得很大并且您开始寻求效率，我建议您切换到ArrayList，它实现了RandomAccess并且只要尊重项目的顺序，效率会更高。

如果您的集合不允许重复项，则最好使用排序集。