什么是List

在 List 中，⽤户可以精确控制列表中每个元素的插⼊位置，另外⽤户可以通过整数索引（列表中的位 置）访问元素，并搜索列表中的元素。 与 Set 不同，List 通常允许重复的元素。 另外 List 是有序 集合⽽ Set 是⽆序集合。

ArrayList

介绍

ArrayList是一个Java日常开发中经常使用到的类，底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

在我们学数据结构的时候就知道了线性表的顺序存储，插入删除元素的时间复杂度为O(n）,求表长以及增加元素，取第 i 元素的时间复杂度为O(1）

• 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
• 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
• 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
• 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。
• 线程不安全，所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

扩容机制

解释

ArrayList在添加数据的时候会判断是否大于容量，如果大于了当前数组的容量，则进行扩容，每次扩容的容量为当前容量的1.5倍。如果每次增加一个，这个效率肯定不高的。

数组容量不能超过Integer.MAX_VALUE-8;如果超过则会OOM。因为对象头里面会存储_length字段，而这个字段长度为8，所以要减去8；

源码

    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }

关于快速删除

在ArrayList源码中可以看到有个fastRemove方法，这个方法为甚么叫快速删除呢，是因为直接调用了System.arraycopy方法，这样就不用考虑数组的边界问题而且还不用有返回值。

  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
    }

关于内部类中的迭代器

• Itr 其中的Itr是实现了Iterator接口，同时重写了里面的hasNext()， next()， remove() 等方法；
• ListItr 继承 Itr，实现了ListIterator接口，同时重写了hasPrevious()， nextIndex()， previousIndex()， previous()， set(E e)， add(E e) 等方法。

可以看出了 Iterator和ListIterator的区别: ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的。

Vector

介绍

Vector相当于是线程安全的ArrayList，实现线程安全的方法也就是在每个修改数组的方法上面加上了一个Synchronized方法，所以效率很低，现在一般使用Collections.syschronizedList方法来创建线程安全的集合。

扩容机制

解释

与ArrayList有所不同，Vector设置了一个自己的扩容数量capacityIncrement，通过设置这个的大小，可以默认让Vector每次扩容这么多，如果不设置，则就以默认的2倍进行扩容。

源码

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

动手实现ArrayList

/**
 * @author unclezs.com
 * @date 2019.06.03 14:40
 */
public class MyList<T> implements Serializable {
    /**
     * 元素
     */
    Object[] elementData = {};
    private static final Object[] EMPTY_ELEMENT_DATA = {};
    /**
     * 容量
     */
    private static int capacity = 10;
    /**
     * 当前元素个数
     */
    private int size = 0;

    /**
     * 泛型转化
     *
     * @param capacity 容量
     */
    public MyList(int capacity) {
        if (capacity > 0) {
            elementData = new Object[capacity];
        } else if (capacity == 0) {
            elementData = EMPTY_ELEMENT_DATA;
        } else {
            throw new IllegalArgumentException("参数错误");
        }
    }

    public MyList() {
        this(capacity);
    }

    /**
     * 当前容量
     *
     * @return size
     */
    public int size() {
        return size;
    }

    /**
     * 检测是否满了，满了则扩容
     */
    private void checkAndExpansion() {
        if (size + 1 > capacity) {
            this.elementData = Arrays.copyOf(elementData, size * 2);
        }
    }

    /**
     * 泛型转化
     *
     * @param index 索引
     * @return 泛型对象
     */
    @SuppressWarnings("unchecked")
    private T elementData(int index) {
        return (T) elementData[index];
    }

    /**
     * 指定下标设置值
     *
     * @param index 索引
     * @param o     元素
     */
    public void set(int index, T o) {
        checkAndExpansion();
        elementData[index] = o;
    }

    /**
     * 在尾部添加一个元素
     *
     * @param o 元素
     */
    public void add(T o) {
        checkAndExpansion();
        elementData[size++] = o;
    }

    /**
     * 移除一个元素
     *
     * @param index 索引
     */
    public void remove(int index) {
        System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
        size--;
    }

    /**
     * 根据下标查询
     *
     * @param index /
     * @return /
     */
    public T get(int index) {
        checkAndExpansion();
        return elementData(index);
    }

    /**
     * 清空集合
     */
    public void clear() {
        this.size = 0;
        elementData = new Object[capacity];
    }

    /**
     * 添加一个集合
     *
     * @param myList /
     */
    public void addAll(MyList<T> myList) {
        if (myList == null || myList.size() == 0) {
            return;
        }
        for (int i = 0; i < myList.size(); i++) {
            this.add(myList.get(i));
        }
    }

    /**
     * 查看是否有这个元素元素
     *
     * @param e 元素
     * @return /
     */
    public boolean isExist(T e) {
        for (Object elementDatum : elementData) {
            if (e.equals(elementDatum)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找元素下标
     *
     * @param t 元素
     * @return /
     */
    public int indexOf(T t) {
        if (t == null) {
            return -1;
        }
        for (int i = 0; i < elementData.length; i++) {
            if (elementData[i] != null && t.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        return Arrays.toString(elementData);
    }
}