重学数据结构（三）——使用单链表实现LRU淘汰缓存机制

• 2020 年 7 月 23 日
• 筆記
• 数据结构

使用单链表实现LRU（Least Recently Used）淘汰缓存机制

需求：存在一个单链表，在单链表尾部的都是越早之前添加的元素。

1. 当元素被访问到时，会添加进缓存（也就是这个单链表中）。
2. 如果这个元素在之前已经被缓存到了链表中，则将这个元素从原来的位置删除，用头插法放到链表的头部。
3. 如果这个元素不在链表中，则根据链表的容量进行判断
   1. 缓存容量未满时，直接用头插法，放到链表的头部
   2. 缓存容量已满时，首先删除链表尾部的元素，再将元素进行插入到头部。

创建Node对象

package com.codezs.datastruct.mylinkedlist;

public class Node<T> {
    T data;
    Node<T> next;

    Node(Node<T> next) {
        this.next = next;
    }

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    public T getData(){
        return data;
    }
    public Node<T> getNext(){
        return next;
    }
    public void setNext(Node<T> next){this.next = next;};
    
}

对单链表实现LRU淘汰缓存机制的实现

package com.codezs.datastruct.mylinkedlist;

public class MyLinkedList<T> {

    //默认链表容量
    private final static Integer DEFAULT_CAPACITY = 10;

    //头结点
    private Node head;

    //链表长度
    private Integer length;

    //链表容量
    private Integer capacity;


    public MyLinkedList() {
        this.capacity = DEFAULT_CAPACITY;
        this.head = new Node(null);
        this.length = 0;
    }

    public MyLinkedList(Integer capacity) {
        this.capacity = capacity;
        this.head = new Node(null);
        this.length = 0;
    }

    public Node getHead(){
        return head;
    }

    //添加新的元素
    public void add(T data){
        Node<T> preNode = findPreNode(data);

        if (preNode != null){
            remove(preNode);
            insertNode(data);
        } else {
            if (length >= this.capacity){
                deleteNodeAtEnd();
            }
            insertNode(data);
        }
    }

    //获取查找到元素的前一个节点
    private Node<T> findPreNode(T data){
        Node node = head;
        while(node.getNext() != null){
            if (data.equals(node.getNext().getData())){
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    //删除node结点下一个元素
    private void remove(Node preNode){
        Node node = preNode.getNext();
        preNode.setNext(node.getNext());
        node = null;
        length--;
    }

    //头插法
    private  void insertNode(T data){
        Node node = head.getNext();
        head.setNext(new Node(data,node));
        length++;
    }

    //删除链表中最后一个元素
    private void deleteNodeAtEnd(){
        Node node = head;

        if (node.getNext() == null) {
            return;
        }

        while (node.getNext().getNext() != null) {
            node = node.getNext();
        }
        Node nextNode = node.getNext();
        node.setNext(null);
        nextNode = null;
        length--;
    }


    public boolean isEmpty(){
        return length == 0;
    }

    public int size(){
        return length;
    }

}