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
}
}
HashMap+双向链表实现LRU (Kotlin实现)
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 转自：https://zhuanlan.zhihu.com/p/34133067?utm_source=weibo...
- 无论是应届生的春招、秋招还是社招，难以避免的一关都是要面对面试官来几个手撕算法，如果你参加过几次面试，就知道链表出...
