本文系记录对Java中集合类List的学习资料，如有异议，欢迎联系我讨论修改。PS:图侵删！如果看不清图请访问:传送门

1 List

List是Collection类下的一个接口，用于存储元素，其兄弟结构如下图：

2 ArrayList

基本信息

ArrayList的声明如下：

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

可以看出，ArrayList实现了RandomAccess, Cloneable, java.io.Serializable，提供随机下标访问(O(1)时间访问元素，实际上就是个空接口，仅用于标识具有该功能)，拷贝，序列化等功能。主要成员变量如下：

    private static final long serialVersionUID = 8683452581122892189L;    // 序列化使用的uid
    private static final int DEFAULT_CAPACITY = 10;   // 默认初始化容量
    private static final Object[] EMPTY_ELEMENTDATA = {};   // 空实例时用于共享的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};   // 空实例时用于共享的默认空数组
    transient Object[] elementData;   // 实际存储数据的数组，注意使用了transient进行修饰，在序列化时有特殊作用
    private int size;   // 实际容量

从定义可知，ArrayList是以数组为媒介进行元素存储。

构造函数

构造函数如下，没啥特别需要说的：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

核心扩容功能

下面介绍ArrayList中核心的功能——扩容，ArrayList每次会将容量变为原来的1.5倍，然后进行数据拷贝，期间涉及多次为前缀的函数调用：

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

核心过程以如下文字表示：

boolean add(E e):先调用void ensureCapacityInternal(size+1)确保添加后数组不越界，返回后添加数据
void ensureCapacityInternal(int minCapacity)：获取默认容量和传入参数的较大者，然后调用ensureExplicitCapacity(minCapacity)
void ensureExplicitCapacity(int minCapacity)：modCount自增；参数值大于当前数组长度，进行扩容，调用grow(minCapacity)
void grow(int minCapacity)：进行扩容，每次设定新容量为旧容量的1.5倍(int newCapacity = oldCapacity + (oldCapacity » 1))
扩容时要停下来执行复制逻辑，因此时间开销不容忽视，最好在使用前预估所需容量，构造时提前初始化容量，避免频繁复制。

在实际复制的时候调用了Arrays.copyOf()执行复制。而Arrays.copyOf()实际调用了System.arraycopy()，二者的区别如下：

Arrays.copyOf()内部实际调用了System.arraycopy()方法
System.arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置
Arrays.copyOf()是系统自动在内部新建一个数组，并返回该数组
System.arraycopy效率要高一些
对于基本数据类型来说System.arraycopy() 方法是深拷贝；对于引用数据类型来说 System.arraycopy()方法是浅拷贝
System.arraycopy线程不安全

public static byte[] copyOf(byte[] original, int newLength){
    byte[] copy = new byte[newLength];
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}
public static void arraycopy(
            Object src,  //源数组
            int srcPos,  //源数组的起始位置
            Object dest, //目标数组
            int destPos, //目标数组的起始位置
            int length   //复制长度
        )

常见API源码

下面给出一些常使用的方法源码，没啥难度，源码基于JDK1.8：

    // 返回实际容量
    public int size() {
        return size;
    }
    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    // 判断是否包含指定元素，实际调用了indexOf函数
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    // 查询指定元素的下标，不存在则返回-1
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    // 拷贝函数，返回当前对象的拷贝
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    // 转化为数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    // 添加元素，这里体现了增删复杂度为O(n)
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    // 删除元素，这里体现了增删复杂度为O(n)
    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;
    }
    // 清除所有元素，并对GC进行优化
    public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

Arrays.asList()与ArrayList

在Arrays类中，有函数Arrays.asList()用于返回一个List，但是此List不同于普通的ArrayList。Arrays.asList()是Arrays类下的一个方法，用于将数组装换成List。在使用时需要注意的是，传入的数组必须是对象数组，而不能是基本类型数组。当传入一个基本类型数组时，Arrays.asList()真正得到的参数不是数组中的元素，而是数组本身导致List只存在一个元素，即这个数组。为了解决这一问题，使用基本类型的包装类即可。此外，在转换为List后不能使用集合修改方法add()、remove()、clear()等方法，否则会抛出异常。造成这一现象的原因是方法返回的并不是新的java.util.ArrayList，而是Arrays的一个内部类，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。而且，通过对数组的修改，会使得List中的对应值也发生改变。

List遍历的选择优先级

实现了 RandomAccess 接口的list，优先选择普通 for 循环，其次 foreach,
未实现 RandomAccess接口的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的,），大size的数据，千万不要使用普通for循环

3 LinkedList

基本信息

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

可以看出，LinkedList实现了Deque(双向队列), Cloneable, java.io.Serializable，提供双向队列，拷贝，序列化等功能。主要成员变量如下：

    transient int size = 0;     // 实际容量
    transient Node<E> first;    // 头结点
    transient Node<E> last;     // 尾结点

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;
        }
    }

从定义可知，LinkedList是以链表为媒介进行元素存储，核心的链表结点定义为其内部静态类Node，通过next和prev分别指向后继节点和前驱节点。

构造函数

    public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

常见API源码

private void linkFirst(E e)     // 添加头结点
void linkLast(E e)      // 添加尾结点
void linkBefore(E e, Node<E> succ)      // 在指定结点前添加结点
private E unlinkFirst(Node<E> f)        // 移除头结点
private E unlinkLast(Node<E> l)         // 移除尾结点
E unlink(Node<E> x)     // 移除指定结点
public E getFirst()     // 获取头结点
public E getLast()      // 获取尾结点
public E removeFirst()  // 移除头结点
public E removeLast()   // 移除尾结点
public void addFirst(E e)       // 添加头结点
public void addLast(E e)        // 添加尾结点
public boolean contains(Object o)       // 判断是否包含指定结点
public int size()       // 获取容量

4 区别与对比

ArrayList与Vector的区别&为什么要用Arraylist取代Vector呢？

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。
Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。

ArrayList和LinkedList的区别

是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

Java学习系列之集合List

1 List

2 ArrayList

基本信息

构造函数

核心扩容功能

常见API源码

Arrays.asList()与ArrayList

List遍历的选择优先级

3 LinkedList

基本信息

构造函数

常见API源码

4 区别与对比

ArrayList与Vector的区别&为什么要用Arraylist取代Vector呢？

ArrayList和LinkedList的区别

Similar Posts

Comments