列表只有两种形式，一种是连续内存的数组，一种是通过指针链起来的链表。
数据结构
数组
存放在一个连续的空间中。元素的地址与当前的下标为线性关系。也就是说如果起始地址为start,要获取下标为 i 的元素，每个元素的大小为x，那么元素 x 的地址就为add(x)=start+x*i.在java中使用ArrayList来实现。
因此我们可以知道数组具有的特性：
- 随机访问非常简单，只需要通过起始地址和下标计算即可
- 扩展困难，由于数组需要连续的空间，当我们开了存放n个元素的空间时，如果要存放n+1个则需要根据扩容策略另外开辟一个大于存放n个元素的空间，将原数组拷贝过去，然后将第n+1放到对应位置
- 插入删除困难。将元素插入到i位置，都需要将i位置及以后的元素搬移到后一个位置，将i位置腾出来。同理将第i个元素删除，则需要将第i+1到最后一个元素向前搬移一个位置。
链表
存放在一个非连续的空间中，元素通过一个next指针来存储下一个元素的地址，通过next指针，就能链头（第一个元素）遍历到链尾（最后一个元素）。还可以增加一个before指针来存储当前元素上一个元素的地址，来支持反向遍历,即从链尾遍历到链头。java中使用LinkedList来实现
我们也总结链表的特性：
- 随机访问困难，想要访问第i个元素，必须从链头通过i个next指针，获取到该元素。
- 扩展简单。当需要新增一个元素时，只需要找个空间放新的元素，并更改对应的next指针，before指针
- 插入删除简单。插入只需将对应的next指针和before指针做更改。删除也一样，将前一个元素的next更改为删除元素的next，将后一个元素的before更改为删除元素的before即可。
遍历
对于数组遍历有以下多种形式：
- 使用下标遍历
- iterator遍历
- for-each循环遍历
- foreach方法遍历
- stream的foreach遍历
我们将arrayList和linkedList分开来分析。
ArrayList的遍历
public static void arraylist(ArrayList<Integer> arrayList){
//1. 下标遍历，get(i)的复杂度为O(1),因此遍历复杂度为O(n)
for(int i=0;i<arrayList.size();i++){
System.out.println( arrayList.get(i));
}
//2. iterator遍历，本质上也是下标获取，it.next为O(1),因此遍历复杂度为O(n)
Iterator<Integer> it=arrayList.iterator();
while(it.hasNext()){
int i=it.next();
System.out.println(i);
}
//3. for-each循环遍历,底层使用iterator实现.因此遍历复杂度为O(n)
for(int i:arrayList){
System.out.println(i);
}
//4. foreach方法遍历。内部使用index遍历实现，与 for(int i=0;i<arrayList.size();i++)类似.因此遍历复杂度为O(n)
arrayList.forEach(item->{
System.out.println(item);
});
//5. stream 的foreach遍历.本质上调用的是ArrayList中的ArrayListSpliterator.forEachRemaining方法。本质上也是个for循环的下标遍历.遍历复杂度O(n)
arrayList.stream().forEach(item->{System.out.println(item);});
//6. stream的foreach并行遍历。与stream类似，也是ArrayListSpliterator.forEachRemaining方法。遍历复杂度O(n)
arrayList.parallelStream().forEach(item->{System.out.println(item);});
}
public static void linkedList(LinkedList<Integer> linkedList){
//1. 下标遍历。get(i)的复杂度为O(n),遍历复杂度O(n^2)
for(int i=0;i<linkedList.size();i++){
System.out.println(linkedList.get(i));
}
//2. iterator遍历，使用链表元素遍历，next()复杂度为O(1),遍历复杂度O(n)
Iterator<Integer> it=linkedList.iterator();
while(it.hasNext()){
int i=it.next();
System.out.println(i);
}
//3. for-each循环遍历。底层使用iterator，因此复杂度为O(1),遍历复杂度O(n)
for(int i:linkedList){
System.out.println(i);
}
//4. foreach方法遍历。底层使用itreble的for-each循环遍历，因此复杂度为O（1）,遍历复杂度O(n)
linkedList.forEach(item->{System.out.println(item);});
//5. stream的foreach遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n)
linkedList.stream().forEach(item->{
System.out.println(item);
});
//6. stream的foreach并行遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n)
linkedList.parallelStream().forEach(item->{
System.out.println(item);
});
}linkedList的遍历
//1. 下标遍历。get(i)的复杂度为O(n),遍历复杂度O(n^2)
for(int i=0;i<linkedList.size();i++){
System.out.println(linkedList.get(i));
}
//2. iterator遍历，使用链表元素遍历，next()复杂度为O(1),遍历复杂度O(n)
Iterator<Integer> it=linkedList.iterator();
while(it.hasNext()){
int i=it.next();
System.out.println(i);
}
//3. for-each循环遍历。底层使用iterator，因此复杂度为O(1),遍历复杂度O(n)
for(int i:linkedList){
System.out.println(i);
}
//4. foreach方法遍历。底层使用itreble的for-each循环遍历，因此复杂度为O（1）,遍历复杂度O(n)
linkedList.forEach(item->{System.out.println(item);});
//5. stream的foreach遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n)
linkedList.stream().forEach(item->{
System.out.println(item);
});
//6. stream的foreach并行遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n)
linkedList.parallelStream().forEach(item->{
System.out.println(item);
});Iterator（迭代器）原理
我们从arraylist讲这个，linkedlist的实现方式基本上是一样的。
- ArrayList的iterator()方法返回一个Iterator对象，他是ArrayList的内部类Itr类型的。
- ArrayList中有一个modCount值，这个值主要是用来标识当前list的更改的次数，相当于一个版本号。这个值初始为0，每当调用list的add或remove等增加删除元素的操作时，就会对modCount进行自增。（batch操作的话会增加对应的数）
- Itr类新建时，会初始化expectedModCount 为modCount，用来记录当前期望的arrayList的版本
- Itr还会记录两个值，一个cursor表示下一个要访问元素的下标默认为0，一个lastRet表示上一次操作的元素的下标，默认-1。这两个值有什么用呢：
- 在Itr的hasNext方法中，判断cursor是否为当前list的size来返回是否有下一个元素
- 在Itr的next方法中，检查cursor的值是否未越界，检查expectedModCount是否与modCount一致，如果符合则将lastRet赋值为cursor，将cursor自增1，然后返回lastRet下标的元素
- 在Itr的remove方法中，检查expectedModCount是否与modCount一致，检查lastRet不小于0，则调用ArrayList的remove方法移除元素，将cursor回退未lastRet，将lastRet设为-1，同步expectedModCount为modCount的值。
做个总结：
- 通过迭代器的三个方法，我们可以知道，当迭代器在迭代过程中，如果直接在ArrayList中直接进行修改，导致modCount值增加，而迭代器不知道，expectedModCount就会与modCount不一致，就会使得next和remove都无法执行。这种机制就被称为fail-fast机制
- 在Itr执行remove之后将lastRet设为了-1，也就是说remove不能连续执行，因为remove会先检查lastRet不能小于0
如何删除元素
讲清楚了迭代器原理，我们就可以来看看如何才能正常的删除元素了，以及为什么有些方式删除会出现问题：
同样分开arrayList和linkedList的删除
arrayList的删除
public static void delArrayList(ArrayList<Integer> arrayList) {
//1.1 下标遍历值顺序删除。
//arrayList的remove方法会将第i+1到最后一个元素往前挪动，调用System.arrayCopy()方法。如果从第一个元素开始删除，那是非常低效的
for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) % 2 == 0) {
arrayList.remove(i);
i--;
}
}
//1.2 下表遍历之逆序删除。
//如果从最后一个元素开始删除，如果连续删除后面n个元素，复杂度为O（n）没有额外的挪动工作，但如果间隔删除复杂度就变成O（n^2)每次删除都会带来元素挪动，间隔删除不建议使用
for (int i = arrayList.size(); i >= 0; i--) {
if (arrayList.get(i) % 2 == 0) {
arrayList.remove(i);
i--;
}
}
//2.迭代器遍历删除。
//本质上调用的是ArrayList的删除方法，而且是正向删除，也就是说每次删除会导致后面的元素挪动，复杂度为O(n^2)，不建议使用
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
iterator.remove();
}
// 3. for-each循环不能删除。
//for-each 是基于迭代器的，但没有返回迭代器，无法通过迭代器来修改list，同时如果在遍历过程中，有其他线程对list进行修改，也会造成异常
/* for(Integer i:arrayList){
arrayList.remove(i);
}*/
// 4. foreach方法遍历不能删除
//本质上是for循环，因为没有正确控制index下标，因此也不能正常删除。删除第i个元素后，第i+1元素到最后的元素会往前移，而此时下标会变为i+1也就导致了原先数组的第i+1个元素被跳过的问题
//arrayList.foreach(item->item);
//5. 使用removeIf方法删除
// 使用一个bitSet来记录需要的元素下标，最后再将元素进行统一移动，复杂度O(n)，空间复杂度O(n)。推荐使用这种方式
arrayList.removeIf(item -> item % 2 == 0);
//6. stream的foreach方法中也是不能正常删除的。但有filter函数.
//7. filter本质上是将符合条件的元素复制过去，不会对原数组操作，最后需要collect()获取到新的对象。
arrayList.stream().filter(item -> item % 2 == 0);
}
public static void delLinkedList(LinkedList<Integer> linkedList){
// 1. 下标删除
// remove方法通过更改链表的节点来删除，删除本身是个O(1)的操作。但定位第i个元素，是个O(n)的操作
//因此连续删除n个元素是个O(n)复杂度，间隔删除n个元素则O(n^2)复杂度。
// 因为linkedList是双向链表，因此与反向删除也一样。
for(int i=0;i<linkedList.size();i++){
linkedList.remove(i);
i--;
}
//2. 迭代器删除
// 删除单个元素为O(1),删除n个元素为O(n)
Iterator iterator=linkedList.iterator();
while(iterator.hasNext()){
iterator.next();
iterator.remove();;
}
//3. removeIf
//使用迭代器的删除。删除n个元素为O(n)
linkedList.removeIf(item->item>2);
//4. stream filter删除。不会对原数组操作。复杂度也是O(n)
linkedList.stream().filter(item->item>2).forEach(item-> System.out.println(item));
}linkedList的删除
// 1. 下标删除
// remove方法通过更改链表的节点来删除，删除本身是个O(1)的操作。但定位第i个元素，是个O(n)的操作
//因此连续删除n个元素是个O(n)复杂度，间隔删除n个元素则O(n^2)复杂度。
// 因为linkedList是双向链表，因此与反向删除也一样。
for(int i=0;i<linkedList.size();i++){
linkedList.remove(i);
i--;
}
//2. 迭代器删除
// 删除单个元素为O(1),删除n个元素为O(n)
Iterator iterator=linkedList.iterator();
while(iterator.hasNext()){
iterator.next();
iterator.remove();;
}
//3. removeIf
//使用迭代器的删除。删除n个元素为O(n)
linkedList.removeIf(item->item>2);
//4. stream filter删除。不会对原数组操作。复杂度也是O(n)
linkedList.stream().filter(item->item>2).forEach(item-> System.out.println(item));