JZTXT

Java中ArrayList与LinkedList的区别

发布时间 2023-11-27 10:40:55作者: 曦欸

一般大家都知道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的区别如下：

  1. ArrayList的实现是基于数组，LinkedList的实现是基于双向链表。

  2. 对于随机访问，ArrayList优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问。而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)

  3. 对于插入和删除操作，LinkedList优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引。

4. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。