首页 / JAVA  

Java中ArrayList和LinkedList区别

一般大家都知道ArrayList和LinkedList的大致区别: 

 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 (LinkedList是双向链表,有next也有previous)
 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。 
 3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。 

ArrayList和LinkedList是两个集合类,用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢?什么时候应该用ArrayList什么时候又该用LinkedList呢?

ArrayList

ArrayList是Java集合常用的数据结构之一,继承自AbstractList,实现了List,RandomAccess、Cloneable、Serializable等一系列接口,支持快速访问,复制和序列化。底层是基于数组实现容量大小动态变化,允许null值存在。

ArrayList使用一个内置的数组来存储元素,这个数组的起始容量是10.当数组需要增长时,新的容量按如下公式获得:新容量=(旧容量*3)/2+1,也就是说每一次容量大概会增长50%。这就意味着,如果你有一个包含大量元素的ArrayList对象,那么最终将有很大的空间会被浪费掉,这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素,数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配,将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素,我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

private transient Object[] elementData;  
 /** 
  * The size of the ArrayList (the number of elements it contains). 
  * 
  * @serial 
  */  
 private int size;
ArrayList类中只定义了两个私有属性,很容易理解,elementData存储ArrayList内的元素,size表示它包含的元素的数量。


ArrayList提供了三个构造函数:

 ArrayList():默认构造函数,提供初始容量为10的空列表。

 ArrayList(int initialCapacity):构造一个具有指定初始容量的空列表。

 ArrayList(Collection<? extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

ArrayList添加元素过程

有这么一段代码:

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("000");
    list.add("111");
}

 看下底层会做什么,进入add方法的源码来看一下:

public boolean add(E e) {
     ensureCapacity(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
}
从上面的源码可以看出,添加元素时,会先判断是否需要扩容,如果需要扩容先扩容,把之前的元素复制到新的elementData数组后,最后才添加新的元素


扩容处理逻辑

我们知道ArrayList默认的构造,底层数组大小是10:

public ArrayList() {
     this(10);
}

那么当我们进行添加元素的时候,它是怎么扩容的呢?

在add()这个方法里我们可以看到 有ensureCapacity(size + 1)这么一个方法,这个方法就是用来判断本次添加元素是否需要进行扩容的,源代码:

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
               // minCapacity is usually close to size, so this is a win:
               elementData = Arrays.copyOf(elementData, newCapacity);
    }
}
在添加元素时,先计算数组元素个数并加1(size+1),然后作为参数传给ensureCapacity 这个方法;然后再通过(size+1)与 elementData 这个数组的长度做比较来决定是否需要扩容处理;扩容时,会先创建一个新的指定大小的新的数组,然后把之前的元素都复制到新数组里

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
       T[] copy = ((Object)newType == (Object)Object[].class)
           ? (T[]) new Object[newLength]
           : (T[]) Array.newInstance(newType.getComponentType(), newLength);
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
}

看到扩容的时候把元素组大小先乘以3,再除以2,最后加1。可能有些人要问为什么?我们可以想:

1、如果一次性扩容扩得太大,必然造成内存空间的浪费

2、如果一次性扩容扩得不够,那么下一次扩容的操作必然比较快地会到来,这会降低程序运行效率,要知道扩容还是比价耗费性能的一个操作

所以扩容扩多少,是JDK开发人员在时间、空间上做的一个权衡,提供出来的一个比较合理的数值。

插入元素

看一下ArrayList的插入操作,插入操作调用的也是add方法,比如:

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("111");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("555");
    list.add("666");
    list.add("777");
    list.add("888");
    list.add(2, "000"); // 在指定位置插入元素
    System.out.println(list);
}
运行结果:

[111, 222, 000, 333, 444, 555, 666, 777, 888]
看一下插入的时候做了什么:

