java零基础入门-高级特性篇(二) List集合
前面讲解过集合框架的大致结构，本章详细介绍List这个接口以及List接口的三个实现，ArrayList，LinkedList和Vector。
既然ArrayList和LinkedList实现了List接口，那么我们首先看看List接口中有哪些方法是常用的，再来看看这两个实现类是怎么实现这些常用方法的。
List接口常用方法
这里的E是泛型，这个东西后面再说，先可以理解为任何一个类型，比如学生类，车辆类等等。集合里面只能放引用类型，所以不要将基础类型放进集合。
add（E e）// 可以暂时理解成 add（Student stu），下面也一样，这个是添加方法，将元素添加进集合，默认往集合尾部添加。
add (int index,E element)，根据指定的位置添加元素，比如我现在List里面有2个元素了，下标是0，1，但是我要新增一个放在中间，就是add（1，stu）这样就可以将元素插入到指定位置。
get (int index) 根据指定位置获取元素，我要第二个元素，get（1）可以获取到。
set（int index，E element），set是替换，add可以理解成插队，你插进去了，后面的人往后移，而set就是请托排队，你来了，托就走了，一手交钱，一手交位，你代替了他的位置，托不会站在你后面继续排队。
remove(int index)，根据指定位置删除元素。
这是List接口里面常用的方法，下面来看看两个实现类如何来实现这些方法。
ArrayList：Array 是数组，ArrayList顾名思义，就是跟数组特性类似的List实现。
LinkedList：Linked 是链表，LinkedList顾名思义，就是有链表特性的List实现。
我们在给类起名字的时候，也最好做到顾名思义，这样让人一目了然，你设计的类是做什么的。
ArrayList
上面说ArrayList跟数组的特性类似，原因就是ArrayList的底层就是使用数组来实现的。数组不是长度固定吗？ArrayList就实现了可变长的数组，下面来看看ArrayList是如何实现可变长数组的。
add（E e），首先新增一个长度加一的数组，然后复制原数组的内容到新数组，然后将add进来的元素添加到最后。
add (int index,E element)，将元素 element放到集合里位置为index的地方。1新建长度加一数组，2原数组复制到新数组，3将原数组复制到新数组 ，4从插入位置到最后往后移一位 ，5将新元素覆盖到index位置。
get和set不改变数组长度，直接使用数组的下标来实现操作，比如get方法，底层其实就是数组的获取元素方法：array[index]，而set也是类似，直接在数组中进行赋值： array[index] = element。
remove操作与add的操作类似，只是做了一个反向操作，新增数组和元素右移变成了新增数组和元素左移。
由于ArrayList底层使用数组实现，所以可以直接使用下标（索引）来查找元素，使得ArrayList的查询效率非常高，get方法只是对数组的方法做了一个简单的封装，没有多余的操作。而正是由于数组实现的底层，数组长度不可变，导致每次新增和删除元素使ArrayList长度发生变化的时候，都需要进行数组的复制操作，这样使计算资源的消耗变大，导致效率较低。
简单来说ArrayList的特点就是查询快，增删慢。这里的慢是相对的，如果在增删较少的场景使用，是完全可以的。
在工作中会大量的使用到List集合，但是大部分时候都是无脑使用ArrayList来做实现，如果在性能要求较高并且频繁的对List进行增删元素的场景使用ArrayList，会使效率降低。那么这种频繁增删元素的场景该使用什么样的List呢？噔噔噔~噔~有请LinkedList出场。
LinkedList
链表是一种数据结构，有很多种形式，LinkedList是使用双向链表实现的，那么双向链表是个啥？
当我们站在一起排成一行的时候，就像军训的时候那样，每一行的同学只能知道你的左边和右边是谁，并不知道你左边的左边或者右边的右边是谁。这种只知道左右，不知道其他的数据结构就是双向链表。
双向链表结构中的每一个元素不仅仅包含了数据，还记录了上一个元素的地址和下一个元素的地址，所以每个元素只知道相邻的元素的位置，对于集合中的其他元素则是一概不知。
再来看一下LinkedList如何新增元素。
这个过程非常快速，不用复制什么数组，双向链表知道第一个元素和最后一个元素的地址，来了一个新元素，将新元素的头部指向前一个元素的值，前一个元素的尾部指向新元素的值，这样就完成了添加。
同理删除元素也非常快，只需要修改前后元素的头尾部指向的元素即可。
这里要提示一下，LinkedList不仅仅实现了List的接口，还实现了Deque接口，Deque是队列Queue的子接口。翻译一下，LinkedList不仅仅有List集合在指定下标新增删除元素等功能，还有队列集合Queue的在第一个元素之前添加元素addFirst，在最后一个元素后添加addLast等方法，充分的运用了双向链表知道头尾地址的优势。
LinkedList实现多个接口，就是我们介绍接口的时候说的，用多个标准组成一个新标准，这个就是实现多个接口用法的最好例子。请各位细细品味。
总结一下LinkedList的特点就是增删快，查询慢。这里的增删是指不按下标增删，按照下标增删元素一样慢。
Vector
Vector这个集合是个非常古老的List实现，早在java1.0的版本的时候就有了，但是由于早期的方法名称定义过于繁琐等问题。经过多年的发展，ArrayList已经可以完全的替代Vector这个类。这里说这个类，其实是很多古老的题目和不思进取的出题者会问 "ArrayList和Vector有什么区别呀？"，他们希望的答案是“Vector线程安全，ArrayList线程不安全”。其实ArrayList也可以通过一些手段达到线程安全，以后讲多线程的时候，再来告诉你答案吧。
因为ArrayList已经可以完全的替代Vector，所以现在版本的java已经不再建议使用这个类，以后你可能只会在各种题目里面见到他。
复习一下前面的知识
接口定义了标准，这里的List接口定义了添加元素，删除元素等方法，而实现类根据不同的需求，使用不同的实现方式，比如ArrayList用数组实现，查询快，LinkedList用双向链表实现，增删快。如果我们还有其他场景有特殊需求，比如我要查询快也要增删快，你甚至可以自己去实现List接口，然后实现List的方法即可，这就是使用接口编程的好处。
以下是扩展知识，了解即可。
ArrayList的扩容
ArrayList在频繁做增删元素的时候效率会降低，究其原因就是底层需要判断新建一个多长的新数组来存放增长后的集合，而这个判断的过程比较复杂，可能会需要一次，也可能会需要多次，导致性能下降。
如果我们可以帮助ArrayList进行底层数组的扩容，也就是说我们成了指挥者，直接告诉他，你给我新建一个XXX长度的数组，而不是让ArrayList自己去判断，这样效率会得到不小的提升。其实ArrayList里面也有提供定义数组容量的方法来精准的定义新数组长度。有兴趣的同学可以去看看源代码。
LinkedList下标操作的实现
前面说LinkedList的查询效率比较慢，原因就是双向链表没有数组那种操作下标的优势。LinkedList的get（index）方法实现，做了以下操作：
1.将要查找的index与集合长度的一半进行对比
2.如果在index在集合前半段，从第一个元素开始，往后循环对比每一个元素，直到找到index的位置。如果index在集合后半段，则从最后一个元素开始，往前循环遍历，直到找到index位置。
你没看错，他只能循环，一个个对比，你说能不慢么。不止是get（index），在LinkedList里面任何要使用index的地方，比如add（index，e）都是一个个循环对比，所以效率都不高。
总结，如果要操作下标，请使用ArrayList~
