Et Voilà | Java 数据结构(二): List

2017-05-10 本文已影响0人 Sophia大黄

今天总结一下List和它的实现类。首先，List是Collection的子接口，它是一种有序集合，List中的元素可以通过索引来进行查找，添加，插入，删除等操作。当然另外一个重要的点就是List允许重复元素的同时存在。有人说List的问题大部分都集中在ArrayList和LinkedList之间的选择上。确实是这样，当确定需要使用List后，使用哪种类型的实现类是摆在每个人面前的选择题。所以我们就需要看看他们的特点，进而选择符合自己需求的实现类。

ArrayList

看到ArrayList这个名字就知道它和Array有着千丝万缕的联系，事实也正是如此，ArrayList的底层实现就是一个object类型的动态数组。说到了动态数组，那就不得不提capacity，也就是容量，如何扩容大黄会具体讲解，这里我们需要看到的是，jdk源码里的初始容量：

    private static final int DEFAULT_CAPACITY = 10;

非常清楚的告知了我们，这个容量初始值为10。然后我们就要把重点转到集合的操作上了，也就是增，插，删，取。

排队进场之Add

add(E e) 方法，是将元素添加在List的尾端，所以大黄美其名曰排队进场。来看下jdk源码：

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

看到那个关于modCount的注释，这是源码就有的哦，我们先押后再聊。关注到方法本身，看到了熟悉的ensureCapacityInternal。在大黄StringBuilder的那篇blog里也有类似方法出现，主要起到了检查容量和进行潜在扩容的作用。看看这里是怎么实现的。

   private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

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

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

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

主要看到grow这个方法， int newCapacity = oldCapacity + (oldCapacity >> 1); 新容量=旧容量*1.5,也就是扩容了50%。可能有些童鞋这一行看不太懂，这个右移是怎么和50%等价的？其实这里是转换为二进制再右移，大约相当于50%增量，举个例子。oldCapacity=10，转为二进制是1010，右移以后就是0101，转回十进制也就是5。然后最后一行，调用了Arrays.copyOf实现了扩容。

任性插队之Insert

插入在ArrayList里并不是以Insert命名的方法，而是add(int index, E element)。老样子，看一下源码：

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

第一行是简单的验证一下index是否在允许范围内，即0~size。然后是容量相关操作，最后就是数据的移动复制，以及插入了。

删除和查找

删除作为基本操作，在ArrayList中有两种实现，一种是remove(int index)，另一种是remove(Object o)，两种方法最底层的实现也是System.arraycopy。而查找的方式基本是get(int index)或是用iterator遍历查找

LinkedList

我们用同样的角度来看一下LinkedList，源码里首先引入眼帘的就是

transient Node<E> first; 
transient Node<E> last;

所以这是典型的通过链表来实现数据结构。继续看下增，插，删，取。

牵起小手之Add

LinkedList的增也是指在List尾端添加新的元素，但是由于是链表结构，实现方式完全不同

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

非常直观，将新加入的元素设为尾节点，然后处理一下size和modCount

直接了当之Insert

和ArrayList一样，这里也是用 add(int index, E element)来完成插入的工作，由于链表的原因，插入在LinkedList里显得更为直接了当。

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

这段代码完成的工作就是将新节点和原来该位置的节点以及该位置后一位的节点联系上。

删除和查找

删除类似于插入的反向工作，断开，重建节点间的联系就能达到删除的目的。查找依然是基于index或基于object，常见的方法有：

get(int index)：返回指定位置处的元素。
getFirst()：返回第一个元素。
getLast()：返回最后一个元素。
indexOf(Object o)：返回第一次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
lastIndexOf(Object o)：返回最后一次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。

爱我还是他

看完了这些比较以后，大家应该已经有了选择ArrayList和LinkedList的思路。其实本质上，选择哪一个其实是在选择数组或者是链表的特性。我们将需求简单的分为：

我的数据相对固定，但是经常需要从List里查找，取出我需要的数据
我不太需要查找，我的数据变化比较大，插入，删除的次数很多很频繁，最后返回给我一个最终答案就好
好了，如果你是 1，请选择ArrayList, 他的随机访问可以帮助你快速锁定需要的元素和它的index。如果你是2，请选择LinkedList,因为...它快!
为什么2不要ArrayList呢? 一个关键的原因就是他插入删除的机制，他需要整个数组的数据移动和复制，你能想象一个size很庞大的ArrayList不停的因为你的插入或删除的需求复制来复制去嘛？所以性能上的缺陷会在数据量很大时体现出来。
另外，针对ArrayList的动态扩容，由于每一次扩容都会对性能产生影响，所以如果我们事先知道这个ArrayList会有多少元素，在构造的时候就给定size是个更优的选择。另外一个好的习惯就是当ArrayList完成了所有的操作，最后调用trimToSize()来把浪费的容量删除，毕竟每次扩展50%并不等于这些扩展的容量都会用尽。像裁缝一样去掉边角料会让整体更加美观，优秀。

餐后甜点之modCount

大黄来兑现一下上面提到的modCount的解析。modCount属于ArrayList的父类AbstractList。每一次调用ArrayList的涉及结构变化的方法时，这个modCount的值都会增加1，添加，删除，插入这样的都属于这类方法。当我们调用了Iterator()方法时，会返回一个Itr对象，在这个对象里，有另一个expectedModCount, 这个变量的值为刚创建迭代对象时List里的modCount。而当这个对象每调用一次next()方法，都会去比较expectedModCount和当下List里的modCount是否相等，如果不相等，则意味着还有其他对象在对我的List进行操作，这时就会抛出ConcurrentModificationException异常。可以认为这是一种避免并发访问破坏数据一致性的保护机制，只不过这个机制以异常为结束。当你需要支持并发访问，需要同时进行迭代和修改，那么这个时候就应该使用另一个ArrayList的兄弟了，CopyOnWriteArrayList。当然，有所了解的同学会说，这个线程安全问题可以将ArrayList更换成Vector，或者使用上一篇我们所说的Colletions里的同步wrapper来进行一次封装。这些大黄将会在后面另开篇幅进行一个总结。

Et Voilà!

Et Voilà | Java 数据结构(二): List

ArrayList

排队进场之Add

任性插队之Insert

删除和查找

LinkedList

牵起小手之Add

直接了当之Insert

删除和查找

爱我还是他

餐后甜点之modCount

猜你喜欢

热点阅读