// 将指定的元素插入此列表中的指定位置。  
// 如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。  
public void add(int index, E element) {  
   if (index > size || index < 0)  
       throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
   // 如果数组长度不足,将进行扩容。  
   ensureCapacity(size+1);  // Increments modCount!!  
   // 将 elementData中从Index位置开始、长度为size-index的元素,  
   // 拷贝到从下标为index+1位置开始的新的elementData数组中。  
   // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  
   System.arraycopy(elementData, index, elementData, index + 1, size - index);  
   elementData[index] = element;  
   size++;  
}
从上面代码可以看到,当我们插入的元素(实际就是添加元素)时,只要不是在数组的尾部即调用add()方法只传一个参数添加元素时,也就是说我们在数组中间或者头部添加元素时,从指定插入的位置到后面所有的元素它们的位置都会向右移动一个位置;这也就是为什么ArrayList在添加和删除元素时效率低的原因,这是非常麻烦和耗时的,所以如果指定的数据集合需要进行大量插入(中间插入)操作,推荐使用LinkedList

删除元素

接着我们看一下删除的操作。ArrayList支持两种删除方式:

1、按照下标删除

2、按照元素删除,这会删除ArrayList中与指定要删除的元素匹配的第一个元素

对于ArrayList来说,这两种删除的方法差不多,都是调用的下面一段代码:

int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
             numMoved);
elementData[--size] = null; // Let gc do its work
其实做的事情就是两件:

1、把指定元素后面位置的所有元素,利用System.arraycopy方法整体向前移动一个位置

2、最后一个位置的元素指定为null,这样让gc可以去回收它

ArrayList的优缺点

从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下:

1、ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。

2、ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。

不过ArrayList的缺点也十分明显:

1、删除元素的时候,从删除位置起后面所有元素都往前移动一个位置,那么就会比较耗费性能。

2、插入元素的时候,只要不是顺序插入,而是指定插入元素的位置时,那么从插入位置到后面所有的元素都会往后移动一个位置,那么就会比较耗费性能。

因此,ArrayList比较适合顺序添加、随机get访问的场景。

ArrayList是线程非安全的,这很明显,因为ArrayList中所有的方法都不是同步的,在并发下一定会出现线程安全问题。那么我们想要使用ArrayList并且让它线程安全怎么办?一个方法是用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List,比如:

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
    System.out.println(synchronizedList.get(i));
}


LinkedList

LinkedList 是 Java 集合中比较常用的数据结构,与 ArrayList 一样,实现了 List 接口,只不过 ArrayList 是基于数组实现的,而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList,而随机访问上则 ArrayList 性能更好。
除了 LIst 接口之外,LinkedList 还实现了 Deque,Cloneable,Serializable 三个接口。这说明该数据结构支持队列,克隆和序列化操作的。与 ArrayList 一样,允许 null 元素的存在,且是不支持多线程的。

LinkedList是基于链表实现的,所以先讲解一下什么是链表;
链表由一些节点组成,物理存储非连续的线性表。其中每个节点都会存储下个节点的指针,由于实际存储空间不连续,对链表插入节点,删除节点可以达到O(1)的复杂度,但是对一个节点的访问需要O(n)的时间。

单向链表
单向链表的每个节点有数据项和指针(指向下个节点地址数据)组成,下图为一个单向链表,表头没有数据项,只有指向下一个节点的指针。表尾节点指向下一个节点pNext指针为NULL(空)。


插入节点操作:

单向链表中由四个数据节点,数据1,数据2,数据3,数据4,现在数据1和数据2节点间插入数据5,只需把数据1节点的pNext指向新的节点,把新节点的pNext指向数据2节点即可。

删除节点操作
删除节点2,只需把第一个节点的pNext执行数据3节点,同时释放节点2的存储空间即可。

所以链表的插入和删除效率是很高的,因为它不需要移动节点的位置,

双向链表
双向链表有别于单向的,每个节点除了数据项外有两个指针分别指向前一个节点和后一个节点,占用空间会大一些,可以实现从头到尾的遍历,又可以从尾到头遍历。


插入节点操作:


节点1与节点2之间插入新节点5,需要把节点1的pNext指向节点5,节点5的pHead指向节点1,节点5的pNext指向节点2,节点2的pHead指向节点5,如下图所示:

删除节点操作:

删除节点2,把节点1的pNext指向节点3,把节点3的pHead指向节点1,同时释放节点2的存储空间即可。

链表与数组区别

1.链表存储空间不连续,可以充分利用碎片空间,数组的存储空间是连续的,内存空间要求高,必须要有足够连续的内存空间。

2.链表的插入删除元素简单,无需对元素移动,但查询元素会慢,数组对元素的插入删除较复杂,同时使用时要预先指定长度,但数组的查询会很快。


LinkedList源码分析

