This is a simple implementation of a Least Recently Used Cache. It is a data structure that stores a fixed number of elements, and when the cache is full, the least recently used element is removed to make room for the new element.
For a true LRU cache:
- If an item already exists in the cache, it is moved to the front of the cache.
- The order of the items in the cache is from most recently used to least recently used.
- Deletion happens from the back of the cache and insertion happens from the front of the cache.
A doubly linked list is a data structure that consists of a series of nodes. Each node contains a value and a pointer to the next node in the list. The last node in the list points to null. Each node also contains a pointer to the previous node in the list. The first node in the list points to null.
A queue is a data structure that stores a list of elements in a particular order. The order is First In First Out (FIFO). The queue has two main operations: enqueue and dequeue. Enqueue adds an element to the back of the queue. Dequeue removes an element from the front of the queue.
A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.