双向循环链表
单链表与双链表对比在实际的软件开发中，从链表删除数据有两种情况： 一是删除节点中“值等于某个给定值”的结点； 二是删除给定指针指向的结点。 对于第一种情况，单链表和双链表都需要查找到值等于给定值的结点，然后将其删除，时间复杂度均为O(n)。 对于第二种情况，已经找到了要删除的结点，而删除前需要知道其前驱结点，对于单链表而言，还是需要从头结点遍历一次链表，其时间复杂度为O(n)，对于双链表，时间复杂度为O(1)。 对于有序链表，双链表可以根据查找值与给定值的大小关系，决定向前或前后查找。 故双链表的应用更加广泛，主要是利用空间换时间的设计思想。如Java中的LinkedHashMap容器就运用了双链表。 当内存空间充足时，更加追求代码的执行速度，可以选择空间复杂度相对较高，但时间复杂度相对很低的算法或数据结构。相反，如果内存比较紧缺，如代码跑在手机或单片机上，这时候就要使用时间换空间的设计思想。即对于执行较慢的程序，可以通过消耗更多的内存进行优化；对于内存消耗过多的程序，可以通过消耗更多时间来降低内存的消耗。 链表与数组性能对比插入删除的时间复杂度：数组O(n)，链表O(1)(还要分情况) 查询的时间复杂度：数组O(1)，链表O(n) 数据使用的是连续内存空间，可以借助CPU的缓存机制，预读数组中的数据，访问效率更高。链表使用的是非连续内存空间，对CPU缓存机制不友好，没办法有效预读。 数组的缺点是大小固定，申请内存过大，容易导致内存不足，申请过小，容易导致不够用而需要扩容耗时。链表本身没有大小限制，天然支持扩容，但指针需要占用额外的存储空间，同时插入和删除操作会导致频繁的申请和释放内存，容易造成内存碎片。在Java中可能导致频繁的GC(垃圾回收)。 链表实现技巧理解指针或引用的含义：不管是指针或引用，都是存储所指对象的内存地址。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。或者说，指针存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 如：p->next=q。这行代码是说，p 结点中的 next 指针存储了q结点的内存地址 p->next=p->next->next。这行代码表示，p结点的next指针存储了p结点的下下一个结点的内存地址 警惕指针丢失或内存泄漏：插入结点时，一定要注意操作顺序。如在a、b结点插入x结点时，先将x的next指针指向结点b，在将a的next指针指向结点x，才不会丢失指针，导致内存泄漏。删除链表结点时，一定要记得手动释放内存空间。否则也会出现内存泄漏的问题。 利用哨兵简化实现难度：针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况作特殊处理，实现会很繁琐，而且也很容易考虑不全。为此，引入哨兵，不管链表是否为空，head指针会一直指向哨兵结点(头结点)。 重点留意边界条件处理：在一些边界或异常情况下，代码最容易产生bug。在代码编写完成后，一定要检查边界条件是否考虑全面。对于链表需要考虑以下几个边界情况： 实际上，不光光是写链表代码，你在写任何代码时，也千万不要只是实现业务正常情况下的功能就好了，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！ 举例画图，辅助思考：看图写代码，可以释放脑容量，留出更多的时间进行逻辑思考。 多写多练，没有捷径：多写几遍，出问题就一点一点调试，熟能生巧 常见的链表操作- 单链表反转
- 链表中环的检测
- 两个有序链表的合并
- 删除链表倒数第n个结点
- 求链表的中间节点
经典应用场景--LRU缓存淘汰算法缓存是一种提高数据提取性能的技术，如CPU缓存、数据库缓存、浏览器缓存等 缓存有大小限制，当缓存被用满时，需要缓存淘汰策略对数据进行清理，腾出空间。 常见的缓存策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used） 实现方式：可以用有序的单链表，最近的数据放在头部，之前的数据放在尾部，如果空间不足，就删除尾部节点，同时链表头部插入新的数据。
| 
楼主
标题置顶
标题高亮
