实现List接口的重要集合源码分析

2020-07-16 本文已影响0人 CryFace

List接口是类集Collection下一个比较重要的接口，它的下面有很多我们常用的实现类，而我们这次主要是介绍它的三个重要实现类！

ArrayList（底层数据结构是数组，线程不安全）
LinkedList（底层数据结构是链表，线程不安全）
Vector（底层数据结构是数组，线程安全）

ArrayList分析

ArrayList类扩展了AbstractList并实现了List接口。它支持随需要而增长的动态数组，也就是说可以动态地增加或减少其大小。它的底层是一个数组，创建的时候有着原始的大小，当超过了它的大小，类集自动增大。当对象被删除后，数组就可以缩小。

默认属性

ArryList的默认有几个属性，其中包含了默认的数组大小，定义为空返回的数组，以及默认返回的数组，还有实际数组大小的变量。我们先理清楚就比较能明白后面的扩容机制

//数组默认的大小
private static final int DEFAULT_CAPACITY = 10;
//当ArrayList指定数组容量为0的时候，返回的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认返回的，只要不是指定为0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存添加到ArrayList的元素，当第一次添加到ArrayList中的时候就会进行扩容
transient Object[] elementData;
//ArrayList的实际大小
private int size;

为了方便，transient Object[] elementData这个数组下面我会简称为操作数组，也就是我们实际进行操作的。

构造方法

上面我们也了解到了ArrayList定义的几个属性，下面我们来介绍关于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);
        }
    }

我们可以指定ArrayList的初始大小，如果大于0就是先对我们用来添加元素的数组进行初始化；如果为0就是我们上面上面说的，返回数组容量为0的数组；如果小于0，那就给你异常了呵呵。

第二个构造方法

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

这是一个定义了构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。？是任意类的意思，E是我们指定的类型，泛型，也就是继承了Collection的集合。

我们将集合转换成数组，如果长度等于0还是返回容量为0的数组，如果不是就调用Arrays.copyOf进行复制给我们的ArrayList操作数组。

常用方法分析

ArrayList的方法有很多，但是我们只要从常见的增删改查一步一步分析，就可以了解了底层很多的实现机制！

增加方法

增加方法有两个，一个是直接添加，一个是按角标进行添加！

直接添加 add(E e)

首先我们来看看它的增加方法，下面这个增加方法，就是直接增加了一个元素。它首先是尝试容量+1，也就是分析对我们的容量有没有必要加1，这是为了防止数组越界！然后就是对我们的操作数组进行元素的添加，然后返回true！

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        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;
        }

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

简单的分析它们进行了什么的操作

如果我们操作数组不等于默认数组，返回我们实际大小加1，这是需要扩容了！如果等于的话，返回与默认容量较大的那个数，因为我们下面要进行判断，我们如果要进行扩容总不能扩到比默认还小吧！
然后就是minCapacity - elementData.length > 0这一步，如果加1操作后的容量大于我们操作数组的长度的话，调用grow方法进行扩容！传入的参数就是我们的最小需要的扩容大小！

那么就到了我们的grow方法

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

我们进行了数组的大小扩容，int newCapacity = oldCapacity + (oldCapacity >> 1);，默认就是扩容1.5倍！如果扩容后小于我们所需要的最小容量那么直接就用我们的最小容量，下面同时还进行了一些边界处理。最后调用我们的Arrays.copyOf进行对原来的操作数组进行复制到扩容后的新数组！

hugeCapacity方法

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

至于为什么最大数组长度要设为为Integer.MAX_VALUE - 8，在后面面试题分析会介绍！

角标添加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++;
    }

首先进行我们调用了rangeCheckForAdd(index);进行了角标检查，防止出现了越界等操作！如果就是调用了我们上面一样的要不要尝试容量加1，也就是判断容量是否足够！然后直接就进行了数组的复制操作，直接复制大小为角标加1的数据部分，然后再进行数组的添加元素和实际大小加1！

System.arraycopy（...）底层是native修饰的方法，也就是调用我们的C++函数来进行复制的！

移除方法