LinkedList中定义了两个私有属性:

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

header是双向链表的头节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next,element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 
size是双向链表中节点实例的个数。


首先来了解节点类Entry类的代码。

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
   }
}
看到LinkedList的Entry中的"E element",就是它真正存储的数据。"Entry<E> next"和"Entry<E> previous"表示的就是这个存储单元的前一个存储单元的引用地址和后一个存储单元的引用地址。用图表示就是:

构造函数

LinkedList提供了两个构造方法,如下所示:
public LinkedList() {
    header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {
    this();
   addAll(c);
}

执行完构造函数后,header实例自身形成一个闭环,如下图所示:



第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。


添加元素

首先看下LinkedList添加一个元素是怎么做的,假如我有一段代码:
 List<String> list = new LinkedList<String>();
     list.add("111");
     list.add("222");
当我们 new LinkedList 时,其实做了几件事情

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null); // 链表节点
    private transient int size = 0;
    /**
     * Constructs an empty list.
     */
    public LinkedList() {
        header.next = header.previous = header;
    }
    ...
}
看到,new了一个Entry出来名为header,Entry里面的previous、element、next都为null,执行构造函数的时候,将节点的previous和next的值都设置为header(节点)的引用地址
那么执行完"List<String> list = new LinkedList<String>()"之后可以这么表示:


接着看第4行add一个字符串"111"做了什么:

public boolean add(E e) {
     addBefore(e, header);
     return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); // 三个参数分别表示 Entry里面的 previous、element、next
    newEntry.previous.next = newEntry; // 当前节点的前一个节点的next指针指向 当前节点地址
    newEntry.next.previous = newEntry; // 当前节点的下一个节点的previous 指针指向 当前节点地址
    size++;
    modCount++;
    return newEntry;
}

从上图可以看出,双向链表中,一是任意节点都可以向前和向后寻址,二是整个链表头的previous表示的是链表的尾Entry,链表尾的next表示的是链表的头Entry

查看元素

看一下LinkedList的代码是怎么写的:

public E get(int index) {
    return entry(index).element;
}
// 获取双向链表中指定位置的节点    
private Entry<E> entry(int index) {    
    if (index < 0 || index >= size)    
        throw new IndexOutOfBoundsException("Index: "+index+    
                                            ", Size: "+size);    
    Entry<E> e = header;    
    // 获取index处的节点。    
    // 若index < 双向链表长度的1/2,则从前向后查找;    
    // 否则,从后向前查找。    
    if (index < (size >> 1)) {    
        for (int i = 0; i <= index; i++)    
            e = e.next;    
    } else {    
        for (int i = size; i > index; i--)    
            e = e.previous;    
    }    
    return e;    
}
由于LinkedList是双向链表,所以LinkedList既可以向前查找,也可以向后查找,第10行~第16行的作用就是:当index小于数组大小的一半的时候(size >> 1表示size / 2,使用移位运算提升代码运行效率),从前向后查找;否则,从后向前查找。


删除元素

看完了添加元素,我们看一下如何删除一个元素。和ArrayList一样,LinkedList支持按元素删除和按下标删除,前者会删除从头开始匹配的第一个元素。用按下标删除举个例子好了,比方说有这么一段代码:

public E remove(int index) {
    return remove(entry(index));
}
private E remove(Entry<E> e) {
    if (e == header)
        throw new NoSuchElementException();
    // 保留将被移除的节点e的内容
    E result = e.element;
    // 将前一节点的next引用赋值为e的下一节点
    e.previous.next = e.next;
    // 将e的下一节点的previous赋值为e的上一节点
    e.next.previous = e.previous;
    // 上面两条语句的执行已经导致了无法在链表中访问到e节点,而下面解除了e节点对前后节点的引用
    e.next = e.previous = null;
    // 将被移除的节点的内容设为null
    e.element = null;
    // 修改size大小
    size--;
    modCount++;
    // 返回移除节点e的内容
    return result;
}
清空预删除节点:
e.next = e.previous = null;
e.element = null;

交给gc完成资源回收,删除操作结束。
与ArrayList比较而言,LinkedList的删除动作不需要“移动”很多数据,从而效率更高。

总结 
ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下: 
1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。

2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。

3.LinkedList不支持高效的随机元素访问。

4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说:当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能;当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。
2019-10-26