欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

Java基础 - Java中ArrayList和LinkedList讲解（测试、适用场景、时复、空复、对比）

程序员文章站 2022-06-09 21:11:57
...

Java中ArrayList和LinkedList讲解

1. 时间复杂度

ArrayList内部是基于对象数组实现的，它的get()方法是按照索引直接获取对应的数据，允许随机访问，效率很高。在访问列表中的任意一个元素时，速度比LinkedList快。

LinkedList内部是基于双向链表实现的，它的get()方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。

现在假设List类型的有一个排好序的大列表（可以是ArrayList/LinkedList），现对这此列表来进行二分查找(binary search)和插入操作（在头部插入，比较极端，为了测试方便），比较ArrayList和LinkedList的查询、添加速度：

//对ArrayList和LinkedList的查找和删除测试
import java.util.*;
public class Demo {
    //准备数据
    public static final int N = 50000;
    public static List values;
    static{
        Integer val[] = new Integer[N];
        Random r = new Random();
        for (int i = 0,cur =0; i < N; i++) {
            cur+=r.nextInt(100)+1;
            val[i] = cur;
        }
        values = Arrays.asList(val);
    }
    //二分查数据
    static long timeSearch(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            int index = Collections.binarySearch(list,values.get(i));//binarySearch()二分查找方法
            if(i != index){
                System.out.println("---error---");
            }
        }
        return System.currentTimeMillis()-start;
    }
    //添加数据
    static long timeAdd(List list){
        long start=System.currentTimeMillis();
        Object o = new Object();
        for(int i=0;i<N;i++)
            list.add(0, o);
        return System.currentTimeMillis()-start;
    }
    
    public static void main(String[] args) {
        System.out.println("查找ArrayList:"+timeSearch(new ArrayList(values)));
        System.out.println("查找LinkedList:"+timeSearch(new LinkedList(values)));
        System.out.println("新增ArrayList:"+timeAdd(new ArrayList(values)));
        System.out.println("新增LinkedList:"+timeAdd(new LinkedList(values)));
    }
}

得到的输出是：

/**
 * 查找ArrayList:9
 * 查找LinkedList:9085
 * 新增ArrayList:308
 * 新增LinkedList:3
 */

以上这个结果是不固定的，但是可以看出在查找时ArrayList的速度明显比LinkedList快。二分查找使用的是随机访问策略，ArrayList支持随机访问，而LinkedList是不支持随机访问的。对一个LinkedList做随机访问所消耗的时间与这个 list 的大小是成比例的，而在ArrayList中进行随机访问所消耗的时间是固定的。

在新增的时候ArrayList明显比LinkedList慢。把一个元素被加到ArrayList的头部，ArrayList中所有已经存在的元素都会后移，这就意味着有大量的数据移动和复制上的开销。而将一个元素加到LinkedList的最开端只是简单的把这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

2. 空间复杂度

LinkedList：在LinkedList中有一个私有的内部类，定义：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个LinkedList对象，在存储一个元素的同时还要存储它的上一个元素和下一个元素，这样一个LinkedList结构中将有很大的空间开销。

ArrayList：ArrayList使用内置的数组来存储元素，这个数组的起始容量是10：

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

每一次数组需要增长时，容量大概会增长50%。如果有一个大量元素的ArrayList对象，那么可能会有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的（每次扩容1.5倍）。频繁的扩容，频繁的对数组进行重新分配，将会导致性能急剧下降。如果知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量（也可通过trimToSize()方法在ArrayList分配完毕之后去掉浪费掉的空间）。

3. 总结

3.1 Java中ArrayList和LinkedList区别和联系

  1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的，LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的实现类，可以根据索引来随机访问集合中的元素，除此之外，LinkedList还实现了Deque接口，Deque接口是Queue接口的子接口，它代表一个双向队列，因此LinkedList可以作为双向队列 ，栈（可以参见Deque提供的接口方法）和List集合使用，功能强大。

  2. 因为Array是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的，可以直接返回数组中index位置的元素，因此在随机访问集合元素上有较好的性能。Array获取数据的时间复杂度是O(1),但是要插入、删除数据却是开销很大的，因为这需要移动数组中插入位置之后的的所有元素。

  3. 相对于ArrayList，LinkedList的随机访问集合元素时性能较差，因为需要在双向列表中找到要index的位置，再返回；但在插入，删除操作是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

  4. LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

3.2 ArrayList和LinkedList有各自所适用的地方

  1. 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
  2. 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
  3. LinkedList不支持高效的随机元素访问。
  4. ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或尾部添加或删除数据,就应该使用LinkedList了。

tips：

ArraList线性表 LinkedList链表
get() 获取第几个下标，时间复杂度 O(1) 获取第几个元素，依次遍历，时间复杂度O(n)
add(E) 在末尾添加，时间复杂度O(1) 在末尾添加，时间复杂度O(1)
add(index,X) 在第index个元素后面插入，后面的元素需要向后移动，时间复杂度O(n) 添加第index个元素后，需要先查找到第几个元素，直接由指针指向操作，复杂度O(n)
remove() 删除元素，后面的元素需要逐个移动，复杂度O(n) 删除元素，直接由指针指向操作，复杂度O(1)
相关标签： java基础 学习总结类 java

上一篇： 前端面试之CSS3动画

下一篇： Java基础 - java.lang.String.charAt()方法的使用，String字符串之间的相加（完美解决内存溢出问题）

推荐阅读