FIFO（First In,First Out）先进先出 优点：是先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单。 缺点：只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址
LFU（Least Freauently Used） 最不经常使用页置换算法，清理掉留给经常使用的使用
LRU（Least Recently Used）喜新厌旧 内存管理的一种页面置换算法，新加入的数据放到链表的头部，当缓存命中（被访问）数据移到链表的头部，当链表满的时候，将链表尾部的数据丢弃。
//单链表 public class LinkedList<T> { public LinkedList() { size = 0; } Node list; //链表有多少个节点 int size; //添加节点 //在头部添加节点 public void add(T data) { Node head = list; Node curNode = new Node(data, list); list = curNode; size++; } //在链表的index位置插入一个新数据 public void add(int index, T data) { checkPositionIndex(index); Node cur = list; Node hrad = list; for (int i = 0; i < index; i++) { hrad = cur; cur = cur.next; } Node node = new Node(data, cur); hrad.next = node; size++; } // 检查index 是否在链表范围结构 public void checkPositionIndex(int index) { if (!(index >= 0 && index <= size)) { throw new IndexOutOfBoundsException("index:" + index + ",size" + size); } } //删除节点 public T remove() { if (list != null) { Node node = list; list = list.next; //gc node.next = null; size--; return node.data; } return null; } public T remove(int index) { checkPositionIndex(index); Node cur = list; Node hrad = list; for (int i = 0; i < index; i++) { hrad = cur; cur = cur.next; } hrad.next = cur.next; //gc cur.next = null; size--; return null; } public T removeLast() { if (list != null) { Node node = list; Node cur = list; while (cur.next != null) { node = cur; cur = cur.next; } //gc node.next = null; size--; return cur.data; } return null; } //修改节点 public void updata(int index, T newData) { checkPositionIndex(index); Node head = list; for (int i = 0; i < index; i++) { head = head.next; } head.data = newData; } //查询节点 public T get() { Node node = list; if (node != null) { return node.data; } else { return null; } } public T get(int index) { checkPositionIndex(index); Node node = list; for (int i = 0; i < index; i++) { node = node.next; } return node.data; } class Node { T data; Node next; public Node(T data, Node next) { this.data = data; this.next = next; } } @Override public String toString() { Node node = list; for (int i = 0; i < size; i++) { System.out.println("" + node.data); node = node.next; } return super.toString(); } } public class LruLinhedList<T> extends LinkedList<T> { // 用于限定内存空间的大小 int memorySize; static final int DEFAULT_CAP = 6; public LruLinhedList() { this(DEFAULT_CAP); } public LruLinhedList(int memorySize) { this.memorySize = memorySize; } // LRU 添加节点 public void lruAdd(T data) { if (size >= memorySize) { removeLast(); add(data); } else { add(data); } } // 删除节点 public T lruRmove() { return removeLast(); } public T lruGet(int index) { checkPositionIndex(index); Node node = list; Node pro = list; for (int i = 0; i < index; i++) { pro = node; node = node.next; } T reData = node.data; //访问节点移开头 pro.next = node.next; Node head = list; node.next = head; list = node; return reData; } public static void main(String[] args) { LruLinhedList<String> LinkedList = new LruLinhedList<>(6); for (int i = 0; i < 6; i++) { LinkedList.lruAdd("" + i); } LinkedList.toString(); System.out.println("" + LinkedList.lruGet(4)); LinkedList.toString(); LinkedList.lruAdd(90+""); LinkedList.toString(); // LinkedList.lruGet(23); // LinkedList.toString(); } }