1 集合框架介绍

• 所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口或实现类。
• 集合接口：6个接口（短虚线表示），表示不同集合类型，是集合框架的基础。
• 抽象类：5个抽象类（长虚线表示），对集合接口的部分实现。可扩展为自定义集合类。
• 实现类：8个实现类（实线表示），对接口的具体实现。
• Collection 接口是一组允许重复的对象。
• Set 接口继承 Collection，集合元素不重复。
• List 接口继承 Collection，允许重复，维护元素插入顺序。
• Map接口是键－值对象，与Collection接口没有什么关系。
• Set、List和Map可以看做集合的三大类：

1. List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。
2. Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）。
   Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。

2 纯手写List框架

List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

3 ArrayList实现

3.1 Arraylist底层基于数组实现

3.2 Arraylist底层默认数组初始化大小为10个object数组

3.3 添加元素后大于当前数组的长度，则进行扩容,将数组的长度增加原来数组的一半。

• add方法
  
• 判断实际存放的容量是否大于elementData
  
• 判断是否需要扩容
  
• 扩容实现
  

3.4 手写Arraylist底层框架

3.4.1 自定List接口

public interface ExtList<E> {

    int size();

    boolean add(E e);

    void add(int index, E e);

    E get(int index);

    E remove(int index);

    boolean remove(E e);
}

3.4.2 实现List接口

public class ExtArrayList<E> implements ExtList<E> {

    private static final int DEFAULT_CAPACITY = 10;

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

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;

    /**
     * 实际容量大小
     */
    private int size;

    public ExtArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ExtArrayList(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 int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    @Override
    public boolean add(E e) {
        // 1.判断实际存放的容量是否大于elementData
        ensureCapacityInternal(size + 1);
        // 2.使用下标进行赋值
        elementData[size++] = e;
        return true;
    }

    @Override
    public void add(int index, E e) {
        // 1.判断实际存放的容量是否大于elementData
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 2.使用下标进行赋值
        elementData[index] = e;
        size++;
    }


    /**
     * 判断实际存放的容量是否大于elementData
     *
     * @param minCapacity 最小为size+1
     * @return void
     * @throws
     * @author zhouxinlei
     * @date 2019-12-24 14:43:09
     */
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }


    private void grow(int minCapacity) {

        //原数组容量大小
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //最小扩容容量
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        } else if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    @Override
    public E get(int index) {
        //判断数组是否越界
        rangeCheck(index);
        return elementData(index);
    }

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

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

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

    private void fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        }
        elementData[--size] = null;
    }

    @Override
    public E remove(int index) {
        E e = get(index);
        int numMoved = elementData.length - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return e;
    }

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

    @Override
    public int size() {
        return this.size;
    }
}

3 LinkList实现

LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比ArrayList差。

3.1 LinkedList数据结构原理

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

3.2 数组和链表结构对比

• 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组。
  
• 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储 数据元素 的　数据域，另一个是存储下一个结点地址的 指针。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
  

3.3 内存存储区别

• 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
• 链表从堆中分配空间, 自由度大但申请管理比较麻烦。

3.4 逻辑结构区别

• 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。　
• 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）　

3.5 总结

• 存取方式上，数组可以顺序存取或者随机存取，而链表只能顺序存取；　
• 存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；　
• 存储空间上，链表由于带有指针域，存储密度不如数组大；　
• 按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；　
• 按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；　
• 插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；　
• 空间分配方面： 数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败； 链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；

3.6 手写LinkList代码实现