```
type cacheVal struct {
value int
younger, older int // These are the keys of the next younger, next older entries in the map, -1 if none
}
type LRUCache struct {
m map[int]*cacheVal
youngest, oldest, capacity int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
m: make(map[int]*cacheVal),
capacity: capacity,
youngest: -1,
oldest: -1,
}
}
func (this *LRUCache) Get(key int) int {
if c, ok := this.m[key]; ok {
if this.youngest != key { // If this is not the youngest entry, move it to be the youngest
this.m[this.youngest].younger = key // Current youngest now points to key as the youngest
if c.older != -1 { // If we have an older key in the current position of the get node
this.m[c.older].younger = c.younger // link the next older node to the get-node's younger
} else if c.younger != -1 { // If the get-node is the current oldest, and we aren't adding a new value in Put
this.oldest = c.younger // The new oldest is the get-node's younger sibling
}
if c.younger != -1 { // If we have a younger node (always true, except on a new put)
this.m[c.younger].older = c.older // Set the younger's older sibling to be the get-node's older sibiling
}
c.younger = -1 // The get-node is now the youngest
c.older = this.youngest // The get-node's older sibling is the previous youngest
this.youngest = key // The global youngest is the get-node
}
return c.value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if len(this.m) == 0 { // This happens just once, on a new map
this.youngest, this.oldest = key, key
}
if this.Get(key) == -1 { // If the value doesn't exist (side-effect: move the put-node to the front of the LRU if it does exist)
this.m[key] = &cacheVal{ // Add a brand new value
value: value,
younger: -1,
older: -1,
}
this.Get(key) // Use get to place it at the front of the LRU linked list
} else {
this.m[key].value = value // update the value
}
if len(this.m) > this.capacity { // Check for over-capacity and remove
c := this.m[this.oldest] // Get the oldest node
this.m[c.younger].older = -1 // The younger node is now the oldest, so clear the older key
oldOldest := this.oldest
this.oldest = c.younger // The younger sibling is now the oldest globally
delete(this.m, oldOldest) // delete the oldest node from the map
}
}
```