java - 手写LRU(使用链表，时间复杂度O(n))

最简单的LRU实现，底层存储采用链表结构，时间复杂度为O(n) 代码如下:

代码语言：javascript复制

package com.jfp;

/**
 * @author jiafupeng
 * @desc
 * @create 2021/3/12 15:58
 * @update 2021/3/12 15:58
 **/
public class Test {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        lruCache.put(6,6);

        System.out.println(lruCache);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(4));
        System.out.println(lruCache);
    }


    public static class LRUCache{

        /**
         * 长度
         */
        private int size;

        /**
         * 最大容量
         */
        private int capacity;

        /**
         * 链表头
         */
        private NodeList headNodeList;

        /**
         * 链表尾
         */
        private NodeList tailNodeList;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
        }

        private static class NodeList{
            private Integer key;
            private Integer value;
            private NodeList pre;
            private NodeList next;

            public NodeList(Integer key, Integer value, NodeList pre, NodeList next) {
                this.key = key;
                this.value = value;
                this.pre = pre;
                this.next = next;
            }
        }

        public void put(int key, int val){
            NodeList getNodeList = getNodeList(key);
            if(getNodeList != null){
                getNodeList.value = val;
                return;
            }

            if(headNodeList == null){
                init(key, val);

            } else {
                tailNodeList.next = new NodeList(key, val, tailNodeList, null);
                tailNodeList = tailNodeList.next;
                size  ;
            }

            if(size > capacity){
                removeHead();
            }
        }

        public Integer get(int key){
            NodeList getNodeList = getNodeList(key);
            return getNodeList == null ? null : getNodeList.value;
        }

        @Override
        public String toString(){
            NodeList nodeList = headNodeList;
            String str = "";
            while (nodeList != null){
                str  = ("["   nodeList.key   ":"   nodeList.value   "]=>");
                nodeList = nodeList.next;
            }

            return str   "null";
        }

        private void removeHead(){
            headNodeList = headNodeList.next;
        }

        private void init(int key, int value){
            headNodeList = new NodeList(key, value, null,null);
            tailNodeList = headNodeList;
            size  ;
        }

        private NodeList getNodeList(int key){
            NodeList tmpNodeList = headNodeList;
            while(tmpNodeList != null){
                if(tmpNodeList.key == key){
                    // 换位置
                    moveToTail(tmpNodeList);
                    return tmpNodeList;
                }

                tmpNodeList = tmpNodeList.next;
            }

            return null;
        }

        private void moveToTail(NodeList nodeList){
            if(nodeList == tailNodeList){
                return;
            }

            if(nodeList == headNodeList){
                headNodeList = nodeList.next;
            }

            NodeList pre = nodeList.pre;
            NodeList next = nodeList.next;
            if(pre != null){
                pre.next = next;
            }

            if(next != null){
                next.pre = pre;
            }

            tailNodeList.next = nodeList;
            nodeList.pre = tailNodeList;
            nodeList.next = null;
            tailNodeList = nodeList;
        }
    }
}

输出

代码语言：javascript复制

[2:2]=>[3:3]=>[4:4]=>[5:5]=>[6:6]=>null
null
4
[2:2]=>[3:3]=>[5:5]=>[6:6]=>[4:4]=>null

存储 链表

0 人点赞