使用循环链表实现LRU算法

C++ 写法

struct node{
    int key;
    int value;
    struct node * left;
    struct node * right;
    node(int k,int v){
        key = k;
        value = v;
        left = NULL;
        right = NULL;
    }
};

class LRUCache {
public:
    
    struct node * head;
    struct node * tail;
    int capacity = 0;
    int current_size = 0;
    
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new node(0,0);
        tail = new node(0,0);
        head -> left = tail;
        head -> right = tail;
        tail -> left = head;
        tail -> right = head;
    }
    
    int get(int key) {
        struct node * ptr = head -> right;
        while (ptr != NULL && ptr != tail) {
            if( ptr -> key == key ){
                int value = ptr->value;
                delete_node(ptr);
                ptr = new node(key,value);
                add_to_head(ptr);
                return value;
            }
            ptr = ptr -> right;
        }
        return -1;
    }
    
    void put(int key, int value) {
        struct node * ptr = head->right;
        bool exists = false;
        if( current_size > 0){
            while (ptr != NULL && ptr != tail) {
                if( ptr -> key == key ){
                    delete_node(ptr);
                    ptr = new node(key,value);
                    add_to_head(ptr);
                    exists = true;
                    break;
                }
                ptr = ptr -> right;
            }
        }
        if(!exists){
            if( current_size < capacity ){
                current_size ++;
            }else{
                delete_tail();
            }
            ptr = new node(key,value);
            add_to_head(ptr);
        }
    }
    
private:
    
    void delete_node( struct node * ptr ){
        if( ptr != NULL ){
            ptr->left->right = ptr->right;
            ptr->right->left = ptr->left;
            delete ptr;
        }
    }
    
    void delete_tail( ){
        if( tail != NULL && tail -> left != head ){
             delete_node(tail->left);
        }
    }
    
    void add_to_head( struct node * ptr ){
        ptr->right = head -> right;
        ptr->left = head;
        head -> right = ptr;
        ptr -> right -> left = ptr;
    }
    
};

Java 实现:

class LRUCache {

    Cache head = null;
    Cache tail = null;
    int currentSize = 0;
    int capacity = 0;

    public LRUCache(int capacity) {
        head = new Cache(0, 0);
        tail = new Cache(0, 0);
        head.left = tail;
        head.right = tail;
        tail.left = head;
        tail.right = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        Cache ptr = head.right;
        while (ptr != tail) {
            if (ptr.key == key) {
                ptr.delete();
                ptr.right = head.right;
                ptr.left = head;
                head.right = ptr;
                ptr.right.left = ptr;
                return ptr.value;
            }
            ptr = ptr.right;
        }
        return -1;
    }

    public void put(int key, int value) {
        boolean isFind = false;
        if (currentSize > 0) {
            Cache ptr = head.right;
            while (ptr != null && ptr != tail) {
                if (ptr.key == key) {
                    ptr.delete();
                    // Insert
                    ptr.right = head.right;
                    ptr.left = head;
                    ptr.right.left = ptr;
                    head.right = ptr;
                    // Value
                    ptr.value = value;
                    isFind = true;
                    break;
                }
                ptr = ptr.right;
            }
        }
        if (!isFind) {
            Cache cache = new Cache(key, value);
            if (currentSize >= capacity) {
                Cache deletePtr = tail.left;
                deletePtr.delete();
            } else {
                currentSize++;
            }
            Cache ptr = head.right;
            head.right = cache;
            cache.left = head;
            cache.right = ptr;
            ptr.left = cache;
        }
    }

    private class Cache {
        int key;
        int value;

        Cache left = null;
        Cache right = null;

        Cache(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
        void delete() {
            if( this.left != null ) {
                this.left.right = this.right;
            }
            if(this.right != null ) {
                this.right.left = this.left;
            }
            this.left = null;
            this.right = null;
        }
    }
}
标签: none
返回文章列表 文章二维码
本页链接的二维码
打赏二维码