前言

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

要求：你是否可以在 O(1) 时间复杂度内完成这两种操作？

LRUCache是最近最少使用缓存，具体概念不了解的可以自行百度，本篇是java代码的实现

提示：难点在于O(1) 时间复杂度，思路就是Hash表加双向链表，所以基本功一定要扎实。
要熟练掌握双向链表的头插和尾插，删除末尾和头部元素，删除某个节点

一、双向链表基础代码

示例：先来看头插法的

package algorithm.list;

public class DoubleLinkList {		// 双向链表

	private DNode head;		//头 
	private DNode tail;		// 尾
	
	DoubleLinkList(){
		head = null;
		tail = null;
	}
	
	public void inserHead(int data){
		DNode newNode = new DNode(data);
		if(head == null){
			tail = newNode;
		}else{
			head.pre = newNode;
			newNode.next = head;
		}
		head = newNode;
	}
	public void deleteHead(){
		if(head == null) return ;		//没有数据
		if(head.next == null){		//就一个点
			tail = null;
		}else{
			head.next.pre = null;	
		}
		head = head.next;
	}
	public void deleteKey(int data){
		DNode current = head;
		while (current.value != data) {
			if (current.next == null) {
				System.out.println("没找到节点");
				return ;
			}
			current = current.next;
		}
		if (current == head) {// 指向下个就表示删除第一个
			deleteHead();
		} else {
			current.pre.next = current.next;
			if(current == tail){		//删除的是尾部
				tail = current.pre;
				current.pre = null;
			}else{
				current.next.pre = current.pre;
			}
		}
	}
}

class DNode{
	
	int value;		//值
	DNode next;		//下一个的指针
	DNode pre;		//指向的是前一个指针

	DNode(int value){
		this.value = value;
		this.next = null;
		this.pre = null;
	}
}

尾插法的也简单。本篇的LruCache采用的头插法。尾插法属于基本功，我在文末会补上

二、LRU实现

代码如下（示例）：

定义一个双向链表

package algorithm.cache;

/**
 * 存储数据
 * 1.正常情况
 * 2.重复的key
 * 3.链表容量满了
 */
public class DoubleLinkList {		// 双向链表

	public Node head;		//头
	public Node tail;		// 尾
	public int size;
	DoubleLinkList(){
		this.head = null;
		this.tail = null;
	}
	
	public Node inserHead(int key,int data){
		Node newNode = new Node(key,data);
		if(head == null){
			tail = newNode;
		}else{
			head.pre = newNode;
			newNode.next = head;
		}
		head = newNode;
		size++;
		return newNode;
	}

	/**
	 * 容量满了删除最后一个元素
	 * 返回删除的元素，去hash表里重写维护关系。
	 */
	public Node removeLast(){
		if(tail==null){
			return null;
		}else if(tail.pre==null){
			head=null;
		}else{
			tail.pre.next=null;
		}
		Node temp=tail;
		tail=tail.pre;
		tail.next=null;
		size--;
		return temp;
	}

	public int size(){
		return size;
	}
	/**
	 * 删除保证时间复杂度O(1)，我需要知道删除哪个
	 * 要通过hash知道他的前驱和后继节点
	 */
	public void remove(Node node){
		if(node.pre==null){
			node=null;
		}
		node.pre.next=node.next;
		node.next.pre = node.pre;
		size--;
	}
}

class Node{
	int key,value;		//值
	Node next;		//下一个的指针
	Node pre;		//指向的是前一个指针

	Node(int key,int value){
		this.key=key;
		this.value = value;
		this.next = null;
		this.pre = null;
	}
}

LRUCache代码

package algorithm.cache;

import java.util.HashMap;


public class LruCache {
    public int capacity;
    public DoubleLinkList list;
    public HashMap<Integer,Node> map;

    public LruCache(int cap) {
        this.capacity=cap;
        list=new DoubleLinkList();
        map=new HashMap<>();
    }

    /**
     * 先改存储，再改映射关系
     * 1.如果没有
     * 2.有
     * @param key
     * @return
     */
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        //两步操作，得到value,提到链表头部
        int res = map.get(key).value;
        put(key,res);
        return res;
    }

    /**
     * 1.如果存在
     * @param key
     * @param val
     */
    public void put(int key,int val){
        Node node=new Node(key,val);
        if(map.containsKey(key)){
            list.remove(map.get(key));
            Node temp=list.inserHead(key,val);
            map.put(key,temp);
        }else{
            if(capacity==list.size){
                Node last = this.list.removeLast();
                map.remove(last.key);
            }
            Node temp=this.list.inserHead(key,val);
            map.put(key,temp);
        }
    }

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

        lc.get(2);
        lc.get(3);
        lc.put(6,6);
        DoubleLinkList list = lc.list;
        Node head = list.head;
        while (head!=null){
            System.out.println(head.key+"  "+head.value);
            head=head.next;
        }
    }
}

总结

随着写代码越来越多，越是发现数据结构与算法这门内功是很有必要的，这里补充下尾插法的双向链表

package algorithm.list;

public class DoubleLinkListTailInsert {
    private Node head;
    private Node tail;

    public DoubleLinkListTailInsert() {
        this.head = null;
        this.tail = null;
    }

    //一定要心中有图,尾部插入
    public void addLast(int data){
        Node node=new Node(data);
        //插入尾部。先固定个头节点
        if(tail==null){
            head=node;
        }else{
            tail.next=node;
            node.prev=tail;
        }
        tail=node;
    }
    public void removeLast(){
        if(tail==null){
            new Exception("无此元素");
        }else if(tail.prev==null){//就一个元素
            head=null;
        }else{ //断掉尾节点的前面的后继指针
            tail.prev.next=null;
        }
        //尾指针向前移
        tail=tail.prev;
    }

    public Node deleteNode(int data){
        //遍历
        Node current=tail;
        while (current.data!=data){
            if(current.prev==null){
                System.out.println("无此元素");
                return null;
            }
            current=current.prev;
        }
        //找到后进行删除，当前节点是尾节点，直接调用removeLast
        if(current==tail){
            removeLast();
        }else{
            current.prev.next = current.next;
            if(current==head){
                head=current.next;
                current.next=null;
            }else{
                current.next.prev=current.prev;
            }
        }
        return new Node(data);
    }

    public static void main(String[] args) {
        DoubleLinkListTailInsert dl=new DoubleLinkListTailInsert();
        dl.addLast(1);
        dl.addLast(2);
        dl.addLast(3);
        dl.deleteNode(2);
        dl.addLast(2);
    }
}

class Node{
    public int data;
    public Node prev;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}