SDE - 1

1. If the list is empty simply return.
2. If the list is not empty, then we define two pointers curr and prev and initialize the pointer curr with the head node.
3. Traverse the circular linked list using curr to find the node to be deleted and before moving curr to the next node everytime, set prev = curr so that previous will be on one node behind current.
4. If the node is found, check if it is the only node in the circular linked list. If yes, do head = NULL.
5. If the circular linked list has more than one node, check if it is the first node of the list. To confirm this, check (curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, then set head = head.next and prev.next = head.
6. If curr is not the first node, we check if it is the last node in the list. To check this is condition (curr.next == head).
7. If curr is the last node. Do prev.next = head and delete the node curr by applying free(curr).
8. If the node to be deleted is neither the first node nor the last node, then set prev.next = temp.next.

We will use an array of type Pair<key, value> to implement our LRU Cache where the larger the index is, the more recently the key is used. Means, the 0th index denotes the least recently used pair, and the last index denotes the most recently used pair.

The key will be considered as accessed if we try to perform any operation on it. So while performing the get operation on a key, we will do a linear search, if the key found in the cache at an index id we will left shift all keys starting from id+1 in the cache by one and put the key at the end (marking it as the most recently used key in the cache). 

Similarly, while performing the put operation on a key, we will do a linear search, if the key found at index equals to id, we will shift left all keys starting from id+1 in the cache by one and put the key at the end. Otherwise, we will check the current size of the cache. If the size equals capacity, we will remove the first(0th) key from the cache by doing the left shift on all the keys by one. Now we can simply insert the key at the end.

size: denotes the current size of the cache.

capacity: denotes the maximum keys cache can hold at one time.

cache: denotes the array of type pair to store key-value pairs.

Pair: Pair type will store these values, key, value.