其实ArrayList的重要点也就是我们的扩容机制，其他的一些方法，但是可以通过阅读源码可以轻松理解的。移除方法可以通过角标和元素来移除

通过角标

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

进行的操作有：

调用rangeCheck边界检查
获取要删除的元素，用于返回
如果角标后面还有元素，对后面的元素进行复制，也就是后面的元素都向前移以为
数组实际大小-1，调用GC

通过元素

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

这个方法看起来很简单，就是遍历，如果找到与我们要删除的元素相等的话，调用fastRemove方法，然后返回true；如果遍历后没有找到要删除的元素的话，那么就返回false，删除失败！所以我们下面具体看一下fastRemove方法。

    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
    }

这个方法就是上面的remove的阉割版，实现的功能都一样！

设置方法

检查角标，替换旧的元素，并返回旧的元素。

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

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

查询方法

检查角标，如果没有越界就返回该值。

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

面试题分析

这里选了比较常见的三道面试题，通过我们上面的源码都可以轻松的分析了！

1、ArrayList扩容机制是怎么样的？详细说一下。

我们在上面分析了，首先是进行判断一下是否需要容量加1操作，防止数组越界，定义我们所需最少的容量大小！然后就是再判断是否需要扩容。如果需要扩容的话，就会增加老数组的1.5倍，如果增加后大小还是小于我们的所需要的最小容量，那么扩容的大小就会改为我们的所需的最小容量大小！如果超过ArrayList允许的最大长度Integer.MAX_VALUE(2^31-1)，那么新数组长度为Integer.MAX_VALUE，否则为Integer.MAX_VALUE - 8。（为什么需要进行-8呢？是因为对象标头大小是不能超过8个字节的，我们可以默认它就是8，所有留了这么一个8字节大小！具体的话可以看这里）

2、在索引中ArrayList的增加或者删除某个对象的运行过程效率很低吗？解释一下为什么？

效率是很低，因为我们也看到了，无论是删除还是增加触发扩容机制的话，都是在底层调用System.copyOf()方法进行数组的复制或者移位操作。

增加元素时，我们要把要增加位置及以后的所有元素都往后移一位，先腾出一个空间，然后再进行添加。
删除某个元素时，我们也要把删除位置以后的元素全部元素往前挪一位，通过覆盖的方式来删除。

3、如何复制某个ArrayList到另一个ArrayList中去？

下面就是把某个ArrayList复制到另一个ArrayList中去的几种技术：

使用clone()方法，比如ArrayList newArray = oldArray.clone();
使用ArrayList构造方法，比如：ArrayList myObject = new ArrayList(myTempObject);
使用Collections的copy方法。

注意1和2是浅拷贝(shallow copy)。这里方法1是所有Object对象都有的；方法2的构造方法我们也介绍了；方法3的Collections是一个工具类，集成了很多对集合的操作方法！

Vector分析

vector也是继承AbstractList然后实现List接口的，跟ArrayList很像，和ArrayList里面很多属性和方法都一样。所以这里主要介绍它和ArrayList的区别。

区别1

Vector是线程安全的，ArrayList是线程不安全的！

Vector是如何实现线程安全的呢？它在所有容易被线程影响的方法都加了Synchronized关键字来修饰！所以我们可以把它看成是同步版的ArrayList。但也恰恰是因为进行了同步操作，所以它的效率是不如ArrayList的。

当然，如果我想要同步操作的话，不是一定要用Vector的，Colletions也提供了可以将ArrayList变成线程同步的方法

 List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());

但其实去看源码也可以发现，这个方法同样是给list的方法加一层synchronized。

区别2

触发扩容机制的时候，我们的ArrayList是1.5倍，而我们的Vector确是两倍！

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以看到我们的4,5行代码，如果设置自动增长的长度就加上这个长度，如果没有的话，默认就是加了原来的容量，也就是扩大为原来的两倍！

总结

简单总结一下，Vector与ArrayList大径相似，最大的区别就是线程安全的区别了，记住这个就好了，反正现在也很少去用Vector了。同时，我们需要注意的，不管是Vector还是ArrayList，有时候是挺浪费内存的。因为有时候如果我有了5w容量了，但是我下面只会再用掉一个容量单位的话，我们的Vector会扩容到7w5，我们的Vector会扩容到10w，这内存浪费的有点多，所以有时候初始的时候就设置大小容量！

