目录
什么是List
在集合框架中，List是一个接口，继承自Collection。
Collection也是一个接口，该接口中规范了后序容器中常用的一些方法
Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的
站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作
List的使用
List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。
ArrayList与顺序表
在集合框架中，ArrayList是一个普通的类，实现了List接口。
?
【说明】
1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
ArrayList的构造：
ArrayList的常见操作?：
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("JavaSE");//添加一个字符串
System.out.println(list);
// 获取list中有效元素个数
System.out.println(list.size());
// 获取和设置index位置上的元素，注意index必须介于[0, size)间
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
list.add(1, "Java数据结构");
System.out.println(list);
// 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
list.remove("JVM");
System.out.println(list);
// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
list.remove(list.size()-1);
System.out.println(list);
// 检测list中是否包含指定元素，包含返回true，否则返回false
if(list.contains("Hello")){
list.add("Hello");
}
// 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之间的元素构成一个新的ArrayList返回
List<String> ret = list.subList(0, 4);
System.out.println(ret);
list.clear();//清空
System.out.println(list.size());
}ArrayList的遍历?
ArrayList 可以使用三种方式遍历：for循环+下标、foreach、使用迭代器
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}//使用迭代器
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}LinkedList与链表?
当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java
集合中又引入了LinkedList，即链表结构。
什么是LinkedList
LinkedList官方文档
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
【说明】
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
LinkedList的构造
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}LinkedList的其他常用方法介绍
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}LinkedList的遍历?
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}