今天来看看Java集合中的List集合，为什么List集合中元素能重复？为什么List集合是有序的？我们来共同交流交流
List集合基础概念
List是什么？
Collection子接口，实现List接口的容器类中的元素是有顺序的，可以重复
根据List这个单词我们也可以发现List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素，像一个列表一样，里面有一条一条的记录
容器类
- ArrayList
- LinkedList
List集合有什么特点吗？
- 元素有序（有序实际上是说存进去是这个顺序，取出来还是这个顺序。这里说的顺序不是说按照大小排序）
- 可以重复
- 默认按元素添加顺序设置元素的索引，以1递增
List底层是什么结构存储的？
底层是Object类型的数组结构。线性表顺序存储结果
List和数组有什么区别？
- List大小不固定，容量自动增长，可以随意添加；
- 数组元素在内存中连续存放、长度固定、每个元素占用的内存相同、可以通过下标迅速访问数组中的元素，检索效率高。如果想要增加数组长度，需要复制。但如果想要增加一个元素，需要移动大量元素，删除也一样（元素以此向左移动一个元素位置，以填补删除操作造成的空缺）
为什么数组在末尾添加元素效率高？
数组不需要遍历，通过下标就可以直接找到位置，速度很快
为什么数组检索速度快（为什么ArrayList检索速度快）？
ArrayList底层是用数组结构进行存储的，数组的存储空间是连续的，这样我们就可以通过下标来访问元素。所以ArrayList之所以检索效率比较高，不单出是因为下标的原因，是因为底层数组发挥的作用。他们是相辅相成的关系。
那使用的时候如何选用是用ArrayList还是数组呢？
如果查找使用很多，删除和插入很少可以使用数组；
插入删除涉及可以使用ArrayList
方法有哪些？
- Object get(int index)：通过索引下标获取指定位置的集合元素
- Object set(int index, Object element)：根据指定的索引下标修改元素
- void add(int index, Object element)：在指定索引下标位置插入数据
- Object remove(int index)根据指定的索引下标移除数据
- int indexOf(Object o)：获取指定元素在集合中第一次出现的索引下标
- int lastIndexOf(Object o)：获取指定元素在集合中最后一次出现的索引下标
- addAll(小标，集合)：在指定索引下标的位置插入集合
- subList（2，4）：取索引下标在大于等于2小于等于4的元素
- size():集合的长度
List常用算法
类java.util.Collections提供了一些静态方法实现了给予List容器的一些常用算法：
- void sort(List) 对List容器内的元素排序
- vid shuffle(List) 对List容器内的对象进行随机排列
- void reverse(List) 对List容器内的对象进行逆序排列
- 用一个特定的对象重写整个List容器
- void copy (List dest,List src) 将src List容器内容拷贝到dest List容器
- int binarySearch(List,Object) 对于顺序的List容器，采用折半查找的方法查找特定对象
import java.util.List; import java.util.LinkedList; import java.util.Collections; public class ListTest2 { List l1 = new LinkedList(); List l2 = new LinkedList(); for(int i =0 ; i<=9 ; i++){ l1.add("a"+i); } System.out.println(l1); Collections.shuffle(l1); //随机排列 System.out.println(l1); Collections.reverse(l1); //逆续 System.out.println(l1); Collections.sort(l1); //排序 System.out.println(l1); System.out.println(Collections.binarySearch(l1,"a5")); //折半查找 }
LinkedList
单向链表及图
LinkedList的特点：
- LinkedList的底层采用了双向链表数据结构（好处是随即增删改元素快速，不涉及到元素位移）
- 检索效率低（每次需要节点开始逐个往下进行检索，直到找到位置）
- 在空间存储上内存地址不连续
链表的优缺点
链表的优点
增删效率比较高。由于链表上的元素在空间存储上内存地址不连续，所以随即增删元素的时候不会有大量元素位移，只需要修改元素指针域指向的位置就行
链表的缺点
检索效率低。不能通过数学表达式计算被查找元素的内存地址，所以每次查找的时候都是从头节点开始遍历，直到找到位置
List接口相关集合：
