单链表实现LRU缓存淘汰算法

public class LRUBasedArray<T> {
    private final int DEFAUL_CAPACITY = 10;
    private Integer capacity;
    private Integer count;
    private T[] value;
    /**
     * 用于元素记录所在数组位置
     */
    private Map<T, Integer> holder;

    public LRUBasedArray() {
        this.capacity = this.DEFAUL_CAPACITY;
        this.value = (T[]) new Object[capacity];
        this.count = 0;
        this.holder = new HashMap<T, Integer>(capacity);
    }

    public LRUBasedArray(Integer capacity) {
        this.capacity = capacity;
        this.value = (T[]) new Object[capacity];
        this.count = 0;
        this.holder = new HashMap<T, Integer>(capacity);
    }

    /**
     * 缓存数据
     * @param data
     */
    public void add(T data){
        if (data == null){
            throw new IllegalArgumentException("该缓存容器不支持null!");
        }
        Integer index = holder.get(data);
        if (index != null){
            // 向右移动
            update(index);
        }else {
            // 是否已满
            if (isFull()){
                // 删除，更新
                removeAndCache(data);
            }else {
                // 右移元素更新
                cache(data, count);
            }
        }
    }

    /**
     * 数据之前已在数组中，将数组中的对应数据更新到数组开始。
     * @param index
     */
    private void update(Integer index){
        T key = value[index];
        rightOffer(index);
        value[0] = key;
        holder.put(key,0);
    }

    /**
     * 向数组插入新数据
     * @param data
     * @param end
     */
    private void cache(T data, Integer end){
        rightOffer(end);
        value[0] = data;
        holder.put(data,0);
        count++;
    }

    /**
     * 删数组最后一位，并将新数据保存到数组开始
     * @param data
     */
    private void removeAndCache(T data){
        T key = value[--count];
        holder.remove(key);
        cache(data, count);
    }


    /**
     * index左侧的统一向右移动一位
     * @param index
     */
    private void rightOffer(Integer index){
        for (int i=index;i>0;i--){
            value[i] = value[i-1];
            holder.put(value[i],i);
        }
    }

    /**
     * 判断数组是否已满
     * @return
     */
    private boolean isFull(){
        return count == capacity;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
            sb.append(value[i]);
            sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUBasedArray<Integer> array = new LRUBasedArray();
        Random random = new Random(20);
        int num = 0;
        for (int i=0;i<20;i++){
            num = random.nextInt(20);
            array.add(num);
            PrintUtill.println("插入"+ num + ":");
            PrintUtill.println(array.toString());
        }
    }

}

public class LRUBaseLinkedList<T> {
    /**
     * 默认容量
     */
    private final int DEFAUL_CAPACITY = 10;

    /**
     * 头结点
     */
    private SNode<T> head;
    /**
     * 链表长度
     */
    private Integer length;
    /**
     * 链表容量
     */
    private Integer capacipy;

    public LRUBaseLinkedList() {
        this.head = new SNode<>();
        this.length = 0;
        this.capacipy = DEFAUL_CAPACITY;
    }

    public LRUBaseLinkedList(Integer capacipy) {
        this.head = new SNode<>();
        this.length = 0;
        this.capacipy = capacipy;
    }

    /**
     *  缓存数据
     * @param data
     */
    public void add(T data){
        SNode preNode = findPreNode(data);
        if (preNode != null){
            // 删除节点
            deleteElemOptim(preNode);
        }else {
            // 节点不存在，队列是否已满
            if (length>=capacipy){
                // 已满，删除队尾
                deleteElemAtEnd();
            }
        }
        // 将节点插入到头
        intsertElemAtBegin(data);
    }

    /**
     * 删除某个结点
     * @param node
     */
    public void deleteElemOptim(SNode node){
        node.setNext(node.getNext().getNext());
        length--;
    }

    /**
     * 删除链表尾部的结点
     */
    public void deleteElemAtEnd(){
        SNode node = head;

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

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

    }

    /**
     * 在头部插入结点
     * @param data
     */
    public void intsertElemAtBegin(T data){
        SNode node = new SNode(data, head.getNext());
        head.setNext(node);
        length++;
    }



    /**
     * 获取查找到元素的前一个节点
     * @param data
     * @return
     */
    private SNode findPreNode(T data){
       SNode node = head;
       while (node.getNext() != null){
           if (node.getNext().element.equals(data)){
               return node;
           }
           node = node.getNext();
       }
       return null;
    }

    private void printAll(){
        SNode node = head.getNext();
        while (node!=null){
            PrintUtill.print(node.element+">");
            node = node.getNext();
        }
        PrintUtill.printlnRule();

    }



    public class SNode<T> {
        private T element;
        private SNode next;

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

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

        public T getElement() {
            return element;
        }

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

        public SNode getNext() {
            return next;
        }

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


    public static void main(String[] args) {
        LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<Integer>();
        Random random = new Random(20);
        int num = 0;
        for (int i=0;i<20;i++){
            num = random.nextInt(20);
            list.add(num);
            PrintUtill.println("插入"+ num + ":");
            list.printAll();
        }

    }
}