kotlin实现LRUCache

与一般的结构不同，参考了LinkedHashMap，将经常访问的放在最后，linkedLast()
相关题目，https://leetcode.cn/problems/lru-cache/

class MyLRUCache(private val maxSize: Int) {
    class Node(
        val key: Int, var value: Int, var before: Node? = null, var after: Node? = null
    )

    private var head: Node? = null
    private var tail: Node? = null
    private val map = HashMap<Int, Node>()

    fun getAndPrintln(key: Int) = get(key).also {
        println("get ${key}, ${this}")
    }

    private fun linkLast(n: Node) {
        if (tail == null) {
            head = n
            tail = head
            return
        }
        tail!!.after = n
        n.before = tail
        tail = n
    }

    private fun removeFirst() {
        if (head == null) {
            return
        }
        head = head!!.after
        head!!.before = null
    }

    private fun linkRemove(n: Node) {
        if (n == head) {
            head = head!!.after
        }
        if (n == tail) {
            tail = tail!!.before
        }
        n.before?.after = n.after
        n.after?.before = n.before
        n.before = null
        n.after = null
    }

    fun putAndPritln(key: Int, value: Int) = put(key, value).also {
        println("put ${key},${value}, ${this}")
    }

    fun put(key: Int, value: Int) {
        // 存在
        if (key in map) {
            val n = map[key]!!
            n.value = value
            if (n == tail) {
                return
            }
            linkRemove(n)
            linkLast(n)
            return
        }
        // 新建
        val n = Node(key, value)
        map[key] = n
        linkLast(n)
        if (map.size > maxSize) {
            map -= head!!.key
            removeFirst()
        }
    }

    fun remove(key: Int): Int {
        // 不存在
        if (key !in map) {
            return -1
        }
        val n = map.remove(key)!!
        linkRemove(n)
        return n.value
    }

    fun get(key: Int): Int {
        if (key !in map) {
            return -1
        }
        val n = map[key]!!
        linkRemove(n)
        linkLast(n)
        return n.value
    }

    override fun toString() = StringBuilder().apply {
        append("[")
        var n = head
        while (n != null) {
            append(
                if (n == head) "" else ", "
            )
            append("${n.key}=${n.value}")
            n = n.after
        }
        append("]")
    }.toString()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104