The is one of the greatest innovations of computer science 🔥🔥🔥. It significantly reduces work on the and provides massive performance gains in terms of speed. 😃 cache CPU It works by saving the result of computations that may be needed later. For example: say you had a service that, given a string, generated a hash. A cache could save time and resources by checking if the hash of the received string had already been generated. If it had, and was still in the cache, it would be returned without running through the hashing algorithm again. Today, we’ll be building a ( ) cache that stores a fixed amount of and ejects the last used item once the cache is full. LRU Last Recently Used strings This won’t be anything you would want to run in production. But it will clearly demonstrate the and that make this type of cache work. data structures algorithms To get and run the final results: git clone go run main.go https://github.com/Lebonesco/go_lru_cache.git Let’s jump into some code! We’ll start by defining our . These will include , , , and . Our will be a doubly linked list of pointers that are mapped to from the . This will allow for and of values. 👍 data structures Node Queue Hash Cache Queue Node Hash O(1) insertion deletion We are just caching right now, but any could replace it. Note: strings data type Next, we’ll setup our constructor functions for the and . Although, starts out empty it needs to be initialized or it will result in a later on. In addition, we create two empty for the and . This will make more sense when we move onto our and methods. Cache Queue Hash “nil pointer error” Nodes Head Tail Add() Remove() Onto the primary code of the cache. The cache has that are required to make it work: (receives the string from the user and returns the result), (adds a string to the cache), (ejects a string from the cache). three methods **Check()** **Add()** **Remove()** Inside of , if the already exists in the cache we first remove it before adding it back again so that the gets shifted to the front of the . Check() string string Queue Both and involve similar operations that reassign and pointers in the . Add() Remove() Left Right Node Queue Awesome, we now have a working cache! 🎉🎉🎉 The last step is to add a and some display methods to demonstrate our results. main() To see your code in action, run: go run main.goSTART CACHEadd: cat1 - [{cat}]add: blue2 - [{blue} <--> {cat}]add: dog3 - [{dog} <--> {blue} <--> {cat}]add: tree4 - [{tree} <--> {dog} <--> {blue} <--> {cat}]add: dragon5 - [{dragon} <--> {tree} <--> {dog} <--> {blue} <--> {cat}]add: potatoremove: cat5 - [{potato} <--> {dragon} <--> {tree} <--> {dog} <--> {blue}]add: houseremove: blue5 - [{house} <--> {potato} <--> {dragon} <--> {tree} <--> {dog}]remove: treeadd: tree5 - [{tree} <--> {house} <--> {potato} <--> {dragon} <--> {dog}]add: catremove: dog5 - [{cat} <--> {tree} <--> {house} <--> {potato} <--> {dragon}] Thank you for taking the time to read this article. If you found it helpful or interesting please let me know 👏👏👏.
