Why the LRUCache implementation is using Array over the Doubly Linked List with Map?

[kuldeepsingh-d11]

Why the LRUCache implementation is using Array over the Doubly Linked List with Map?

[EskiMojo14]

fwiw if it's not possible to replicate the existing behaviour with a linked list, I'm sure we'd be open to a new memoiser instead

[markerikson]

Reworking this isn't a priority right now, but if you'd like to submit that as a PR we can take a look.

Note that one issue with your implementation is that it uses a Map and expects a single key, whereas our LRU implementation has an entire set of arguments and does equality checks on that.

[kuldeepsinghborana]

@markerikson
The LRU implementation with a doubly linked list and hashmap can not be achieved,
As the library provides a custom equality check comparator, hashmap works with an exact value match (reference/value).

I tried but 2 tests are failing because of it.
#701

@markerikson @aryaemami59, Do you have any idea, if we can achieve this?

[kuldeepsinghborana]

@aryaemami59 I am trying to modify the existing implementation

[aryaemami59]

@kuldeepsinghborana Ok I'll take a look.

[markerikson]

Because it was copied from another package, relatively simple code, and relatively small bundle size.

[kuldeepsingh-d11]

but the Doubly linked List code is not very large, and it is also simple code

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.head = { key: null, value: null, prev: null, next: null };
        this.tail = { key: null, value: null, prev: this.head, next: null };
        this.head.next = this.tail;
    }
    get(key) {
        if (!this.cache.has(key)) return -1;

        const node = this.cache.get(key);
        this.moveToHead(node);
        return node.value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.value = value;
            this.moveToHead(node);
        } else {
            const newNode = { key, value, prev: this.head, next: this.head.next };
            this.head.next.prev = newNode;
            this.head.next = newNode;
            this.cache.set(key, newNode);

            if (this.cache.size > this.capacity) {
                const tailKey = this.removeTail();
                this.cache.delete(tailKey);
            }
        }
    }

    moveToHead(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }

    removeTail() {
        const key = this.tail.prev.key;
        this.tail.prev.prev.next = this.tail;
        this.tail.prev = this.tail.prev.prev;
        return key;
    }
}

[aryaemami59]

@kuldeepsinghborana I can take a look, just out of curiosity are you trying to modify the exisiting implementation for lruMemoize or are you trying to create a new standalone mamoize function?