[数据结构与算法]List集合介绍、ArrayList，Vector，LinkedList 源码简要剖析

1. List接口

1.1. 基本介绍：

List接口是继承Collection接口，所以Collection集合中有的方法，List集合也继承过来。

1. List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复；
2. List集合中每个元素都有其对应的顺序索引，即支持索引；
3. List容器中的元素都对应一个整数型序号记载其在容器中的位置，可以根据序号存取容器的元素；

1.2. List集合常用方法

1.void add(E element)
向列表的尾部追加指定的元素
2. void add(int index,E element)
在列表的指定位置插入指定元素。
3.void clear()
从列表中移除所有元素
4.boolean equals(Object c)
比较指定的对象与列表是否相等
5.boolean isEmpty()
判断集合是否为空 如果为空 则返回true,否则返回false
6.int lastIndexOf(Object o)
返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回-1
7.remove(int index)
移除列表中指定位置的元素
8.get (int i)
获取给定位置元素
9.set (int i , E element)
用一个新元素替换给定元素，并返回原来那个元素

2.ArrayList底层结构和源码分析

ArrayList底层操作机制源码分析

1. ArrayList中维护了一个Object类型的数组elementData transient Object[] elementData transient 表示瞬间的，短暂的，表示该属性不会被序列化
2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0， 第一次添加，则扩容elementData为10，如需再次扩容，则扩容为element为1.5倍；
3. 如果使用的是指定大小的有参构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容为elementData为1.5倍

代码示例：

在debug处，step into ；

IDEA中，ctrl+鼠标左键 进入 DEFAULTCAPACITY_EMPTY_ELEMENTDATA源代码，初始化为一个空数组

step out ，

java 在jdk1.5 之后引入的 自动装箱和自动拆箱；
IntegerCache.high和IntegerCache.low默认分别为 127 和-128
如果传入的值是在-128~127之间就会建立Integer实例并且把实例放入缓存中，当再传入的值是缓存中存在的,就会把缓存中的实例返回，如果不在 -128~127之间就不会把 实例放入缓存中.直接返回一个实例。

先执行 list.add(), 先确定是否要扩容，然后再执行是否要赋值

step into，ensureCapacityInternal，

该方法确定 minCapacity,第一次扩容为 10

modcount用于记录修改次数，也防止有多个线程共同修改，会有异常抛出
elementData大小不够用，就会调用grow去扩容

通过扩容机制要扩容到多大
第一次newCapacity = 10 ；
第二次即以后，按照1.5倍扩容
扩容使用的是 Arrays.copyof()

最后，将值 0 ，存储进elementData 数组,后面若初始数组容量大于10，就是自动调用1.5倍扩容机制。

3.Vector底层结构和源码剖析

1. Vector类定义的说明

   public class Vector<E>
     extends AbstractList<E>
     implements List<E>,RandomAccess, Cloneable,Serializable 
     
   

2. Vector底层也是一个对象数组 protected Object[] elementData ;

3. Vector 是线程同步的，即线程安全的，Vector类的操作方法带有synchronized

4. 在开发中，需要线程安全时，考虑使用Vector

代码示例：
初始化定义一个 vector数组

Vector 数组的无参构造，默认先分配10个空间大小

ensureCapacityHelper验证数组容量大小

minCapacity=1， ·elementData空间大小为 10 暂时不需要扩容
Vector数组中，成功存入 一个元素；

4.LinkedList底层结构和源码剖析

LinkedList底层结构

1. LinkedList实现了双向链表和双端队列的特点；
2. 可以添加任意元素（元素可以重复），包括null ；
3. 线程不安全，没有实现同步 ；

LinkedList的底层操作机制

1. Linkedlist底层维护了一个双向链表；
2. LinkedList中维护了两个属性first 和 last分别指向 首节点和尾结点 ；
3. 每个节点（Node对象），里面有维护了prev，next， item三个属性，其中通过prev指向前一个，通过next指向后一个。最终实现双向链表；
4. 所以LinkedList的元素添加和删除，不是通过数组来完成的，相对来说效率较高

代码示例：

先初始化一个双向链表，这是linkedList的 属性 first = null ， last = null

将新加入的结点，放在双向链表的最后
当加入第一个结点时，first， last 指针都指向null；
当加入后续结点时，跟随源码一步一步推导，不难得出双向链表的增删原理；

5.Vector和ArrayList比较

6.ArrayList和LinkedList比较

如何选择ArrayList和LinkedList：

1. 如果我们改查较多，选择ArrayList；
2. 如果增删过多，选择LinkedList ；
3. 一般来说，在程序中，80%-90%都是查询，因此大部情况下会选择ArrayList
4. 在一个项目中，根据业务的灵活选择，也可能是这样，一个模块使用的是ArrayList，另一个模块使用的是LinkedList

寒假回来，首次写博客，第一次写java集合源码的笔记！
若有不当之处，欢迎大家积极指正，谢谢啦！！！