关于arraylist的链表的比较
我知道LinkedList
是作为双链表实现的。 它在添加和删除方面的性能优于Arraylist
,但在get和set方法方面更差。
这是否意味着我应该选择LinkedList
over Arraylist
进行插入?
我写了一个小测试,发现ArrayList
插入速度更快。 那么链表如何比ArrayList
更快?
请参考以下我做过的例子。
import java.util.Date; import java.util.LinkedList; import java.util.List; public class TestLinkedList { public static void main(String[] args) { long lStartTime = new Date().getTime(); System.out.println("lStartTime:: " + lStartTime); List integerList = new LinkedList(); for (int i = 0; i < 10000000; i++) { integerList.add(i); } long lEndTime = new Date().getTime(); System.out.println("lEndTime:: " + lEndTime); long difference = lEndTime - lStartTime; System.out.println("Elapsed milliseconds: " + difference); } }
Linkedlist在插入时确实更快,问题在于你的例子。 在您的代码中,您通过一直追加到最后插入。 对于ArrayList,它就像LinkedList一样简单。 你应该做的是建立一个说5000项的列表,然后开始插入中间。 这里数组变慢 – 你必须在插入位置之后一直移动数组的其余部分。 这将显示出差异。 分析事物的运作方式,不难理解为什么。 这是修改后的代码:
import java.util.Date; import java.util.LinkedList; import java.util.ArrayList; import java.util.List; public class Prob { public static void main(String[] args) { long lStartTime = new Date().getTime(); System.out.println("lStartTime:: " + lStartTime); List integerList = new LinkedList (); for (int i = 0; i < 5000; i++) { integerList.add(0, i); } for (int i = 0; i < 100000; i++) { integerList.add(1000, i); } long lEndTime = new Date().getTime(); System.out.println("lEndTime:: " + lEndTime); long difference = lEndTime - lStartTime; System.out.println("Elapsed milliseconds: " + difference); } }
LinkedList
在插入时不比ArrayList
快。 ArrayList
由数组支持,因此插入元素是微不足道的。 插入到LinkedList
涉及创建一个较慢的新Entry
实例。
插入到ArrayList
的唯一时间可能更慢是插入导致ArrayList
容量增加,这需要创建一个新数组并将旧数组复制到它。