4. 数据结构篇：链表
链表和数组有什么不同？
链表和数组一样，也是非常常用的数据结构，但是比数组稍微复杂一点，这两者也经常拿来做比较，那他们有什么不同呢？
我们先从底层的数据结构来看一看： 
① 数组需要连续的内存空间，对内存的要求较高。而链表恰恰相反，它通过指针把一组零散的内存块串联起来，其中，内存块称为链表的结点，而指向下一个内存块地址的指针称为后继指针。
因此，假如需要申请一块 100MB 大小的内存空间，数组很可能因为没有一块连续的 100MB 内存而申请失败，而链表则要求零散的内存加起来有 100MB 就够了。
② 链表和数组一样，支持数据的查询、插入和删除操作， 数组通过下标查询数据（随机访问）的速度很快，因为可以通过寻址公式快速得到任意下标的内存地址，但是插入和删除元素的速度很慢，因为涉及到数据的的搬移。
而链表查询的速度很慢，因为某一结点的内存地址只能从头开始遍历去获取，但是插入和删除操作很快，因为只需要改变指针的指向，不涉及到数据的搬移。 
链表的类型
链表的类型有单链表、循环链表、双向链表、双向循环链表。
1. 单链表
单链表最简单，也最常用，单链表有一个“头结点”，和一个“尾结点”，头结点记录了链表的基地址，通过基地址就可以遍历得到整条链表，尾结点的后继指针 next 指向空地址 null，表示链表的终点。 
2. 循环链表
循环链表是一种特殊的单链表，不同的是只需要把尾结点的后继指针改成指向头结点。当需要处理的数据具有环形结构时，就比较适合采用循环链表。比如著名的约瑟夫问题。 
3. 双向链表
双向链表，顾名思义，它支持双向遍历。它的结构与单向链表相比，除了有一个后继指针 next 外，还有一个前驱指针 prev。 
虽然两个指针占用了更多的内存空间，但是也带来了操作的灵活性。它的插入和删除操作比单链表更加高效。
这里来仔细分析一下单链表的插入和删除操作：
先来看删除操作
从一个链表中删除一个数据无外乎两种：
- 删除某个给定值的结点
- 删除给定指针指向的结点。
第一种，虽然单链表的删除操作的时间复杂度是 O(1)，但是删除之前查找这个给定值的过程比较耗时，需要从头开始遍历，时间复杂度为 O(n)，根据加法法则，删除操作总的时间复杂度就为 O(n)。
第二种，虽然知道了指定删除节点的地址，但是删除结点需要知道其前驱节点的指针和下一个节点的指针，下一个结点的指针就是其后继指针，而单链表并不能直接获取其前驱结点，因此需要从头结点开始遍历链表，直到 p->next = q，说明 p 就是 q 的前驱结点，这种情况时间复杂度仍为 O(n)。
而对于双向链表来说，第二种情况就比较有优势了，因为每个结点都保留了前驱结点的指针，因此删除操作可以在 O(1) 的时间复杂度内搞定。
对于插入操作
也分为两种：
- 在指定结点后插入
- 在指定结点前插入
第一种，只需要简单改变指定结点的后继指针指向新结点，而新结点的指针指向下一个结点就 OK 了，时间复杂度为 O(1)。
第二种，单链表无法知道指定结点的前驱结点，所以要从头遍历链表来获取，时间复杂度为 O(n)。而双向链表可以把复杂度降为 O(1)。
4. 双向循环链表
它长这个样子： 
拓展
双向链表实际上用到了空间换时间的设计思想。对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。
比较典型的应用就是缓存。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
数组 VS 链表
使用链表实现 LRU 缓存淘汰算法
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
如何使用链表来实现 LRU 缓存淘汰策略？
可以维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部。
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
基于这种算法实现的的缓存访问的时间复杂度为 O(n)。 实际上，如果用散列表来实现，可以把时间复杂度降为 O(1)，后面再用代码来实现。
本文首发于 turbobin’s Blog 。转载请注明出处，附上本原文链接， 谢谢合作。
关注微信公众账号「曹当家的」，订阅最新文章推送