链表

链表将一串零散的内存连接在一起，是天然的动态结构。

链表的两个元素：节点和指针。

节点用于存储具体的数据，指针用于指向节点

指针分为后继指针next和前驱指针prev，next指向下一个节点，prev指向前一个节点

根据指针的指向特点，链表分为：单链表，循环链表，双向链表，双向循环链表

单链表必：包含节点和next，头结点记录链表的基地址，next指向下一个节点，尾节点的next指向NULL

循环链表：单链表的尾节点不再指向NULL，而是指向头结点

双向链表：每个节点具备prev和next两个指针，prev指向前一个节点，next指向后一个节点，头结点prev和尾结点的next指向NULL

双向循环链表：双向链表的头结点prev执行尾结点，尾结点的next指向头节点

使用链表实现LRU算法

常用的缓存淘汰算法包括：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

单链表中前面表示最近使用，后面表示最近未使用。

查询一个元素，如果查到了，则将该元素移动至头部

如果没查到：

• 如果空间足够，则添加元素至头部
• 如果空间不够，则删除尾部节点，再添加元素至头部

public class LRU {
  private LinkedList<Integer> linkedList= new LinkedList<>();

  public LinkedList<Integer> get(Integer e) {
    if (linkedList.contains(e)) {
      linkedList.remove(e);
      linkedList.addFirst(e);
      return linkedList;
    } else if (linkedList.size() >= 5) {
      linkedList.removeLast();
    }
    linkedList.addFirst(e);
    return linkedList;
  }

  public static void main(String[] args) {
    LRU lru = new LRU();
    for (int i = 0; i < 5; i++) {
      System.out.println(lru.get(i));
    }
    for (int i = 0; i < 5; i++) {
      System.out.println(lru.get(i));
    }
  }
}