LRU Cache: An Introduction and Implementation in Go

LRUCache: An implementation in Go

Introduction: An LRUCache is a data structure that uses the scheme of evicting the Least Recently Used item. Basically a cache is a mechanism used by software to effectively handle data access and reading in an efficient manner. Caching improves performances by recently used or frequently used in memory. Using a cache, we avoid the overhead required to fetch an item that is already in memory. LRU (Least Recently Used) is one cache mechanism where we evict an item that is not used to make rooms for new items to be added. Some other popular caching mechanisms are MRU, LFU, etc.

Access: O(1)

Get: O(1)

Space Complexity: O(N)

Use Cases: An LRUCache is the default implementation used by the Android and iOS client for Dropbox and the Linux Client uses something called segmented LRU.

Implementation: An LRU Cache is often implemented by using two data structures, hence the space complexity. The popular ones are using a Doubly Linked list and a HashMap.

Here is an implementation in Go.




Imagination is more important than knowledge — Einstein

Love podcasts or audiobooks? Learn on the go with our new app.

Updating Magento 2 development dependencies


Azure analytics (Application insights)

Rules-as-Code: Encoding Rules in a Government Context — Part 1

How a Shell Works

Questions & Concerns: A use case study on GraphQL

Automated Reader — Reading Printed Text Out Loud

More than a line, enemy movement in Unity

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aadit Kapoor

Aadit Kapoor

Imagination is more important than knowledge — Einstein

More from Medium

In Golang Passing a Context To Function Performing I/O Can Save From DDOS Attack.

Golang with Leetcode: Letter Combinations of a Phone Number

Golang way of working with resources (For Java devs)

Part 2: Grpc Proto Code Generation Using Protoc for Message and Services