Java集合框架之List---ArrayList与LinkedList源码分析

时间:2021-07-12 19:19:53

Java集合框架之List---ArrayList与LinkedList源码分析

一、 ArrayList概述:


public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。
ArrayList不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类,也可以使用concurrent并发包下的CopyOnWriteArrayList类。
ArrayList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了Cloneable接口,能被克隆。
每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步

二、 ArrayList的实现:

 对于ArrayList而言,它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析ArrayList的源代码:

   1) 私有属性:

   ArrayList定义类4个私有属性:

 

/**
* Default initial capacity. 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;

//空数组,当调用无参数构造函数的时候默认给个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//这才是真正保存数据的数组
private transient Object[] elementData;

//arrayList的实际元素数量
private int size;

很容易理解,elementData存储ArrayList内的元素,size表示它包含的元素的数量。

有个关键字需要解释:transient。  

  Java的serialization提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。有点抽象,看下Java关键字transient应该能明白。

transient修饰符让elementData无法自动序列化,这样的原因是,数组内存储的的元素其实只是一个引用,单单序列化一个引用没有任何意义,反序列化后这些引用都无法在指向原来的对象。ArrayList使用writeObject()实现手工序列化数组内的元素。

    private void writeObject(java.io.ObjectOutputStream s)  
throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject();

s.writeInt(elementData.length);

for (int i=0; i<size; i++)
s.writeObject(elementData[i]);

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

2) 构造方法:

   ArrayList提供了三种方式的构造器,可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

   // ArrayList带容量大小的构造函数。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

// 新建一个指定容量的数组</span>
this.elementData = new Object[initialCapacity];
}

// ArrayList无参构造函数。默认容量是10。
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}

//构造方法传入一个Collection, 则将Collection里面的值copy到arrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

3) 元素存储:

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)这些添加元素的方法。下面我们一一讲解:

3.1、set(int index, E element): 用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。

    public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}

3.2、add(E e): 将指定的元素添加到此列表的尾部。

数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。所以在初始化ArrayList的时候尽量预算下大致的容量需求,降低平凡调整容量的开销。

    public boolean add(E e) { 
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; return true;
}
private void ensureCapacityInternal(int minCapacity) { //确保内部容量
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

protected transient int modCount = 0; //抽象类AbstractList定义的

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

//超出了数组可容纳的长度,需要进行动态扩展!!!
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//这才是动态扩展的精髓,看到这个方法,ArrayList瞬间被打回原形!!!!1
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;

//设置新数组的容量扩展为原来数组的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

//再判断一下新数组的容量够不够,够了就直接使用这个长度创建新数组,
//不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;

//判断有没超过最大限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

//将原来数组的值copy新数组中去, ArrayList的引用指向新数组
//这儿会新创建数组,如果数据量很大,重复的创建的数组,那么还是会影响效率,
//因此鼓励在合适的时候通过构造方法指定默认的capaticy大小
elementData = Arrays.copyOf(elementData, newCapacity);
}
//检查容量的int值是不是已经溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
 
3.3、add(int index, E element) 

: 将指定的元素插入此列表中的指定位置。如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。 

        //size表示的是现有的元素个数,并非ArrayList的容量,容量应该是数组elementData的长度。
private int size;

public void add(int index, E element) {
rangeCheckForAdd(index);
// 如果数组长度不足,将进行扩容。 方法同上
ensureCapacityInternal(size + 1); //Increments modCount!!

// 将 elementData中从Index位置开始、长度为size-index的元素,
// 拷贝到从下标为index+1位置开始的新的elementData数组中。
// 即将当前位于该位置的元素以及所有后续元素右移一个位置。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;

size++;
}

//比set方法里的rangeCheck(int index)多index < 0,索引不能小于0
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
3.4、addAll(Collection<? extends E> c) :  按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。

    public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

3.5、addAll(int index, Collection<? extends E> c):  从指定的位置开始,将指定collection中的所有元素插入到此列表中。

    public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
 
 
 

4)、元素读取

   // 返回此列表中指定位置上的元素。     
public E get(int index) {
rangeCheck(index);

return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}

 
 

5)、元素删除

ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下:

1、remove(int index):首先是检查范围,修改modCount,保留将要被移除的元素,将移除位置之后的元素向前挪动一个位置,将list末尾元素置空(null),返回被移除的元素。
    public E remove(int index) {        rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}
2、remove(Object o) : 移除此列表中首次出现的指定元素(如果存在)。 即ArrayList中允许存放重复的元素

    public boolean remove(Object o) {
// 由于ArrayList中允许存放null,因此下面通过两种情况来分别处理。
 if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 类似remove(int index),移除列表中指定位置上的元素
 fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

首先通过代码可以看到,当移除成功后返回true,否则返回false。remove(Object o)中通过遍历element寻找是否存在传入对象,一旦找到就调用fastRemove移除对象。为什么找到了元素就知道了index,不通过remove(index)来移除元素呢?因为 fastRemove跳过了判断边界的处理 ,因为找到元素就相当于确定了index不会超过边界,而且fastRemove并不返回被移除的元素。下面是fastRemove的代码,基本和remove(index)一致。

    private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}

3、removeRange(int fromIndex,int toIndex):   

    protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);

// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}


6) 、调整数组容量:

 ensureCapacity(int minCapacity) : 从上面介绍的向ArrayList中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。

    public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。 所以在初始化ArrayList的时候尽量预算下大致的容量需求,降低平凡调整容量的开销。 当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量。


void  trimToSize() : 将底层数组的容量调整为当前列表保存的实际元素的大小的功能。

由于elementData的长度会被拓展,size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况,将出现空间的浪费。trimToSize将返回一个新的数组给elementData,元素内容保持不变,length和size相同,节省空间。

     public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}

关于ArrayList和Vector区别如下:
    ArrayList在内存不够时默认是扩展50% + 1个,Vector是默认扩展1倍。
    Vector提供indexOf(obj, start)接口,ArrayList没有。
    Vector属于线程安全级别的,但是大多数情况下不使用Vector,因为线程安全需要更大的系统开销。


7)、转为静态数组toArray

7.1、Object[] toArray(), 调用Arrays.copyOf将返回一个数组,数组内容是size个elementData的元素,即拷贝elementData从0至size-1位置的元素到新数组并返回。

    public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

7.2、<T> T[] toArray(T[] a) : 如果传入数组的长度小于size,返回一个新的数组,大小为size,类型与传入数组相同。所传入数组长度与size相等,则将elementData复制到传入数组中并返回传入的数组。若传入数组长度大于size,除了复制elementData外,还将把返回数组的第size个元素置为空。

    @SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

8)、Fail-Fast机制:

ArrayList也采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体介绍请参考这篇文章深入Java集合学习系列:HashMap的实现原理 中的Fail-Fast机制。

9)、总结:

关于ArrayList的源码,给出几点比较重要的总结:

    1、注意其三个不同的构造方法。无参构造方法构造的ArrayList的容量默认为10,带有Collection参数的构造方法,将Collection转化为数组赋给ArrayList的实现数组elementData。
    2、注意扩充容量的方法ensureCapacity。ArrayList在每次增加元素(可能是1个,也可能是一组)时,都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时,就设置新的容量为旧的容量的1.5倍加1,如果设置后的新容量还不够,则 直接新容量设置为传入的参数(也就是所需的容量),而后用Arrays.copyof()方法将元素拷贝到新的数组(详见下面的第3点)。从中可以看出,当容量不够时,每次增加元素,都要将原来的元素拷贝到一个新的数组中,非常之耗时,也因此建议在事先能确定元素数量的情况下,才使用ArrayList,否则建议使用LinkedList。
    3、ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法。我们有必要对这两个方法的实现做下深入的了解。
    4、ArrayList基于数组实现,可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,插入删除元素的效率低。
    5、在查找给定元素索引值等的方法中,源码都将该元素的值分为null和不为null两种情况处理,ArrayList中允许元素为null。


--------------------------------------------------------------------------------------------------------------------------


二、LinkedList

框架图

Java集合框架之List---ArrayList与LinkedList源码分析

1、LinkedList类定义

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList的特性:
  1、是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  2、实现 List 接口,能对它进行队列操作
  3、实现 Deque 接口,即能将LinkedList当作双端队列使用。
  4、实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  5、实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  6、是非同步的。

为什么要继承自AbstractSequentialList ?
    AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些骨干性函数。降低了List接口的复杂度。这些接口都是随机访问List的,LinkedList是双向链表;既然它继承于AbstractSequentialList,就相当于已经实现了“get(int index)这些接口”。
    此外,我们若需要通过AbstractSequentialList自己实现一个列表,只需要扩展此类,并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

2、LinkedList数据结构原理
   LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:

Java集合框架之List---ArrayList与LinkedList源码分析
既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:

Java集合框架之List---ArrayList与LinkedList源码分析

二、源码分析

linkedList的源码分析比较简单,熟悉双向循环链表理解起来就特别容易

2.1、私有属性

    transient int size = 0;

transient Node<E> first;

transient Node<E> last;
Node结点的代码
    private static class Node<E> {        E item;        Node<E> next;        Node<E> prev;        Node(Node<E> prev, E element, Node<E> next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }
节点类很简单,item存放业务数据,prev与next分别存放前后节点的信息(在数据结构中我们通常称之为前后节点的指针)。
2.2 构造方法

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

    public LinkedList() { }

public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
2.3、元素批量添加:public boolean addAll(Collection<? extends E> c) ;

第二个构造方法需要用到的

    public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
    /**     * 将collection中的数据从集合index位置开始插入     */    public boolean addAll(int index, Collection<? extends E> c) {        //检验将要插入index的位置是否合法        checkPositionIndex(index);        Object[] a = c.toArray();        int numNew = a.length;        // 没有插入元素        if (numNew == 0)            return false;        /* successor :保存index处的节点。插入位置如果是size,则在头结点前面插入,否则在获取index处的节点插入           predecessor: 获取前一个节点,插入时需要修改这个节点的next引用         */        Node<E> pred, succ;        if (index == size) {            succ = null; //头结点中不存放数据            pred = last;        } else {            succ = node(index);            pred = succ.prev;        }        // 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面        for (Object o : a) {            @SuppressWarnings("unchecked") E e = (E) o;            Node<E> newNode = new Node<>(pred, e, null);            if (pred == null)                first = newNode;            else                pred.next = newNode;            pred = newNode;        }        //因为是循环链表,需要处理最后一个结点        if (succ == null) {            last = pred;        } else {            pred.next = succ;            succ.prev = pred;        }        // 修改size        size += numNew;        modCount++;        return true;    }    private void checkPositionIndex(int index) {        // 插入位置超过了链表的长度或小于0,报IndexOutOfBoundsException异常        if (!isPositionIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }    private boolean isPositionIndex(int index) {        return index >= 0 && index <= size;    }    private String outOfBoundsMsg(int index) {        return "Index: "+index+", Size: "+size;    }    /**     * 获取index处的节点     * 算法思想:简单的二分查找。     * 如果index大于size的一半,从后往前找;否则从前往后找     */    Node<E> node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node<E> x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node<E> x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }
2.4、在链表后面增加元素:public boolean add(E e)
    public boolean add(E e) {        linkLast(e);        return true;    }
    void linkLast(E e) {        final Node<E> l = last;        final Node<E> newNode = new Node<>(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;        size++;        modCount++;    }
get获取元素
    public E get(int index) {        checkElementIndex(index);        //获取index处的节点的数据值        return node(index).item;    }    private void checkElementIndex(int index) {        if (!isElementIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }    private boolean isElementIndex(int index) {        return index >= 0 && index < size;    }    private String outOfBoundsMsg(int index) {        return "Index: "+index+", Size: "+size;    }