LRU随笔

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

package shanxi.weinan.sfproject.lru;

import java.util.Scanner;

/**
 * 基于单链表实现LRU算法
 */
public class LRUBaseSingleLinkedList<T> {

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

    /**
     * 头节点
     */
    private SingleNode<T> headNode;

    /**
     * 链表长度
     */
    private Integer length;

    /**
     * 链表容量
     */
    private Integer capacity;

    public LRUBaseSingleLinkedList() {
        this.headNode = new SingleNode<>();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    }

    public LRUBaseSingleLinkedList(Integer capacity) {
        this.headNode = new SingleNode<>();
        this.capacity = capacity;
        this.length = 0;
    }



    public void add(T data) {
        // 获取查找元素的前一个节点
        SingleNode preNode = findPreNode(data);

        // 链表中存在，删除元数据，再将数据插入到链表头
        if (preNode != null) {
            deleteElemOptim(preNode);
            insertElemAtBegin(data);
        } else {
            if (length >= this.capacity) {
                deleteElemAtEnd();
            }
            insertElemAtBegin(data);
        }

    }

    /**
     * 获取查找到元素的前一个节点
     */
    private SingleNode findPreNode(T data) {
        SingleNode node = headNode;

        while (node.getNext() != null) {
            if (data.equals(node.getNext().getElement())) {
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    /**
     * 删除preNode节点下一个元素
     */
    private void deleteElemOptim(SingleNode preNode) {

        // 要删除的目标数据
        SingleNode temp = preNode.getNext();
        preNode.setNext(temp.getNext());
        temp = null;
        length--;
    }

    private void deleteElemAtEnd() {

        SingleNode head = headNode;
        // 空链表直接返回
        if (head.getNext() == null) {
            return;
        }

        // 倒数第二个节点
        while (head.getNext().getNext() != null) {
            head = head.getNext();
        }

        SingleNode temp = head.getNext();
        head.setNext(null);
        temp = null;
        length--;
    }

    private void printAll() {
        SingleNode node = headNode.getNext();
        while (node != null) {
            System.out.print(node.getElement() + ", ");
            node = node.getNext();
        }
        System.out.println();
    }

    /**
     * 链表头部插入节点
     */
    private void insertElemAtBegin(T data) {
        SingleNode next = headNode.getNext();
        headNode.setNext(new SingleNode(data, next));
        length++;
    }

    class SingleNode<T> {
        private T element;

        private SingleNode next;

        public SingleNode(T element) {
            this.element = element;
        }

        public SingleNode(T element, SingleNode next) {
            this.element = element;
            this.next = next;
        }

        public SingleNode() {
            this.next = null;
        }

        public T getElement() {
            return element;
        }

        public void setElement(T element) {
            this.element = element;
        }

        public SingleNode getNext() {
            return next;
        }

        public void setNext(SingleNode next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LRUBaseSingleLinkedList list = new LRUBaseSingleLinkedList<>();
        Scanner sc = new Scanner(System.in);
        while (true) {
            list.add(sc.nextInt());
            list.printAll();
        }
    }
}