鲁达 列表只有两种形式，一种是连续内存的数组，一种是通过指针链起来的链表。
数据结构
数组
存放在一个连续的空间中。元素的地址与当前的下标为线性关系。也就是说如果起始地址为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<arrayLi();i++){ Sy( arrayLi(i)); } //2. iterator遍历，本质上也是下标获取，it.next为O(1),因此遍历复杂度为O(n) Iterator<Integer> it=arrayLi(); while()){ int i=it.next(); Sy(i); } //3. for-each循环遍历,底层使用iterator实现.因此遍历复杂度为O(n) for(int i:arrayList){ Sy(i); } //4. foreach方法遍历。内部使用index遍历实现，与 for(int i=0;i<arrayLi();i++)类似.因此遍历复杂度为O(n) arrayLi(item->{ Sy(item); }); //5. stream 的foreach遍历.本质上调用的是ArrayList中的ArrayLi方法。本质上也是个for循环的下标遍历.遍历复杂度O(n) arrayLi().forEach(item->{Sy(item);}); //6. stream的foreach并行遍历。与stream类似，也是ArrayLi方法。遍历复杂度O(n) arrayLi().forEach(item->{Sy(item);}); } public static void linkedList(LinkedList<Integer> linkedList){ //1. 下标遍历。get(i)的复杂度为O(n),遍历复杂度O(n^2) for(int i=0;i<linkedLi();i++){ Sy(linkedLi(i)); } //2. iterator遍历，使用链表元素遍历，next()复杂度为O(1),遍历复杂度O(n) Iterator<Integer> it=linkedLi(); while()){ int i=it.next(); Sy(i); } //3. for-each循环遍历。底层使用iterator，因此复杂度为O(1),遍历复杂度O(n) for(int i:linkedList){ Sy(i); } //4. foreach方法遍历。底层使用itreble的for-each循环遍历，因此复杂度为O（1）,遍历复杂度O(n) linkedLi(item->{Sy(item);}); //5. stream的foreach遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n) linkedLi().forEach(item->{ Sy(item); }); //6. stream的foreach并行遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n) linkedLi().forEach(item->{ Sy(item); }); }linkedList的遍历
//1. 下标遍历。get(i)的复杂度为O(n),遍历复杂度O(n^2) for(int i=0;i<linkedLi();i++){ Sy(linkedLi(i)); } //2. iterator遍历，使用链表元素遍历，next()复杂度为O(1),遍历复杂度O(n) Iterator<Integer> it=linkedLi(); while()){ int i=it.next(); Sy(i); } //3. for-each循环遍历。底层使用iterator，因此复杂度为O(1),遍历复杂度O(n) for(int i:linkedList){ Sy(i); } //4. foreach方法遍历。底层使用itreble的for-each循环遍历，因此复杂度为O（1）,遍历复杂度O(n) linkedLi(item->{Sy(item);}); //5. stream的foreach遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n) linkedLi().forEach(item->{ Sy(item); }); //6. stream的foreach并行遍历。调用的是linkedList的LLSpliterator的forEachRemaining，也是通过节点的next指针遍历,遍历复杂度O(n) linkedLi().forEach(item->{ Sy(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) { 下标遍历值顺序删除。 //arrayList的remove方法会将第i+1到最后一个元素往前挪动，调用Sy()方法。如果从第一个元素开始删除，那是非常低效的 for (int i = 0; i < arrayLi(); i++) { if (arrayLi(i) % 2 == 0) { arrayLi(i); i--; } } 下表遍历之逆序删除。 //如果从最后一个元素开始删除，如果连续删除后面n个元素，复杂度为O（n）没有额外的挪动工作，但如果间隔删除复杂度就变成O（n^2)每次删除都会带来元素挪动，间隔删除不建议使用 for (int i = arrayLi(); i >= 0; i--) { if (arrayLi(i) % 2 == 0) { arrayLi(i); i--; } } //2.迭代器遍历删除。 //本质上调用的是ArrayList的删除方法，而且是正向删除，也就是说每次删除会导致后面的元素挪动，复杂度为O(n^2)，不建议使用 Iterator iterator = arrayLi(); while ()) { i(); } // 3. for-each循环不能删除。 //for-each 是基于迭代器的，但没有返回迭代器，无法通过迭代器来修改list，同时如果在遍历过程中，有其他线程对list进行修改，也会造成异常 /* for(Integer i:arrayList){ arrayLi(i); }*/ // 4. foreach方法遍历不能删除 //本质上是for循环，因为没有正确控制index下标，因此也不能正常删除。删除第i个元素后，第i+1元素到最后的元素会往前移，而此时下标会变为i+1也就导致了原先数组的第i+1个元素被跳过的问题 (item->item); //5. 使用removeIf方法删除 // 使用一个bitSet来记录需要的元素下标，最后再将元素进行统一移动，复杂度O(n)，空间复杂度O(n)。推荐使用这种方式 arrayLiIf(item -> item % 2 == 0); //6. stream的foreach方法中也是不能正常删除的。但有filter函数. //7. filter本质上是将符合条件的元素复制过去，不会对原数组操作，最后需要collect()获取到新的对象。 arrayLi().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<linkedLi();i++){ linkedLi(i); i--; } //2. 迭代器删除 // 删除单个元素为O(1),删除n个元素为O(n) Iterator iterator=linkedLi(); while()){ i(); i();; } //3. removeIf //使用迭代器的删除。删除n个元素为O(n) linkedLiIf(item->item>2); //4. stream filter删除。不会对原数组操作。复杂度也是O(n) linkedLi().filter(item->item>2).forEach(item-> Sy(item)); }linkedList的删除
// 1. 下标删除 // remove方法通过更改链表的节点来删除，删除本身是个O(1)的操作。但定位第i个元素，是个O(n)的操作 //因此连续删除n个元素是个O(n)复杂度，间隔删除n个元素则O(n^2)复杂度。 // 因为linkedList是双向链表，因此与反向删除也一样。 for(int i=0;i<linkedLi();i++){ linkedLi(i); i--; } //2. 迭代器删除 // 删除单个元素为O(1),删除n个元素为O(n) Iterator iterator=linkedLi(); while()){ i(); i();; } //3. removeIf //使用迭代器的删除。删除n个元素为O(n) linkedLiIf(item->item>2); //4. stream filter删除。不会对原数组操作。复杂度也是O(n) linkedLi().filter(item->item>2).forEach(item-> Sy(item));