一般大家都知道ArrayList和LinkedList的区别:
1、ArrayList的实现是基于数组,LinkedList的实现是基于双向链表。
2、对于随机访问,ArrayList优于LinkedList
3、对于插入和删除操作,LinkedList优于ArrayList
4、LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
一.在时间复杂度上的区别
假设我们有两个很大的列表,它们里面的元素已经排好序了,这两个列表分别是ArrayList类型和LinkedList类型的,现在我们对这两个列表来进行二分查找(binary search),比较它们的查找速度。
import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; public class Demo1 { static List array = new ArrayList(); static List linked = new LinkedList(); public static void main(String[] args) { for (int i = 0; i < 10000; i++) { array.add(i); linked.add(i); } System.out.println("ArrayList访问消耗的时间:" + getTime(array)); System.out.println("LinkedList访问消耗的时间:" + getTime(linked)); } public static long getTime(List list) { long time = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { int index = Collections.binarySearch(list, list.get(i)); if (index != i) { System.out.println("ERROR!"); } } return System.currentTimeMillis() - time; } }
运行结果:
ArrayList访问消耗的时间:10
LinkedList访问消耗的时间:383
可以看出,对于随机访问,ArrayList的访问速度更快。
ArrayList和LinkedList的插入数据耗时:
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Demo2 { static List array = new ArrayList(); static List linked = new LinkedList(); public static void main(String[] args) { for (int i = 0; i < 10000; i++) { array.add(i); linked.add(i); } System.out.println("ArrayList插入消耗的时间:" + insertTime(array)); System.out.println("LinkedList插入消耗的时间:" + insertTime(linked)); } public static long insertTime(List list) { long time = System.currentTimeMillis(); for (int i = 100; i < 10000; i++) { list.add(10, i); // 在索引为10的位置插入i } return System.currentTimeMillis() - time; } }
运行结果:
ArrayList访问消耗的时间:31
LinkedList访问消耗的时间:4
可以看出,对于插入操作,LinkedList 的速度更快。
总结:
ArrayList和LinkedList的区别如下:
-
ArrayList的实现是基于数组,LinkedList的实现是基于双向链表。
-
对于随机访问,ArrayList优于LinkedList,ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问。而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起,在这种情况下,查找某个元素的时间复杂度是O(n)
-
对于插入和删除操作,LinkedList优于ArrayList,因为当元素被添加到LinkedList任意位置的时候,不需要像ArrayList那样重新计算大小或者是更新索引。
4. LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
- LinkedList ArrayList Javalinkedlist arraylist java linkedlist arraylist vector java linkedlist arraylist java p11 linkedlist arraylist linkedlist arraylist框架vector linkedlist arraylist vector list 相同点linkedlist arraylist vector linkedlist arraylist vector linkedlist arraylist源码 异同linkedlist arraylist