ArrayList和LinkerList区别和ArrayList简单解析

ArrayList和LinkerList区别和ArrayList简单解析 1，数组和集得区别？

（1）创建数组要初始化长度，且长度不可改变
     集合长度可变
（2）数组数据类型可以是基本数据类型，也可以是引用数据类型
     集合只能是引用数据类型

2，list和set的区别？

（1）list能保证插入数据顺序排序，数据可重复
     set不保证插入数据顺序排序，数据不可重复
（2）list可以通过索引获取数据，set不能通过索引获取数据

3，list主要实现类：arraylist，linkedlist，vectory

（1）ArrayList：
     底层是Object类型的动态数组在内存中需要一片连续得空间，线程不安全(线程安全就是多线程访问时，采用了加锁机制)，效率高，数据可重复,可以为null
     查询快：因为是数组具有下标索引
     增删慢：添加和删除要移动下标位置之后的索引，如果元素插在数组末尾也很快，需要扩容时都慢
     空间：需要连续空间，并且扩容是1.5倍有可能一篇空间没用到
（2）linkedList:
     底层是双向链表（双向链表有俩个指针分别指向节点前后，第一个节点指向前为null，最后一个节点指向后为null）不需要连续空间，线程不安全，效率高，可以存储重复元素，没有长度的概念，不存在扩容问题，
     查询慢：没有索引，迭代链表查询，但是采用了二分折半查询。只需要遍历一半链表，但还是慢
     增删快：只需要移动指针，默认添加到尾部
     空间：每个节点都要存储指向前一个和后一个节点的指针
（3）Vectory：底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素

ArrayList源码解析add：jdk1.8

（1）创建指定大小容量得集合，如果是0则创建一个object类型得空数组，否则参数不合法
ArrayList代码中得3种构造方法：
    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);
        }
    }
（2）创建一个object类型得空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
（3）add:默认添加到尾部，所以很快，
        带有索引的插入，先判断所引是否越界，无论是否扩容都要拷贝数组，在拷贝数组时会对索引进行+1
        数组拷贝方法：System.arraycopy()，返回的是新对象
        remove也一样，nt numMoved = size - index - 1; System.arraycopy()移动索引，复制数组
    
    public boolean add(E e) {
        //判断数组是否需要初始化和数组是否需要扩容，同时size数组长度进行了+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将元素插在索引的最后一位+1，所以保证了arraylist中元素插入有序
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        //elementData是存放元素的对象数组
        //如果数组是空的，就初始化长度为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //minCapacity=初始化长度19，或者数组中的元素长度+1
        ensureExplicitCapacity(minCapacity);
   }
   
   private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    //数组的元素长度+1，大于原数组长度 ，就需要进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
   }
    //开始扩容
    private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //扩容后=扩容前+（扩容前/2，扩容1.5倍(位移一位除以2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //若果扩容后的长度 - 数组中元素长度+1 小于0，则数组长度为原始数组长度+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:
    //创建新长度newCapacity的数组，进行拷贝扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    总结add：
          1，ArrayList添加元素，判断数组是否为空，
             如果为空初始化数组长度为10,
             如果数组不为空，数组中元素长度为原数组中元素长度+1
          2，变化后的数组元素长度减去原数组长度大于0，进行扩容
          3，开始扩容：扩容规则:扩容后=扩容前+（扩容前>>2，扩容1.5倍(位移一位除以2)
          4, 扩容后的长度和变化后的数组长度，谁大谁就是最终的数组长度
          5，扩容：创建新长度的数组，拷贝原数组内容
    问题：ArrayList插入数据如何保证有序的？
            添加元素将元素插在索引的最后一位+1，所以保证了arraylist中元素插入有序，即使是带索引参数插入，也会移动索引排序
          ArrayList如何扩容？
          1，如果数组中元素长度+1大于了数组长度，就需要扩容
          2，扩容规则扩容规则:扩容后=扩容前+（扩容前>>2
          3，扩容规则后的长度如果小于数组元素长度+1，则扩容为原数组元素长度+1
          4，扩容相当于自己拷贝自己，实现扩容
          ArrayList增删查效率？
          1，查询：直接根据索引查询，快
          2，增加：不带参数的增加，默认增加到尾部，快，但是需要扩容时。慢
          3，带索引的增加和删除，拷贝数组时需要移动索引后下标，慢，当需要扩容时更慢
          ArratList为啥线程不安全？如何解决
          当俩个线程同时添加数据的时候，elementData=0的数据有可能会被覆盖
          使用synchronized关键字，Collections.synchronizedList()同步就会有锁机制，效率低