Day 24 - LRU Cache

Solution.kt

// https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3309/

class LRUCache(capacity: Int) {
    var map: HashMap<Int, ListNode>
    var head: ListNode
    var tail: ListNode
    var currSize: Int
    val maxCapacity: Int
    
    init {
        this.map = HashMap<Int, ListNode>()
        this.head = ListNode(0, 0)
        this.tail = this.head
        this.currSize = 0
        this.maxCapacity = capacity
    }
    
    fun get(key: Int): Int {
        if (!map.containsKey(key)) {
            return -1
        }
        
        val node = map.get(key)
        moveToTheTop(node)
        return node!!.value
    }

    fun put(key: Int, value: Int) {
        if (map.containsKey(key)) {
            var node = map.get(key)
            node?.value = value
            moveToTheTop(node)
            return
        }
        
        if (this.currSize == this.maxCapacity) {
            removeLRUNode()
        } else {
            this.currSize += 1
        }
        
        var newNode = ListNode(key, value)
        this.map.put(key, newNode)
        addNodeAtTheTop(newNode)
    }
    
    fun moveToTheTop(node: ListNode?) {
        if (this.tail == node) {
            return
        }
        
        val nextNode = node!!.next
        val prevNode = node!!.prev
        
        if (nextNode != null) {
            nextNode.prev = prevNode    
        }
        
        prevNode?.next = nextNode
        node?.prev = this.tail
        this.tail?.next = node
        this.tail = node!!
        node?.next = null
    }
    
    fun addNodeAtTheTop(node: ListNode?) {
        node?.prev = this.tail
        this.tail?.next = node
        this.tail = node!!
    }
    
    fun removeLRUNode() {
        val nodeToRemove = this.head?.next
        if (nodeToRemove == null) {
            return
        }
        
        val nextNode = nodeToRemove?.next
    
        if (nextNode != null) {
            nextNode?.prev = this.head
        }
        
        this.head?.next = nextNode
        this.map.remove(nodeToRemove!!.key)
    }

    class ListNode(k: Int, v: Int) {
        var key: Int
        var value: Int
        var prev: ListNode?
        var next: ListNode?

        init {
            this.key = k
            this.value = v
            this.prev = null
            this.next = null
        }
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */