tips

1. 之前讲的有关于删除，其实有两种不同的类型吧，Erase就是就是给我一个节点的地址，然后我把这个节点给他释放掉（删掉）；还有一种就是remove，这个相当于就是说给我一个数值，然后我在链表当中把那个书给他删掉，那这个不就是find+Erase嘛，因此严格以上我们就没有必要提供remove了。

2. 像之前的那个Erase函数，万一有人用pos传过来的是哨兵位头节点的地址，那不就裂开了，确实，所以严谨一点的话，还是需要去检查一下的

复杂链表

相当于在原先我们之前了解到的链表的基础之上，每个节点里面又加了一个random指针，这个指针呢可以指向空，也可以指向整个链表当中的任何一个节点，不要求前后顺序。所以说很多地方都把它叫做复杂链表。

顺序表与链表之间的区别

1. 虽然链表的结构有八种，但是在实际的应用当中还是有一定的区分的。像第一种就是单向不带头不循环链表，这种链表更多的是在做题OJ当中会出现，这就是作为复杂数据结构的子结构出现，如哈希表，邻接表。因为只有这种单链表才有考头，其他的链表都弄得太好了，所以其他考不了。

2. 然而实际当中如果真正用链表数据结构存储数据的话，就一般用的是双向循环带头链表，它几乎完美弥补了顺序表的缺陷，比如说顺序表的尾插，不够了需要扩容，但是对于双向循环带头链表而言，就不需要进行扩容（扩容的话是有消耗的，而且用不完，还有可能会浪费，像双向循环带头链表的话都是按需申请；而且在中间插入删除的话，也不需要挪动数据，只需要改变一下链接关系就可以，所以YYDS）。

3. 那是不是意味着双向循环带头链表可以去替代顺序表？并不是这样子的，他们两个实际上在应用的过程中是组合配合的关系。

4. 比如说我要找到所有数据当中的第八个数据，因为顺序表的话只是在物理上是连续存储，因此如果我要找第八个数据的话，只要通过下标访问非常容易就能够找到，但是由于链表在物理上并不是连续存储的，因此效率上会比顺序表要低；而且还有对于排序而言，链表的排序性能远远比不上顺序表，因为排序的时候经常需要通过下标去访问位置，对于这一点顺序表的话有得天独厚的优势；还有以后要学的数据结构：堆，它的底层也是顺序表；还有二分查找.....像上面提到的这些种种结构还是顺序表更为合适，链表的话就有点不行了，他们优势互补，我的短板正好是你的优点。

5. 顺序表与链表的话都会称赞对方一句yyds，是两个互补的结构。从结构上来讲的话，顺序表物理上是连续的，而链表的话在物理上是不连续的。顺序表的话是支持下标访问的，链表的话就不支持下标访问了，你要去找第几个的话，就得挨着挨着去找，这样的话就会比较麻烦。再次强调几遍（链表不支持下标访问，链表不支持下标访问，链表不支持下标访问，链表不支持下标访问，链表不支持下标访问）！而顺序表的问题就在于删除数据啊什么的，都需要去挪动数据，还有扩容什么的等等

顺序表与链表的缓存利用率与计算机存储体系的简单认识

再来讲一下我们计算机的存储体系：

1. 存储的话，有不同的介质可以去存储，我们平时最关注的存储是哪两个呢？主存（内存）与磁盘（或者叫硬盘）

2. 内存是最主要的存储介质，他的速度比较快，但是没电的话它就没了；还有一个是磁盘的存储，或者说硬盘的存储，他是不带电的，不带电存储，就是说没有电的话，它也可以存储数据，因此比如说你写了一个文件，你必须得把它保存到磁盘里面，如果说万一你电脑没电了，你又不把它保存到硬盘里面，那么你写的这个东西就消失了。

3. 他们现在问题就来了，如果现在我们有一个顺序表与链表。那他们的数据到底是在哪边？到底是存在哪里的？是存在内存里面的，还记得之前讲过什么是数据结构吗？就是说在内存当中去管理数据，这些空间都是我们向内存堆区动态申请过来的，数据结构的内存一般都是从堆区里面过来的，为什么是堆呢，主要是你可以想要多少就给你多少，就是专门开放给程序员自由使用的内存。

4. 那比如说我现在要对顺序表或者说链表的每个位置的数据遍历访问&修改，那到底是谁对这个数据去进行修改（比如说我要把数据➕1）？或者说谁对这个数据去进行访问，然后比如说打印到我们的黑框框里面？这些活到底是谁干的呢？这都是CPU干的，因为你要去访问啊，去打印数据，这些都是都是指令，指令是由CPU去执行的，这些什么访问啊，修改啊，全都是CPU在执行，所以说相当于是CPU要访问内存。

5. 但是呢现在有个问题，CPU是不能够直接访问内存，知道为什么吗？主要是CPU太快，觉得内存太慢了，觉得你跟不上我的速度。这时候就建立了三层缓存这个东西，叫做CPU高速缓存（有三层噢）。因为CPU与内存的速度不一样，因此玩不到一块儿去，这时候就建立一个统一的介质。CPU是先会去访问高速缓存（高速缓存里面也会有地址，比如说知道内存里面这个地址的数据存在我的哪个地址里），如果你在这个缓存里面，那就叫做命中，命中以后我就直接访问了。（高速缓存的话比内存要快很多，那内存为什么不用高速缓存这个介质呢？主要是高速缓存这个介质成本太高了），缓存远远小于内存。如果说没有命中的话，CPU就会把内存当中的数据加载到缓存里面，在进行访问。在高速缓存里面的话，容量有限，一般来说蛮小的，我往里面加载东西进去，万一里面是满的话，一定要把某些东西给挤出去，这里面的就会有一些算法，不是我们需要关心的。

6. 缓存的命中率（利用率）顺序表相对要高，而链表的话相对要低一点。因为这里面的话，主要来说有一个原则：就是说我把内存的数据往缓存里面去加载的时候呢，比如说我要去访问内存的四个字节，事实上并不会只仅仅往缓冲里面加载进去四个字节，多加载几个进去，为什么呢？因为计算机里面有一个东西叫做局部性原理（就是说你现在在访问这块空间里面的数据，那么大概率接下来是访问紧接着下面的数据），而且还由于其他原因加载四个字节进去的话并不划算，所以说尽管我是访问四个字节数据，但是可能顺便会把后面的一段也加载到高速缓存里面。

7. 假设顺序表与链表的数据目前都不在缓存，一开始大家都不命中，然后开始都往高速缓存里面去加载内存当中的数据，这时候比如说再去访问下一个数据，对于顺序表而言的话，就直接会在高速缓存当中命中（因为顺便把内存后面的一段也加载进去了），这个优势的原因就在于他在物理上面是连续存储的。而你看看链表，虽然也会加载内存一长段进去到高速缓存，但这时候并不一定包含链表的下一个节点，因为他节点之间是随机的，乱七八糟无规则的，没有必然的联系。而且这是我还会造成缓存污染，因为它会多加载一段到缓存里面，但是后面那一段可能并不是我想要的，而高速缓存本来就空间十分有限，结果你可能还把别人给挤出去了，你自己又有一部分是毫无用处，就是说原先可能有用的东西，因为新的东西进来就让位，被挤出去了。因此顺序表缓存利用率更高，链表缓存利用率更低。