Java-08：Vector、ArrayList、LinkedList有何区别？-蒲公英云

三个集合都是我们常用的数据集合，在看它们之间的区别前，我们先来看看它们的继承结构。

1、继承结构图

在这里插入图片描述

Collection接口是层次结构中的根接口，构成Collection的单元称为元素。Collection接口提供了添加元素，删除元素，管理数据的方法。

List接口表示这是一个元素有序，可以重复，可以为null的集合，那它又是凭借什么实现有序的。List数据结构在内存中会开辟一块连续的空间，然后将内存地址与索引对应。

Queue接口在Collection基础上添加操作队列方法，Deque接口是一个双向队列，同时也添加相应的方法。

2、读写效率

我们可以看出ArrayList和Vector是一个有序的数组，底层数据结构为数组；LinkedList是一个有序的双向链表，底层的数据为链表。

那既然是数组和链表，在数据的插入、删除，就会有自己的优势和劣势。

数组在中间插入数据时，会将插入位置之后的数据向后移动，同理删除中间数据，会将后面的数据前移，不过在访问数据时，可以依据随机访问的特性能很高效地访问；
链表在插入或删除数据时，只需要修改next的指向就能很高效插入数据，不过在查询数据时，只能从头部或者尾部开始逐步遍历，直到遍历完链表或找到。

我们就要根据具体场景来选择数据结构，如果添加/删除数据多，查询少，链表再适合不过；如果查询多，添加/删除数据少，那就选择数组。

Vector和ArrayList最根本的区别是Vector是一个线程安全的集合，它的所有方法上都有着ssynchronized关键字，不过保证线程安全，避免不了额外的性能消耗，在不是多并发的场景下，ArrayList合适的多。

看完读写效率方面的差距，我们再来看看，再插入数据时，集合的具体表现。

3、读写机制

我们需要关注的点有存放数据的结构，初始容量，如何扩容，添加数据时的操作

3.1 ArrayList

存放数据的结构？

transient Object[] elementData;

在ArrayList中，我们能很容易发现这个存放数据的结构elementData，当时为啥它需要transient关键字修饰呢。

transient关键字只能修饰成员变量，在对象进行序列化时，由该关键字修饰的成员变量不会序列化。但是elementData不是存放数据的嘛，不能序列化，我如何将它持久化或者传输呢。

elementData被transient关键字修饰的关键所在：例如Object[]长度为20，但是只存放了10个数据，还会有10个空位，Java不想让这10个空位也序列化，一起传输过去。所以ArrayList中提供了writeObject和readObject方法来序列化和反序列化。

数组的初始容量？

那我们就来看下它的构造函数

// 没有指定大小
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    // 传入指定大小
    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);
        }
    }
    private static final Object[] EMPTY_ELEMENTDATA = { };

第一种情况：空参构造器，elementData被赋值空数组，数组的长度为0
第二种情况：传入指定大小，如果initialCapacity为0，则被赋值空数组；如果initialCapacity>0，则创建一个initialCapacity大小的数组。

那EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA又是什么情况呢？后面揭晓！

数组怎么进行扩容？

private static final int DEFAULT_CAPACITY = 10;
    // mincapacity = size + 1传入
    private void ensureCapacityInternal(int minCapacity) { 
        // 如果是由空参构造器构造出来ArrayList实例，
        // 从DEFAULT_CAPACITY和minCapacity选择一个大的
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) { 
        // 集合的总操作+1
        modCount++;
        // 如何数值正确，继续执行
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) { 
        // 
        int oldCapacity = elementData.length;
        // 新容量为1.5倍的原始数值
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 将minCapacity与newCapacity进行比较，同时注意容量数值的边界
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 复制数组到新数组
        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;
    }

我们来总结下，ArrayList如何扩容？

将size+1作为最小容量闯入扩容方法，如果是空参构造器生成的实例，则从DEFAULT_CAPACITY和size+1中选择一个大的数
生成一个newCapacity，大小为1.5倍的旧容量，将newCapacity与minCapacity进行比较取较大值
如果比较出来的数值大于Integer.MAX_VALUE - 8，那数组的新容量为Integer.MAX_VALUE
赋值旧数组的数据到新数组

add操作？

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

知道扩容方法的原理后，add方法就很明显了。

3.2 LinkedList

存放数据的结构？

链表嘛，还是双向的，我们就很容易能脑补到具体的情景

先来看下节点Node：

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中两个引用，一个指向链表头，一个指向链表结尾

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

如何添加数据？

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