LinkedList分析

LinkedList实现了List接口，我们还需要关注的是它还实现了一个比较重要的接口就是Deque。所以我们的LinekdList是可以像操作队列和栈一样来操作。

LinkedList底层是一个双向链表，我们同样像分析ArrayList那样对属性和构造方法还有常用方法进行分析，来了解一下它的特性！

属性

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

三个属性，我们的链表长度，头结点，尾节点。

构造方法

我们有两个构造方法，一个空构造方法public LinkedList() {}，因为我们是链表，所以是不需要指定长度和容量的。还有一个就是有参构造，可以传入一个Collection类型的子集合，后续会调用方法addAll进行链表的初始化。

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

addAll会再调用另一个可以传入链表长度的重载方法。然后代码主要是进行这些操作：

检查边界，只能在大于等于0和小于等于链表长度的范围才行
进行判断，如果要用来初始化的集合长度等于0，返回false
如果判断是否在尾结点插入，然后进行相关操作
对数组遍历进行结点的插入
链表的长度加上我们的数组长度，返回true。

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

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        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 += numNew;
        modCount++;
        return true;
    }

常用方法

LinkedList常用的方法太多了，很多都是链表的相关操作，可以看起来有点复杂，但是仔细去研读源码，也就很好理解。这里也就介绍一下增加删除吧

增加

增加操作的话，可以在头结点前面增加，也可以在我们的尾结点后面增加，默认的add方法是在尾结点后面增加。

add(E) 在尾结点后面插入，调用linkLast(e)方法
addLast(E)在尾结点后面插入，调用linkLast(e)方法
addFirst（E）在头结点前面插入，调用linkFirst(e)方法

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    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++;
    }

代码很好理解，具体操作解析的如下图：

删除

移除元素的话，有三个方法

remove(Object o)，移除在链表中的元素
removeLast()，移除链表最后一个元素
removeFirst()，移除链表第一个元素

remove方法

我们先来看看remove方法

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

首先是进行了元素的判空，然后进行了遍历，然后都调用了unlink方法后返回true；如果没有找到元素就返回false。

顺藤摸瓜来看看unlink方法

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

这个方法呢，很普通，就是进行双向链表的正常删除操作，没什么好解释的，如果不懂的话，可以看看下面这张图。如果看了图还是不能理解的话，需要去补充链表的知识了！

removeFirst()与removeLast()

这两个方法，一个调用了unlinkFirst(Node<E> f)，一个调用了unlinkLast(Node<E> l)，也都是双向链表的正常操作，没有什么特别难的地方！

LinkedList小总结

LinkedList的方法非常多，基本都是一些链表的操作。同时它也是线程不安全的，我们同样可以用Collections帮助类对其进行转换成线程安全的。

        LinkedList<Integer> linkedList = (LinkedList<Integer>) Collections.synchronizedList(new LinkedList<Integer>());

面试题分析

这里我只找了一题，因为很多基本很多都只问这题。其他的话，通过上面的学习也可以说道说道！

请说明ArrayList和LinkedList的区别？

ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

（这里再补充一下）

ArrayList增删慢不是绝对的(在数量大的情况下，已测试)：

如果增加元素一直是使用add()(增加到末尾)的话，那是ArrayList要快
一直删除末尾的元素也是ArrayList要快【不用复制移动位置】
至于如果删除的是中间的位置的话，还是ArrayList要快！

但一般来说：增删多还是用LinkedList，因为上面的情况是极端的~

参考资料

Core Java

公众号《Java 3y》文章

知乎专栏《Java那些事儿》

实现List接口的重要集合源码分析

ArrayList分析

默认属性

构造方法

第一个构造方法

第二个构造方法

第三个构造方法

常用方法分析

增加方法

移除方法

设置方法

查询方法

面试题分析

Vector分析

区别1

区别2

总结

LinkedList分析

属性

构造方法

常用方法

增加

删除

LinkedList小总结

面试题分析

参考资料

猜你喜欢

热点阅读