LinkedList,按大小按升序插入元素

ArrayList 可能不是一个好的选择,因为它在插入中间时将元素向右移位。我查看了 LinkedList ,但在列表中找不到用于在给定节点之前/之后插入的方法。有一个 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。

额外信息: 在这四种情况下,当插入一个新元素时,我从一开始枚举列表,直到找到一个更大的元素,然后在它之前插入新节点。我这样做是因为应用程序需要处理较小的元素。所以我不做向量和数组的二进制搜索。