import java.util.concurrent.ConcurrentHashMap

class LRUCache constructor(private val capacity: Int) {
    class DLinkedNode {
        var key: String? = null
        var value: Int = 0
        var pre: DLinkedNode? = null
        var post: DLinkedNode? = null
    }

    private val head = DLinkedNode()
    private val tail = DLinkedNode()
    private val map = ConcurrentHashMap<String, DLinkedNode>()
    private var count = 0

    init {
        head.pre = null
        head.post = tail

        tail.pre = head
        tail.post = null
    }

    fun get(key: String): Int {
        val node = map[key] ?: return -1

        moveToHead(node)

        return node.value
    }

    fun put(key: String, value: Int) {
        val node = map[key]

        if(node != null){
            node.value = value
            moveToHead(node)
            return
        }

        val newNode = DLinkedNode()
        newNode.key = key
        newNode.value = value
        addNode(newNode)

        if(++count > capacity){
            map.remove(tail.pre!!.key)
            removeNode(tail.pre!!)
            count--
        }

    }


    private fun moveToHead(node: DLinkedNode) {
        removeNode(node)
        addNode(node)
    }

    private fun addNode(node: DLinkedNode) {
        head.post!!.pre = node
        node.post = head.post

        head.post = node
        node.pre = head
    }

    private fun removeNode(node: DLinkedNode) {
        val pre = node.pre
        val post = node.post

        pre!!.post = post
        post!!.pre = pre
    }

}

参考：LRU原理和Redis实现——一个今日头条的面试题 - 知乎 (zhihu.com)