# Readable efficient code with O(1) time complexity

• My solution using Dicitonary(HashTable) and Doubly Linked List with fewer lines of code requires O(1) time complexity for both set and get operations. (Implemented in C# and readable)

Lets create a wrapper class for holding the elements.

``````class Node
{
public int Key;
public int Value;
public Node(int k, int v)
{
Key = k;
Value = v;
}
}

``````

Now, lets create a dicitonary to hold the elements so that it can be used for fast loolups.
Key : Key
Value : Instance of wrapper class Node

``````Dictionary<int, LinkedListNode<Node>> map = new Dictionary<int, LinkedListNode<Node>>();

``````

Also, a Doubly Linked List to keep track of inserted elements.

``````LinkedList<Node> list = new LinkedList<Node>();
``````

Finally, count to keep count of number of elements in the list and size to store the capacity.

Set(key, value)
Case 1:
Check if the dictionary contains the key. If yes, remove that node from the linked list and insert it to the end.
Update the key in the dictionary to hold the newly inserted reference and return.

``````if(map.ContainsKey(key))
{
list.Remove(map[key]);
map[key] = list.Last;
return;
}

``````

Case 2:
If count == size
Remove the first node from the linked list and remove its entry from the dicitonary adn decrement the count.
Create a new node instance and insert it to the end of the linked list. Update the dictionary entry and increment the count.

``````if(count == size)
{
list.RemoveFirst();
count--;
}
map[key] = list.Last;
count++;
``````

Case 3:
If count < size
Create a new node instance and insert it to the end of the linked list. Add to the dictionary and increment the count.

``````        list.AddLast(new Node(key, value));
map[key] = list.Last;
count++;
``````

Get(key)
If the dictionary contains the key, remove its corressponding node from the linked list and insert it to the end.
Update its dictionary entry to point to the newly created node instance.
Else return -1

``````  if(map.ContainsKey(key))
{
int value = map[key].Value.Value;
list.Remove(map[key]);
map[key] = list.Last;
return value;
}
return -1;
``````

Final code

``````public class LRUCache {

class Node
{
public int Key;
public int Value;
public Node(int k, int v)
{
Key = k;
Value = v;
}
}

int count, size;

public LRUCache(int capacity) {
size = capacity;
}

public int Get(int key) {
if(map.ContainsKey(key))
{
int value = map[key].Value.Value;
list.Remove(map[key]);
map[key] = list.Last;
return value;
}
return -1;
}

public void Set(int key, int value) {
if(map.ContainsKey(key))
{
list.Remove(map[key]);
map[key] = list.Last;
return;
}
if(count == size)
{