前言

前面我们对Java集合框架有了一个基本的认识, 这里我们从几大接口入手, 逐步讲解其实现类; 下面要讲解的是List的实现类, 即常用的ArrayList和LinkedList

文章源码基于JDK8

Java集合框架系列博客:

正文

一. ArrayList

1.1 特点概述

这里先将结论给出, 稍后会挑重难点详细讲解

动态数组: ArrayList是一个动态数组, 所谓的动态数组, 就是使用时不必担心扩容问题(会自动扩容, 其实现原理其实也是通过创建一个更大的数组来进行数据拷贝, 关于扩容规则稍后会细讲);
支持随机访问: 既然是基于数组实现的, 那么其当然也就具备了数组的随机访问特点, Java中通过RandomAccess接口来标识List是否支持随机访问(该接口实际上没有方法, 只是为了在使用某些算法时, 通过instanceof RandomAccess去判断作用对象是否支持随机访问, 如果支持的话, 就可以使用某些特定算法)
支持序列化: 实现了Serializable接口
Iterator遍历
线程不安全: 多线程使用时可能会出现问题

1.2 动态数组

ArrayList的默认初始容量为10, 其提供了三个构造函数, 分别是: public ArrayList(int initialCapacity)(支持指定初始容量); public ArrayList()(无参构造函数); public ArrayList(Collection<? extends E> c)(支持从已有数据集创建)

我们最常见的用法是: ArrayList<T> arr = new ArrayList();; 因此我们先来看其无参构造函数, 如下; 其中elementData就是用于存储数据的数组; DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个初始长度为0的数组, 这样设计的原因也是为了节约空间(因为没必要一开始就占用内存空间, 合理的做法应该是在具体需要使用的时候再去分配)

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

如果是使用无参构造函数进行创建的话, 那么在第一次使用add()进行数据添加的时候会进行第一次扩容, 也就是扩展到默认初始容量(10); 见下面代码:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 此时size为0
        elementData[size++] = e;
        return true;
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 这里相等进入
            return Math.max(DEFAULT_CAPACITY, minCapacity); // 返回默认初始容量
        }
        return minCapacity;
    }

那如果并非是第一次执行add()操作呢, 其扩容规则又如何; 这里的代码也比较简单, 在下面的grow()函数中; 逻辑比较简单, 扩容规则是, 增加当前数组长度的50%; 那么是不是每次执行add操作的时候都会进行扩容呢, 肯定不是的, 只有当add会造成溢出时才会进行扩容

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; // 注意这里用来判断的是数组的长度, 而不是当前数据个数
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容50%
        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);
    }

1.3 随机访问

ArrayList由于内部使用数组实现, 所以能够支持快速的索引定位, 但是数组的连续空间在带来增加和索引查找便利的同时, 也使得删除元素变得相对耗时, 所以在实际使用的时候, 需要根据需求特点来合理选择

1.4 Iterator遍历

ArrayList支持普通的Iterator遍历, 也自己实现了一个特殊的ListIterator遍历

1.4-1 Iterator遍历的效率

关于Iterator遍历, for循环遍历和foreach遍历的效率分析, 可以参见文末参考链接

这里只是单纯的讲一下结论:

在ArrayList中使用for循环遍历的效率比另外两种高, 因为其支持随机访问; for循环适合访问顺序存储结构, 可以根据下标快速获取指定元素(即支持随机访问)
Iterator适合访问链式存储结构(如在LinkedList中其访问效率就比for高), 因为迭代器是通过next()和Pre()来定位的, 但它也可以访问顺序存储结构的集合(forEach的使用效率其实和Iterator差不多)
使用Iterator最大的一个好处是, 可以随时修改或者删除集合内部的元素, 并且是在不需要知道元素和集合的类型的情况下进行的(当需要对不同的容器实现同样的遍历方式时, 迭代器是最好的选择)

1.4-2 Iterator和ListIterator

二者最大的区别就是ListIterator支持双向的遍历, 而Iterator只是常规的从头到尾的遍历

1.5 线程不安全

ArrayList不是一个线程安全的集合, 如果要在多线程的情况下使用, 可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类, 也可以使用concurrent并发包下的CopyOnWriteArrayList类或者遗留的Vector

另外就是使用Iterator遍历的过程中, 如果用户add或者remove了元素的话, 会抛出ConcurrentModificationException异常, 其实这也是一种保护机制, 具体代码如下; 至于modCount是每次调用add或者remove方法都会自增的

        public E next() {
            checkForComodification();
            ...
        }

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

        int expectedModCount = ArrayList.this.modCount;  // 这个值在初始化Iterator时就确定了

二. LinkedList

2.1 特点概述

老规矩, 先给出总的结论!

特殊数据结构: LinkedList可以被用作特殊的数据结构, 如: 双向链表, 堆栈, 队列或者双端队列等
序列化: 实现了Serializable接口
线程不安全: LinkedList不支持线程同步, 当使用Iterator或者ListIterator去遍历的时候, 在多线程时, 可能会出现问题(抛出ConcurrentModificationException异常)

2.2 特殊数据结构

LinkedList内部是以Node为节点连接起来的一个链表, 从Node节点的组织方式(如下), 其实也可以看出, 其有两个指针, 一个指向前驱, 一个指向后继, 那么很自然的, 其就支持双向的遍历, 同时, LinkedList对外提供了丰富的接口, 让我们可以根据自己的需要, 去选择将其视为哪种数据结构来使用

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

和ArrayList一样, 我们可以使用ListIterator来方便的实现双向的遍历, 同时其还提供了addFirst()和addLast()方法, 以及明确的push()和pop()方法, 那么我们就可以根据自己的组织方式将其视为双向链表或者堆栈等来使用, 当然, 其还有许多其他有用接口, 具体使用时再去查看即可, 这里不做多讲

2.3 线程不安全

和ArrayList一样, 其也没有实现线程同步, 所以在多线程时, 也要慎用; 当然, 可以使用Collections.synchronizedList(new LinkedList(...))来进行包装, 成为一个线程安全的LinkedList

上面讲了ArrayList使用Iterator或者ListIterator遍历的过程中, 如果对数据进行了修改, 那么会抛出异常, 对于LinkedList也有同样的问题, 原因也一样, 这里不再赘述

三. 总结

到这里, 与List有关的两个常用实现类ArrayList和LinkedList就讲解完了, 重点在于掌握每种实现的特点, 在实际使用的时候再去具体选择, 总的来说, 这两种实现都比较简单, 涉及到的算法也不难; 需要回顾的话, 翻到前面去看每种实现的概述即可!

四. 参考链接

Iterator和for效率分析

Java集合框架之List

讲解List的实现类

前言

正文