Class LRUCache<K, V>

A simple LRU cache implementation that uses a doubly linked list to track the order of items in an hash map.

Illustration of the design:

  oldest                                                   newest
   entry             entry             entry             entry
   ______            ______            ______            ______
  | head |.newer => |      |.newer => |      |.newer => | tail |
  |  A   |          |  B   |          |  C   |          |  D   |
  |______| <= older.|______| <= older.|______| <= older.|______|

 removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added

Items are added to the cache using the add() method. When an item is added, it's marked as the most recently used item. If the cache is full, the oldest item is removed from the cache.

Each item also tracks the item that was added before it, and the item that was added after it. This allows us to quickly remove the oldest item from the cache without having to iterate through the entire cache.

Note: This implementation is loosely based on the implementation found in the lru_map package which is licensed under the MIT license and recommends users to copy the code into their own projects.

Type Parameters

  • K

    The type of the key

  • V

    The type of the value

Constructors

constructor

Methods

add get has remove size

Constructors

constructor

  • new LRUCache<K, V>(config?: LRUCacheOptions): LRUCache<K, V>

  • A simple LRU cache implementation that uses a doubly linked list to track the order of items in an hash map.

    When instatiating the cache, you can optionally specify the type of the key and value, as well as the maximum size of the cache. If no maximum size is specified, the cache will default to a size of 100.

    Type Parameters

    • K
    • V

    Parameters

    Returns LRUCache<K, V>

    Example

    const cache = new LRUCache<string, number>({ maxSize: 100 });
    // or
    // const cache = new LRUCache();

    cache.add('a', 1);
    cache.add('b', 2);

    cache.get('a');

    console.log(cache.size()); // 2

Methods

add

  • add(key: K, value: V): void

  • Adds a new item to the cache.

    If the key already exists, it updates the value and marks the item as the most recently used. If inserting the new item would exceed the max size, the oldest item is removed from the cache.

    Parameters

    • key: K

      The key to add to the cache

    • value: V

      The value to add to the cache

    Returns void

get

  • get(key: K): undefined | V

  • Returns a value from the cache, or undefined if it's not in the cache.

    When a value is returned, it's marked as the most recently used item in the cache.

    Parameters

    • key: K

      The key to retrieve from the cache

    Returns undefined | V

has

  • has(key: K): boolean

  • Returns true if the key exists in the cache, false otherwise.

    Parameters

    • key: K

      The key to check for in the cache

    Returns boolean

remove

  • remove(key: K): void

  • Removes an item from the cache, while doing so it also reconciles the linked list.

    Parameters

    • key: K

      The key to remove from the cache

    Returns void

size

  • size(): number

  • Returns the current size of the cache.

    Returns number

Settings

Member Visibility

On This Page

Constructors
Methods