链表结构

• 链表与数组

  • 底层存储

    • 数组需要一块连续的空间，而链表只需要一些零散的内存快即可。

    

  • 性能比拼1

  

  • 性能比拼2
    • 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
    • 除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。
    • 而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）

• 单链表

• 双链表
  • 实际中双向链表应用更广，比单链表效率要高。找到前驱只需要O(1)
  • Linklist,LinkedHashMap 等都是双向链表。
  • Linklist——默认删除是从头结点开始删除的。

• 循环链表

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

• 缓存

​ 缓存是为了缓解慢速的内存与快速的CPU之间矛盾而产生的，访问速度极快。

​ 缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 ==FIFO==（First In，First Out）、最少使用策略 ==LFU==（Least Frequently Used）、最近最少使用策略 ==LRU==（Least Recently Used）

​ LRU 策略，使得页面置换次数低，抖动次数少。

• 算法思想

  我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。---头插法
  

  • 如果此数据之前被缓存进链表中了，我们遍历得到这个链表的结点，并将原来的位置删除，将该节点插入链表的头部。
  • 如果此数据没有在缓存链表中，则：
    • 如果缓存未满，则直接插入到链表的头部。
    • 如果此时缓存已经满了，则删除链表尾部的内容，然后将新的数据结点插入链表的头部。

• 代码实现

判断一个字符串是否是回文串

• 算法思想(双向链表)
  • 用快慢指针找到链表的中点(当快指针走到头时，慢指针就恰好走到中间)
  • 然后慢指针在往反方向走，走到表头，相当于是反向遍历链表左半部分(双向链表)
  • 同时，正向遍历链表的右半部分，并且将二者数据进行比较，如果完全一致，则说明是回文串。
• 算法思想(单链表)
  • 用快慢指针找到链表的中点(当快指针走到头时，慢指针就恰好走到中间)
  • 将单链表后半部分逆序，就是慢指针的next部分。一直遍历知道链表尾部
  • 同时，正向遍历链表的前半部分，并且将二者数据进行比较，如果完全一致，则说明是回文串。
  • 最后将后半部分复原

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

• 理解指针或引用的含义

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

  ​ C语言--指针，Python，Java--引用

• 警惕指针丢失和内存泄漏

  • 我们插入结点时，一定要注意操作的顺序。(先把next指向存好，在将next指向其他地方)
  • 删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。

• 利用哨兵简化实现难度

  • 不利用哨兵的话，插入和删除，都需要考虑边界上的特殊结点。第一个和最后一个。

  %% 插入操作
  new_node->next = p->next;
  p->next = new_node;
  
  if (head == null) { %%需要额外考虑插入的结点是不是第一个结点
    head = new_node;
  }
  
  %%删除操作
  p->next = p->next->next;
  
  if (head->next == null) {%%需要额外考虑删除的结点是不是最后一个结点
     head = null;
  }
  

  • 引入头结点，即哨兵，head指针会一直指向这个头结点。有了这个头结点，插入和删除代码就统一了。

• 重点留意边界条件处理

  ==健壮性==

  ​ 在写任何代码时，也千万不要只是实现业务正常情况下的功能就好了，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

  • 如果链表为空时，代码是否能正常工作？
  • 如果链表只包含一个结点时，代码是否能正常工作？
  • 如果链表只包含两个结点时，代码是否能正常工作？
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

• 举例画图，辅助思考

• 多写多练，没有捷径

==LeetCode练习题==

• 实现单链表、循环链表、双向链表，支持增删操作
• 实现单链表反转
• 实现两个有序的链表合并为一个有序链表
• 实现求链表的中间结点
• 链表中环的检测