列表只有两种形式，一种是连续内存的数组，一种是通过指针链起来的链表。

数据结构数组

存放在一个连续的空间中。元素的地址与当前的下标为线性关系。也就是说如果起始地址为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);        });    }

         //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);        });

我们从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));    }

        // 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));