【Java容器】List容器使用方法及源码分析

List容器

  • ArrayList:使用动态数组保存元素,支持随机访问。
  • Vector:与ArrayList类似,但是它是线程安全的。
  • LinkedList:使用双向链表保存元素,只能顺序访问,此外可以用作为栈、队列和双向队列。

1 ArrayList

1.1 简介

基于动态数组实现了List接口。除了List接口的所有方法之外,还提供了调整内部数组大小的方法。该类与Vector类大致相同,区别在于ArrayList是不支持同步的。

size,isEmpty,get,set,iterator和listIterator方法都只需时间复杂度为O(1)。其他的操作时间复杂度为O(n)。且常数因子与LinkedList类相比更低。

每个ArrayList实例都有一个capacity,描述了该列表中实际用于存储元素的数组的大小。当向列表中添加元素时,capacity会自动增大。使用ensureCapacity方法,可以在向列表中添加大量元素之前先使数组扩容,避免列表自身多次自动扩容。

1.2 存储结构

ArrayList内部使用一个数组来保存元素,ArrayList的容量就表示该数组的大小,

transient Object[] elementData; // non-private to simplify nested class access

任何空的ArrayList中的elementData数组用一个默认的空数组表示,

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

当向空ArrayList中添加第一个元素时,会扩容到DEFAULT_CAPACITY大小,

private static final int DEFAULT_CAPACITY = 10;

此外,ArrayList中还使用一个size记录当前保存元素的个数,

private int size;

1.3 添加元素

add(E e)方法可以向ArrayList的末尾添加一个元素,

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

其中会先调用ensureCapacityInternal(int minCapacity)方法对elementData数组的大小进行检查与扩容,

private void ensureCapacityInternal(int minCapacity) {
        // ensureCapacity(int minCapacity)方法返回数组所需要的大小
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

然后调用ensureExplicitCapacity(int minCapacity)方法,

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

使用grow(int minCapacity)方法对数组进行扩容并复制旧数组的元素到新数组中,

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;
        // 如果新容量大于MAX_ARRAY_SIZE(2^31-1-8)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 判断要求容量的大小是否大于MAX_ARRAY_SIZE(2^31-1-8)
            // 若要求容量大于MAX_ARRAY_SIZE(2^31-1-8),则新容量为Integer.MAX_VALUE(2^31-1)
            // 否则新容量为MAX_ARRAY_SIZE(2^31-1-8)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // 将旧数组元素复制到新数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

1.4 获取元素

get(int index)方法返回列表中指定位置的元素,

public E get(int index) {
        // 检查下标是否合法
        rangeCheck(index);
        // 返回元素
        return elementData(index);
    }

1.5 删除元素

remove(int index)方法删除列表中指定位置的元素并将其返回,

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);
        // 将数组最后一位设为null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

1.6 fast-fail机制

fail-fast 机制是java集合(Collection)中的一种错误机制。作用是在集合的迭代器的迭代期间,如果发现集合被其他线程修改,则抛出异常,避免执行一些不确定的操作。

例如:当某一个线程A通过迭代器去遍历某集合的过程中,若该集合的内容被其他线程所改变了,那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。

实现方式:

AbstractList中有一个modCount字段用于记录容器结构发生变化的次数,

protected transient int modCount = 0;

结构变化指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,若仅仅设置元素的值不算作结构发生变化,例如,

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 增加modCount
        elementData[size++] = e;
        return true;
    }
        
    public E remove(int index) {
        rangeCheck(index);

        modCount++;    // 增加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;
    }

在使用ArrayList的迭代器时,迭代器中会记录当前列表的modCount

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;    // 记录创建迭代器时,容器的modCount
        ...
    }

在使用迭代器的next()remove()previous()set()add()方法时,会通过检测该字段,判断容器是否被意外地修改了,

// 迭代器类中定义的检查modCount的方法,在迭代时容器被意外修改时抛出异常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

如果容器的modCount与迭代器中记录的expectedModCount不一致,即容器在迭代器遍历期间被修改,就会返回ConcurrentModificationException异常。

1.7 同步

使用Collections.synchronizedList方法可以获得一个线程安全的List,

List list = Collections.synchronizedList(new ArrayList(...));    // 获取线程安全的List

该方法根据输入容器的具体类型,实例化一个SynchronizedCollection类的子类对象,

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        private static final long serialVersionUID = 3053995032091335093L;

        final Collection<E> c;  // 底层Collection容器
        final Object mutex;     // 用于加锁的对象
        //构造方法
        SynchronizedCollection(Collection<E> c) {
            this.c = Objects.requireNonNull(c);    // 输入的Collection对象
            mutex = this;    // 自己作为锁
        }
        ...
    }

在该类中,将原来非线程安全的容器与一个锁组合,并对几乎所有方法加synchronized关键词,使得对容器的操作是线程安全的。

需要注意,当使用SynchronizedCollection类的迭代器时,需要用户自己手动加锁,因为iterator()没有使用同步锁,

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        ...
        // 没有加synchronized修饰
        public Iterator<E> iterator() {
            return c.iterator(); // Must be manually synched by user!
        }
        ...
    }

2 Vector

2.1 简介

Vector的实现与ArrayList相似,也是通过动态变化的数组存储元素,不过使用了synchronized进行同步,

// 添加元素
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    // 获取元素
    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }
    // 删除元素
    public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);

        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--elementCount] = null; // Let gc do its work

        return oldValue;
    }

2.2 ArrayList与Vector

  • Vector是同步的,所以开销比ArrayList大,性能较低。
  • Vector每次扩容默认请求的大小是原容量的2倍(可通过capacityIncrement设置),ArrayList则是原容量1.5倍。

3 LinkedList

3.1 存储结构

LinkedList使用双向链表保存元素,因此在插入删除操作的时候相比底层为数组的ArrayList更快,

// 节点的结构
    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;
        }
    }
    // 头节点
    transient Node<E> first;
    // 尾节点
    transient Node<E> last;

3.2 LinkedList与ArrayList

  • ArrayList基于动态数组,LinkedList基于双向链表。
  • ArrayList支持随机访问,LinkedList不支持。
  • LinkedList在任意位置添加删除元素更快。

相关推荐