2021-05-09-链表（上）：如何实现LRU缓存淘汰算法

偏执的太偏执、 2023-01-19 09:53 113阅读 0赞

*  # 链表的特点 #

通过指针将一组零散的内存块串联在一起；内存块称为链表的结点；为了将所有的结点联系起来，每个链表的结点除了存储数据之外，还需要记录链上下一个结点的地址，这个记录下个结点地址的指针叫后继指针；第一个结点叫头结点，记录链表的基地址；最后一个结点叫尾结点，指向一个空地址null，代表链表的最后一个结点；

不像数组对内存要求高，数组要求内存必须是连续的，申请100M的，如果没有连续的100M内存空间就会申请失败；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70][]

*  # 单链表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1][]

*  # 循环链表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2][]

循环链表是一种特殊的单链表，尾结点指针指向头结点；

优点是链表尾到链表头比较方便，适合处理具有循环结构特点的数据；

约瑟夫问题；

*  # 双向链表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3][]

单链表只有一个方向，结点只有一个后继指针指向后面的结点；

双向链表支持两个方向，每个结点不止一个后继结点next指向后面的结点，还有一个前驱节点prev指向前面的结点；

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址；

双向链表在删除指定位置结点的时候，更加高效，因为双向链表的结点已经存储了前驱结点的指针，不需要像单链表那样需要遍历；

除了删除，一个有序链表，在查找时，双向链表的按值查询也比单链表更加高效；

Java的LinkedHashMap就用到了双向链表这个结构；

利用空间换时间；

*  # 双向循环链表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4][]

双向链表+循环链表

*  # 链表vs数组性能 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 5][]

数组：代码对内存的使用非常苛刻；

*  # 如何实现lru缓存淘汰算法 #

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的；

当有一个新的数据被访问时，从链表头部开始遍历：

1、如果此数据已经被缓存到链表中，我们遍历等到这个数据对应的结点，并将其从原来的位置删除，插入到链表的头部；

2、如果数据没有被缓存到链表中：

2.1、如果链表数据已满，就需要删除链表尾部的结点，将心的数据插入到链表的尾部；

2.2、如果链表数据未满，则将此结点插入链表的尾部；

*  # 如何判断一个字符串是回文字符串，如果这个字符串是链表存储的，时间空间复杂度如何 #

利用快慢指针的方法；

快指针每次前进两个单位，慢指针每次前进一个单位并修改其后继指针指向前一个结点；

当fast指针走完（空结点或者空结点的前一个结点），慢指针刚好走到中间结点；此时慢指针继续向前走，同时开启一个新指针向后走，判断链表结点前后是否相等；

public class ListNode{
       int val;
       ListNode next;
       ListNode(int x){
          val=x;
       }
    }
    
    class solution{
       public boolean isPalindrome(ListNode head){
          if(head == null || head.next==null){
            return true;
          }
          ListNode prev=null;
          ListNode fast=head;
          ListNode slow=head;
          
          while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            ListNode slowNext=slow.next;
            slow.next=prev;
            prev=slow;
            slow=slowNext;
          }
    
          if(fast!=null){
          // 当链表结点个数为奇数，慢结点需要往前走一个结点
             slow=slow.next;
          }
    
          while(prev!=null){
             if(slow.val!=prev.val){
               return false;
             }
             slow=slow.next;
             prev=prev.next;
    
          }
       }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70]: /images/20221021/a04b8908fcc142e8ad51001f81a861af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1]: /images/20221021/a6de093ae937460088692c30c76eba60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2]: /images/20221021/ebf185fe5cee4a96b41dbc82cdf41ed3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3]: /images/20221021/d7444be2fa844f7f960f7b0c7ebf1b92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4]: /images/20221021/81734cfd9ee24834bb1ee37d424775f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 5]: /images/20221021/4a4705a67a3944d5be2c4bdc3f12245f.png