1、ArrayList、LinkedList、Vector异同点

• 存储的元素是有序的、可重复的。
• 底层数据结构： Arraylist 底层使用的是 Object 数组；Vector底层使用的也是Object数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；Vector中的方法都被synchronized关键字修饰，故线程安全，但性能较低。
• 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入；Vector类似ArrayList。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList、vector 支持。快速随机访问就是通过元素的index快速获取元素对象(对应于get(int index)方法)。
• 内存空间占用： ArrayList、vector 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱指针以及数据）。

2、核心源码解析

2.1、ArrayList核心源码解析

2.1.1、ArrayList数据结构

Object数组。

 /**
     * 默认Object[]初始大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空数组实例，当new ArrayList(int initialCapacity),initialCapacity为0时，把该实例赋值给elementData
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 默认数组实例，当new ArrayList()时，把该实例赋值给elementData
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 实际存储数据的数组结构
     */
    transient Object[] elementData; // non-private to simplify nested **加粗样式**class access

    /**
     * 数组中元素个数
     */
    private int size;

有参构造：当initialCapacity为0，会把定义的EMPTY_ELEMENTDATA实例赋值给elementData，大于0时，this.elementData = new Object[initialCapacity]。
无参构造：默认会把定义的DEFAULTCAPACITY_EMPTY_ELEMENTDATA实例赋值给elementData。

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //当initialCapacity为0，会把定义的EMPTY_ELEMENTDATA实例赋值给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2.1.2、ArrayList的add(E e)方法

public boolean add(E e) {
        //数组扩容方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //往数组添加元素
        elementData[size++] = e;
        return true;
    }

数组扩容方法：ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {
        //calculateCapacity方法：
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

计算当前数组需要最小大小。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是刚new ArrayList()创建的实例，则此时数组默认大小是DEFAULT_CAPACITY：10，否则是当前元素个数+1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

判断当前数组是否需要扩容。

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

        // 执行数组扩容条件
        //minCapacity：当前数组最小的大小
        //elementData.length：当前数组实际大小
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

数组扩容方法:每次扩容后数组大小是原大小的1.5倍。

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

2.1.3、ArrayList的get(int index)方法

获取指定下标的元素。

public E get(int index) {
        //检查下标index是否越界
        rangeCheck(index);
        //直接返回指定下标元素
        return elementData(index);
    }

检查下标index是否越界，越界会抛出IndexOutOfBoundsException，即索引越界异常。

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

2.1.4、ArrayList的remove(int index)方法

ArrayList删除元素需要移动大量元素，这就是ArrayList增删效率低的原因。

public E remove(int index) {
        //检查下标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;
    }

2.1.5、ArrayList的set(int index, E element)方法

public E set(int index, E element) {
        //检查下标index是否越界
        rangeCheck(index);
        //暂存需要删除的元素，最后需要返回
        E oldValue = elementData(index);
        //给指定下标赋值
        elementData[index] = element;
        return oldValue;
    }

2.2、LinkedList核心源码解析

2.2.1、数据结构

双向链表。

//元素个数
transient int size = 0;

    /**
     * 指向首节点的指针
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * 指向最后一个节点的指针
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkedList除了实现List接口，还实现了Deque双端队列接口，因此LinkedList提供了操作队列相关方法，例如：poll()、pollFirst()、pollLast()、peek()、peekFirst()、peekLast()等；也提供了对栈的相关操作，例如：pop()、push()等方法。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.2.2、LinkedList的add(E e)方法

新增元素。

public boolean add(E e) {
        //在链表尾添加一个节点
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        //创建一个l指针指向最后一个元素
        final Node<E> l = last;
        //新创建一个节点，并把该节点的前驱指针指向l指向的节点，即尾部节点
        final Node<E> newNode = new Node<>(l, e, null);
        //last指针指向新节点
        last = newNode;
        if (l == null)
            //l指针为空，代表链表为空链表
            first = newNode;
        else
            //非空，把尾节点的next指针指向新的节点
            l.next = newNode;
         //元素个数加1
        size++;
        modCount++;
    }

新创建的节点结构。

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

2.2.3、LinkedList的get(int index)方法

获取指定小标的元素。

public E get(int index) {
        //检查下标是否越界
        checkElementIndex(index);
        //遍历链表获取指定下标节点的元素
        return node(index).item;
    }

遍历链表方法：获取指定下标的节点。此处做了优化，不是遍历整个链表，而是判断指定下标是在链表的前半部分还是后半部分，最终最多只会遍历一半链表。

Node<E> node(int index) {
        // assert isElementIndex(index);
        //size >> 1:元素个数/2
        if (index < (size >> 1)) {
            Node<E> x = first;
            //从链表头部开始遍历
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            //从链表尾部开始遍历
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

2.2.4、LinkedList的remove(int index)方法

node()方法如上，遍历链表，找到需要删除的节点。

public E remove(int index) {
        //检查下标是否越界
        checkElementIndex(index);
        return unlink(node(index));
    }

unlink():删除指定下标的节点，x指向被删除的节点。

E unlink(Node<E> x) {
        // assert x != null;
        //暂存被删除的元素，最后返回
        final E element = x.item;
        //next指针指向被删除节点的下一个节点
        final Node<E> next = x.next;
        //prev指针指向被删除节点的上一个节点
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            //prev指向的节点的后继指针指向next指向的节点，即被删除元素的下一个节点
            prev.next = next;
            //将被删除节点的前驱指针赋值null
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            //next指向的节点的前驱指针指向prev指向的节点，即被删除元素的上一个节点
            next.prev = prev;
            //将被删除节点的后继指针赋值null
            x.next = null;
        }

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

2.2.5、LinkedList的set(int index, E element)方法

给指定下标元素重新赋值。

public E set(int index, E element) {
        //检查下标是否越界
        checkElementIndex(index);
        //遍历链表获取指定下标的节点
        Node<E> x = node(index);
        E oldVal = x.item;
        //新元素覆盖旧元素
        x.item = element;
        return oldVal;
    }

2.2.6、LinkedList的poll()方法

获取并删除列表的头(第一个元素)。与remove()相似，区别是remove()方法中如果链表为空，则会抛出NoSuchElementException异常。

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

remove()方法删除逻辑。

public E remove() {
        return removeFirst();
    }
    
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

2.2.7、LinkedList的peek()方法

获取但不删除列表的头(第一个元素)。

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

2.3、Vector核心源码解析

Vector底层数据结构与ArrayList一样，功能也类似，但比ArrayList功能更丰富。并且可以手动指定扩容大小，capacityIncrement指定。

/**
     * vector底层数据结构
     */
 protected Object[] elementData;

    /**
     * 元素个数
     */
    protected int elementCount;

    /**
     * 扩容大小
     *
     * @serial
     */
    protected int capacityIncrement;

/**
     * initialCapacity：初始化数组大小
     *capacityIncrement:指定每次扩容大小
     * @serial
     */
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    /**
     * 指定初始化数组大小，默认每次扩容为原来数组大小的一倍
     *         is negative
     */
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    /**
     * 默认数组大小为10
     */
    public Vector() {
        this(10);
    }

Vector中Object数组扩容方法，当capacityIncrement不大于0时，每次扩容原来数组的一倍。

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

3、双向链表和双向循环链表

3.1、双向链表

双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
[图片上传失败...(image-4f84c8-1636522570847)]

3.2、双向循环链表

双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

image