链表（上）：如何实现LRU缓存淘汰算法?

链表与数组的区别

1. 底层的存储结构上
   数组需要一块连续的内存区域来存储，如果剩余的连续内存没有达到数组的大小的话，那就不能够存储。
   链表不需要一块连续的内存区域，它通过“指针”来将一组零散的内存块串联起来使用。

   
   数组与链表的区别.jpg

单链表

我们知道链表通过“指针”来将不连续的内存空间连接起来，这每一块内存空间就叫做链表的“结点”，而每个结点除了要存储相应的数据之外，还要存储下一个结点的地址，这样才能保证结点相连接起来。我们把这个存储下一个结点的地址的指针叫做后继指针next。

单链表.jpg
如图所示，单链表中有两个特殊的结点。

• 头结点：记录链表的基地址。
• 尾节点：next指向null。

单链表的插入删除操作

单链表插入删除.jpg
如图所示，插入和删除操作只需要对后继指针进行操作即可，其时间与空间复杂度为 循环链表.jpg

其与单链表的优点在于从链尾到链头比较方便。

双向链表

顾名思义，双向链表就是既可以从前往后查询，也可以从后往前查询。因此每个节点就要多维护一个指针来保存pre。

双向链表.jpg

如图所示，双向链表支持以的方式来找到前驱节点。在一些情况下，双向链表的插入删除操作要比单链表更加简单：

1. 当我们要删除某个节点的前驱节点的时候，如果用单链表就只能重新遍历，然后找到next等于目标结点的节点，然后删除。但是如果我们使用双向链表，那么只需要使用pre就能够得到前驱节点。
2. 当我们使用的是有序链表，然后按值查询的时候，如果我们记住了上一次查询的值的大小，然后与这次查询的值进行对比，大的话则向前查询，小的话，则向后查询，这样就能够节省很多查询的时间。
   但是因为双向链表比单链表多保存了一个指向前驱结点的指针，在data不大的情况下，多占用的内存空间就很可观了，这也是双向链表的缺点。

链表VS数组性能

1. 首先说说数组的优点，因为数组是在内存中连续的存储的，所以可以借用CPU的缓存机制来预读数组的数据，使其效率更好。
2. 因为数组是支持按照下标随机访问的，可以以的时间复杂度来获取data。而链表则需要。
3. 然后说说数组的缺点，因为数组是不支持动态插入删除的，每次插入删除都需要将剩下的数组移动一次，时间复杂度为。而链表的则为。除此之外，如果使用不支持动态扩容的数组，那么在加入大量数组，超过数组所能容纳的界限之后，就会出现内存不足的情况。

如何实现LRU缓存

回到标题，如何实现LRU缓存呢。因为LRU的特性是最近最少使用的数据被删除，可想而知，这种插入删除较多的情况不能够使用数组来实现。
我们可以维护一个有序单链表来实现LRU算法，链表以使用时间为其顺序，链表头是最近最少使用的节点，删除也是从链表头开始删除。
当我们新增一个节点的时候，也相当于这个节点被使用，所以将其放到链表尾部，如果这个使用缓存已满，从头部删除一个节点。当我们使用某一个节点的时候，也将其转移到链表的尾部。
因为链表的增删都是，所以该有序单链表的时间复杂度为。

思考题

如何使用单链表实现回文字符串判断？

public class palindrome {

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        //注意次数回文length为单复数都考虑进去了，如果为单数，则fast！=null，
        // 此时slow为回文中间的数据，需要再使用其next
        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null) {
            assert prev != null;
            if (slow.val.equals(prev.val) ) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }
}

class ListNode {
    String val;
    ListNode next;

    ListNode(String val) {
        this.val = val;
    }
}

其中需要注意的点

1. 在进行节点的data数据判断的时候，不能使用==，应该使用equals函数。
2. 需要对回文为单复数长度两种情况进行考虑，单数情况下，当fast到达末尾的时候，slow处于回文正中间，此时应该向后挪一位。复数情况下，最后fast == null，此时slow处于回后半段的第一位，不需要挪动。