java集合一List
一 集合适用于存储的容器，封装不同类型的数据，实现自动增长（相较于数组）
https://www.cnblogs.com/yangliguo/p/7476788.html
即单列集合Collection和双列结合Map
除了 map 系列的集合，即左边集合都实现了 Iterator 接口，这是一个用于遍历集合中元素的接口，主要hashNext(),next(),remove()三种方法
List接口的实现类中最经常使用最重要的就是这三个：ArrayList、Vector、LinkedList。
ArrayList实现
1 ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。
2 底层使用数组实现
3 该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5 倍，这种操作的代价很高。
4 采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为 的风险
5 remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC
ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。
get() 通过寻找底层数组的下标遍历，所以相对其他容器比较快
add(int index ) add（Element e） 添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查,增长比例为1.5倍（gorw()方法，通过验证这个minCapacity的大小确保用最小的容量存储list中所有的元素，这里面最重要的一个方法是Arrays.copyOf()，elementData的真正作为数组缓存的实现就在这里，这个newCapacity表示扩展的ArrayList，如果超出10的话，会执行这个（oldCapacity>>1）位移运算，左移一位表示增加一半，就是说newCapacity最终的容量是10+10*0.5，这里就是ArrayList的动态扩容机制，每次扩容都是1.5倍. ） 数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张, 在末尾添加元素
remove() 这个方法来看remove()方法的源码
rangeCheck()是检查这个索引是否超出集合的size
其中numMoved是要被数组复制的长度，为什么要用这个System.arraycopy()方法呢
原因是ArrayList的底层数据结构是线性表结构，删除集合中的一个元素（除删除最后一位），这个元素后面的所有元素都要向前挪一位，采用这个方法巧妙的将这个特性实现。
总结
- 非线程安全
- 基于对象数组
- get(int index)不需要遍历数组，速度快；
- iterator()方法中调用了get(int index)，所以速度也快
- set(int index, E e)不需要遍历数组，速度快
- add方法需要考虑扩容与数组复制问题，速度慢
- remove(Object o)需要遍历数组，并复制数组元素，速度慢
- remove(int index)不需要遍历数组，需要复制数组元素，但不常用
- contain(E)需要遍历数组
http://zhangshixi.iteye.com/blog/674856l
https://www.cnblogs.com/leesf456/p/5308358.html
LinkedList实现
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的
1 LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
2 底层的数据结构是基于双向链表的，该数据结构我们称为节点
3 双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点， next是 该节点的下一个节点，item是该节点所包含的值。
4 它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到
add(E) 在添加元素方面LinkedList不需要考虑数组扩容和数组复制，只需要新建一个对象，但是需要修改前后两个对象的属性。
get() 查找节点
- 链表节点的按索引查找，需要遍历链表；而数组不需要。
- header节点既是头节点也是尾节点
- 双向链表的查找，先去判断索引值index是否小于size/2，若小于，从header节点开始，从前往后找；若大于等于，从header节点开始，从后往前找
- size>>1，右移一位等于除以2；左移一位等于乘以2
remove（）
- remove(entry(index))
- remove(Object o)需要遍历链表，remove(int index)也需要
- 相较于ArrayList 跳整要删除节点的前后节点的指向即pre next
- 将删除的节点置空
总结
- LinkedList基于环形双向链表方式实现，无容量的限制
- 添加元素时不用扩容（直接创建新节点，调整插入节点的前后节点的指针属性的指向即可）
- 线程不安全
- get(int index)：需要遍历链表
- remove(Object o)需要遍历链表
- remove(int index)需要遍历链表
- contains(E)需要遍历链表
https://www.cnblogs.com/java-zhao/p/5105575.html
http://www.cnblogs.com/ITtangtang/p/3948610.html
https://www.cnblogs.com/leesf456/p/5308843.html
ArrayList实现了随机访问的接口，LinkedList实现了Quene的接口。
ArrayList是基于数据实现的list，而LinkedList是基于链表实现的list。所以，ArrayList拥有着数组的特性，LinkedList拥有着链表的特性。
- 优缺点
ArrayList
优点：适合随机读取的时候，读取速度快，可以一步get(index)。
缺点：添加值很慢——一方面，添加数据在array中间的时候，需要移动后面的数；另一方面，当长度大于初始长度的时候，每添加一个数，都会需要扩容。
LinkedList：双向链表
优点：添加值很快——添加在list中间也只需要更改指针；长度不固定。
实现栈和队列方面，LinkedList要优于ArrayList。
- 其它
LinkedList的remove(int)和remove(Object)的方法的时间复杂度都是O(n),不是O(1).因为会有一个查找的过程。
LinkedList的remove(int)要优于remove(Object)，因为remove(int)在查找的时候，会从链表的中间查找，如果int比中间小，找前半部分，否则找后半部分（类似二分查找）。
ArrayList的增删比LinkedList的开销更大，因为除了有查找的时间复杂度外，还有增删的移动过程。
关于遍历效率
List底层储存都是使用数组来进行存储的，ArrayList是直接通过数组来进行存储，而LinkedList则是使用数组模拟指针，来实现链表的方式，因此从这里就可以总结出，ArrayList在使用下标的方式循环遍历的时候性能最好，通过下标可以直接取数据，速度最快。而LinkedList因为有一层指针，无法直接取到对应的下标，因此在使用下标遍历时就需要计算对应的下面是哪个元素，从指针的头一步一步的走，所以效率就很低。想到指针就会联想到迭代器，迭代器可以指向下一个元素，而迭代器就是使用指针来实现的，因此LinkedList在使用迭代器遍历时会效率最高，迭代器直接通过LinkedList的指针进行遍历，ArrayList在使用迭代器时，因为要通过ArrayList先生成指针，因此效率就会低于下标方式，而for-each又是在迭代器基础上又进行了封装，因此效率会更低一点，但是会很接近迭代器。
Vector相较于ArrayList
Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。
当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间。