链表的底层存储结构

        和数组相对比，数组需要一块连续的内存空间来存储，对内存的要求比较高。比如，如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的声誉总可用空间大于100MB，仍然会申请失败。

        而链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

        如下图：

      三种最常见的链表结构

        单链表       

        头结点用来记录链表的基地址，尾结点的指针指向一个空地址NULL。

        插入删除非常方便，时间复杂度为O(1)：

        但随即访问第k个元素，就比较低效了，无法像数组一样根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是要依次遍历结点直到找到相应结点。时间复杂度为O(n)。

        循环链表

        是一种特殊的单链表。它和单链表唯一的区别就是尾结点不指向空地址而是指向链表的头结点。

        它的优点是：从链表尾到链头比较方便，当要处理的数据具有环形结构特点时，就特别适合采用循环链表。（比如约瑟夫问题）

        双向链表

        每个结点不止有一个后继指针指向下一个结点，还有一个前驱指针指向前一个结点。

        但比单链表要占用更多的内存空间。

        虽然如此，它在某些情况下的插入、删除等操作都要比单链表简单、高效 。

        以删除操作为例：

        1)删除结点中“值等于某个给定值”的结点。

        单纯的删除操作时间复杂度是O(1)，但是遍历查找的时间是主要的耗时点，时间复杂度为O(n)，则总的时间复杂度为O(n)。

        2)删除给定指针指向的结点。

        我们已经找到了要删除的结点，但是删除某个结点q还需要知道它的前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找前驱结点我们还要从头开始遍历链表，直到p->next=q，说明p是q的前驱结点。

        但是对于双向链表来说就比较有优势了，可以直接获取到它的前驱结点，所以单链表删除操作需要O(n)的时间复杂度，而双链表只需要在O(1)的时间复杂度内就搞定了。

        插入操作也是同理，不再赘述。

        除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

        综上，这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表应用更加广泛的原因。

        这就是用空间换时间的设计思想：当内存空间充足的时候，如果我们更加追求代码的执行速度，就可以选择空间复杂度相对较高，时间复杂度相对较低的额算法或者数据结构。反之，如果内存比较紧缺，我们就要用时间换空间。

        总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。    

        如果把双向链表和循环链表整合在一起，就可以有一个新的版本，双向循环链表：

      链表vs数组

        1)数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU缓存不友好，没办法有效预读。

        这个评论解释了原因：

        2)数组的缺点是大小固定，如果声明的太大，系统可能没有足够的连续内存空间分配给它，如果声明的太小，则扩容的时候比较费时。

        3)如果你的代码对内存的使用非常苛刻，数组就更适合。因为链表中的每个结点都需要消耗额外的存储空间去存储指针，内存消耗会翻倍。而且频繁的插入删除在操作会导致频繁的内存申请和释放，容易造成内存碎片。

      缓存淘汰策略

        缓存的大小有限，当缓存被用满时，哪些素具应该被清理出去，哪些数据应该被保留，需要缓存淘汰策略来决定。

        常见的策略有三种：先进先出策略FIFO（First In,First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略（Least Recently Used）。

      如何基于链表实现LRU缓存淘汰算法？

        这个方法不管缓存有没有满，都需要遍历一遍览表，所以时间复杂度为O(n)。

        实际上可以继续优化这个思路，比如引入散列表来记录每个数据的位置，将缓存时间复杂度降到O(1)。这个后面讲到散列表的时候再说。

      如何基于数组实现LRU缓存淘汰算法？

      如何用判断一个用单链表存储的字符串是否是回文字符串？

        评论真的很精彩，闲暇了也可以多看看评论涨姿势~

      如何轻松写出正确的链表代码？

        1)理解指针或者引用的含义。

        将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

        2)警惕指针丢失和内存泄漏。

        插入结点时，一定要注意操作的顺序。比如在a和b结点之间插入x：

        
        要先将插入结点的next指针指向结点b，再把结点a的next指针指向结点x，这样才不会丢失指针，导致内存泄漏。

        3)利用哨兵简化实现难度。

        针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个结点的情况进行特殊处理，这样代码会很繁琐不简洁。如果我们引入哨兵节点，在任何时候，不管链表是否为空，head指针都会一直指向这个哨兵结点。（我们也把这种有哨兵节点的链表叫带头链表，没有哨兵结点的链表叫做不带头链表）

        （原文中举了一个在数组中查找key的例子，可以看一看~）

        4)重点留意边界条件处理。

        可以用来检查链表代码是否正确的边界条件有这样几个：

        5)举例画图，辅助思考。

        6)多写多练。

        老师精选了5个常见的链表操作，只要把它们写熟练，链表操作应该都没有问题了：

      小结

        写链表代码是最考验逻辑思维能力的。因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。所以，这也是很多面试官喜欢让人手写链表代码的原因。所以，这一节讲到的东西，一定要自己写代码实现一下，才有效果。