java LinkedList，按大小升序插入元素
在Java中，我希望按大小升序存储元素。在插入之前，我需要处理所有较小的元素。所以我开始枚举处理较小元素的列表，当我遇到较大元素时，我想在这个较大元素之前插入新节点。什么样的数据结构才是最好的选择^{CD1}}可能不是一个好的选择，因为它在插入中间时将元素向右移位。我查看了LinkedList的API，但没有找到在列表中给定节点之前/之后插入的方法。有一个add方法“在列表中的指定位置插入指定的元素”，但它要求该位置为整数。那么，这是否意味着Java实现从一开始就遍历列表，直到找到指定的位置？看起来很贵。我有我想要插入的位置（一个节点），只是一些引用应该被正确地更改，以将新节点包括在列表中。有什么建议吗
谢谢
贾巴
更新：感谢大家的回答，我可以使用ListIterator解决LinkedList的问题。然后我做了一个对比测试，得到了一些令人惊讶的结果。因此，目标是以排序的方式维护列表/数组中的元素。为此，我比较了四种选择：（1）Vector，（2）ArrayList，（3）LinkedList和（4）MyLinkedList，这是我自己的实现（非常简单）。在测试中，我创建了一个包含1000个元素的数组，并用1到100之间的随机整数填充它。然后我将这些元素添加到循环中的每个容器中。当这个数组被添加30次时：MyLinkedList（2.7秒）、LinkedList（6.6秒）、ArrayList（6.9秒）、Vector（7.5秒）。将数组添加100次：MyLinkedList（80.7秒）、ArrayList（82.5秒）、Vector（92.7秒）、LinkedList（176.3秒）。添加数组200次：ArrayList（304.3秒）、Vector（332.7秒）、MyLinkedList（381.2秒）、LinkedList（610.4秒）。 结论：ArrayList总是比Vector更快。因为它不是同步的，所以也就不足为奇了。虽然差别不大。如果列表不太大（在我的例子中最多有100000个元素），我通过自己的实现获得了最好的性能。令人惊讶的是，LinkedList的性能相当差。随着列表规模的增长，LinkedList变得越来越糟糕。最后的结论：如果列表不是太大，那么您可以通过自己的实现获得最佳性能。如果列表的大小非常大，请使用ArrayList。 这个结果让我惊讶，因为ArrayList需要移动很多元素，而链表只需要更改一些引用。但由于ArrayList基于数组，尽管移位次数很高，但它的性能仍优于链表
额外信息：在所有四种情况下，插入新元素时，我从一开始就枚举列表，直到找到一个更大的元素，然后在它前面插入新节点。我这样做是因为应用程序需要处理较小的元素。这就是为什么我不在Vector和ArrayList上进行二进制搜索
# 1 楼答案
你看过
TreeMap吗？一旦你输入一个新值，它就会自动排序我还研究了树（如
DefaultMutableTreeNode）和文档（如XML和DOM）我在那里看到的问题，它们都允许一个节点有多个子节点，而我对纯LinkedList的理解是每个节点只有一个父节点和一个子节点希望这比我上一篇文章更有用
# 2 楼答案
首先，你可以使用SortedList，它会立即为你解决问题
（杜恩，除了我想象中的SortedList，还有其他语言。）
ArrayList#sort可能会有所帮助
如果做不到这一点，您需要一个实现[2参数add method][1]的列表实现
[1]：http://download.oracle.com/javase/1.4.2/docs/api/java/util/List.html#add(int，爪哇。lang.Object）
# 3 楼答案
我在看JavaAPI，Java中没有SortedList类。可以使用java中的集合UTIL。util，例如
Collections.sort(listToSort, comparator)[1]，以获得所需的顺序您必须使用
TreeSet或创建自己的SortedList类，该类围绕现有的列表接口进行包装，并在添加时进行排序# 4 楼答案
如果列表没有重复元素，可以考虑树集。树集为您保持元素的有序排列。它保证了添加、删除等的日志（n）时间