LRU Cache | Using Doubly Linked List & Map

A normal linked list:

{
this.key
this.val
this.next
}

What Is a Doubly Linked List?

A doubly linked list is a type of data structure made up of nodes. Each node contains:

1. A value data the node holds.
2. A pointer to the next node in the sequence.
3. A pointer to the previous node in the sequence.

Unlike a singly linked list, where each node only points to the next node, a DLL allows traversal in both directions.

{
this.key
this.val
this.next
this.prev
}

Adding a node:

1. addToHead(node) will add a node at the head (most recently used).
2. removeNode(node) will remove a node from its current position.
3. removeTail will remove the least recently used node

Why Use a Doubly Linked List?

1. Efficient Insertion and Deletion:
2. You can insert or delete a node in O(1) time if you have a reference to the node.
3. No need to shift elements like in an array or traverse back like in a singly linked list.
4. Bidirectional Traversal:
5. You can move forward (next) or backward (prev) through the list.
6. This is useful for problems like LRU Cache, where you need to remove the "tail" node efficiently.
7. Maintains Order:
8. Nodes are linked in a specific sequence, making it ideal for problems requiring order maintenance (like tracking most/least recently used items).

Now adding 3, is more than what the cache could hold, so we remove the Least Recently Used: Must remove least recently used item (1:'A')

1. Remove 1:'A' (least recently used):
2. Remove from tail of list
3. Remove key 1 from HashMap
4. Add new node 3:'C':
5. Add to HashMap: key 3 points to new node
6. Add to front of list
7. Update double links

GET Operation like get(2):

1. Find node using HashMap
2. REMOVE node from its current position:

• Node's prev.next = Node's next
• Node's next.prev = Node's prev

1. ADD node to front (after head):

• Node's next = Head's next
• Node's prev = Head
• Head's next.prev = Node
• Head's next = Node

PUT Operation follows the same pattern:

1. If key exists:

• Update value
• Remove from current position
• Add to front (same as get)

1. If key doesn't exist:

• If cache is full, remove tail.prev node
• Create new node
• Add to front (same pointer operations)

class Node {
    constructor(key, val) {
        this.val = val
        this.next = null
        this.prev = null
        this.key = key
    }
}


class LRUCache {
    /**
     * @param {number} capacity
     */
    constructor(capacity) {
        this.cache = new Map()
        this.capacity = capacity
        this.head = new Node(0, 0)
        this.tail = new Node(0, 0)

        this.head.next = this.tail
        this.tail.prev = this.head
    }

    _remove(node) {
        // 0 -> lru -> 1
        node.prev.next = node.next
        node.next.prev = node.prev

    }

    _addToFront(node) {
        //head -> node -> normalNext
        node.next = this.head.next
        node.prev = this.head
        this.head.next.prev = node
        this.head.next = node

    }


    get(key) {
        /*
If the key exists, return its value & mark it as recently used.
If the key does not exist, return -1.
        */
        // we take access the current Node
        // put it next to current head
        // if key doesn't exist return -1
        if (!this.cache.has(key)) {
            return -1
        }

        const currentNode = this.cache.get(key)
        this._remove(currentNode)

        this._addToFront(currentNode)
        // now our list head's next should be this node
        return currentNode.val
    }


 

    put(key, value) {
// when we update the cahce, put the recent ones closer to head
        if (this.cache.has(key)) {
            const node = this.cache.get(key)
            node.val = value
            this._remove(node)
            this._addToFront(node)
            return
        }

        // now how do we handle the capacity
        if (this.cache.size >= this.capacity) {
            // now our list head's next should be this node
            const lru = this.tail.prev
            this._remove(lru)
            this.cache.delete(lru.key)
        }
        const newNode =new Node(key,value)
        this._addToFront(newNode)
        this.cache.set(key, newNode)
    }



}