1-1 链表(List)及经典问题

链表基础知识

链表的典型应用场景

现在我们有这样一个需求：现在这个4GB的存储器是一个连续的存盘空间，我们要在这个存盘空间里面开辟1GB的连续的存盘空间，接下来我们是要在4GB的存储器空间划分出来1GB的存盘空间，如图：

malloc函式是c语言里的内容，就好比java里的new；作用相同的，就是开辟存盘空间，

可以想象成我找了一个1GB大小的阵列，虽然有点夸张，只是举例，

经过我这样的申请空间之后，我们把我们的整个资料切分了，原本是好好的一整块阵列，变成两块了，一个是2GB的碎片，一个是1GB的碎片，如图：

那我们接下来在程序里申请空间的话，我们如何去管理这个存储器碎片？

作业系统底层里面，把两个存储器碎片用链表给他窜起来，我们可以通过2GB找到1GB的碎片，这样就不至于说我们存储器里面出现碎片丢失，有一片存盘空间找不到的情况；这是简单的一个应用，

现在只是简单拿出来了解一下，后续会对这个LRU快取淘汰算法进行详细的讲解，

什么是LRU？你可以理解为冰箱里有好多菜，我周一买了些菜，周二买了些菜，周日也买了些菜，但我们最后发现冰箱里放不下了，这时候我们新买的菜也不能不放进冰箱里，所以这时我们只能在冰箱里挑出一些菜给它扔掉，这时候我们会扔哪些菜呢？答案肯定是放的最久的菜，因为是最容易坏的，

那我们如何区分哪个最久呢？我们可以用链表给它链起来，这样我们就知道，哪个菜是最开始就放进冰箱里的，我们可以优先将它淘汰掉，并放入我们新的菜，就好比将图片中的资料1删掉，存入新的资料5，再想填入新的资料，删掉资料2，以此类推，

假设资料3是我们非常想吃的菜，但按照顺序即将被淘汰掉，我们可以把资料3拿出来，放在最后，更新一下它的优先级，这样的话资料3的优先级就高于资料4，我们洗掉资料2之后，会洗掉资料4；这是链表常用的一个实作方式，

链表使用的场景还是非常多的，

链表与阵列的结构性能对比

阵列的存盘是连续、聚合的

链表的存盘是离散的，我们通过抽象的指标域概念连接了起来

阵列是一段连续的存盘空间，支持资料随机访问，我们想找到哪个资料就可以立刻找到；但我们假设有一个100存储器的阵列，我想对这个阵列进行扩容的话，我可能需要申请一个200存储器的阵列，再把100存储器阵列的所有资料原封不动的搬过去，这样我们才能得到一个200存储器的阵列，

链表是非连续的，扩容非常简单，找一个结点，就可以实作插入或者洗掉；但我们如果访问资料的话，就只能随机的访问，它不能按顺序进行访问；

这是我们从资料结构层面进行对比，

那我们从硬件层面考虑呢？

CPU读取优化

读取阵列时，假设我想读取阵列的第100个数，我可以直接找到资料并将它拿出来，但真正计算机实作里面，我们真的是只把100这一个资料从存储器拿到cpu里面吗？其实不是的，存储器的内容导到cpu里，这叫做背景关系切换，这种资料之间的读取是非常耗时的，所以说cpu不会大材小用的，你想读一个东西，我就只老老实实的读一个吗？cpu不是这样的，cpu很不老实，在我们当前节点前后，分别多读取一段存储器空间，具体资料各个硬件不一样，当我们读取100的时候，cpu很多余的将100前后的x个空间都拿出来，它具体读取的内容是x+1+x，虽然你只想读取一个，但是cpu会读取2x+1个数，

cpu为什么会这幺做？正是因为阵列的连续的，如果我想读取一个数的话，那么我读取前面或者后面这个数的概率会大一点，所以它会进行一个多余的操作，但这个操作也不算是多余，它读取一个资料，和再读取这个资料前后的资料，如果时间消耗几乎是一样的话，cpu为什么不多读一点呢？这就是我们cpu层面上的快取优化，

那对于链表来说，可以用这种优化吗？答案肯定是不能的，因为链表的存盘是非常随机的，在存储器里一个在东面，一个在西面，当你cpu想读当前这一个链表结点时，它不知道你前面的结点和后面的结点都在哪里，所以说链表有很大的一个缺点，它没有办法运用在我们的cpu快取优化；对应到我们的工程实作里面，这两个的差距是非常非常大的，