Introduction

A cache LRU (Least Recently Used) is similar to a dictionary. It stores data associated to a key. The difference between a dictionary and a Cache is that the latter has a limited capacity. Every time we reach the capacity, the Cache deletes the least recently used element.

In this article, we are going to see how to implement a Cache LRU with Swift.

Happy Reading!

Contents

Getting Started

First of all, we must understand what data structures we should use to implement our Cache LRU. There are different ways to implement it. In this version, we will use:

  • Doubly Linked List: This is the core of our implementation. We need this list to store the elements of our cache. We don’t use an Array because it would be slower. The Cache LRU policy is to move the elements recently used in the head very often. If we move an element in the head—at the index 0—in an array, we should perform a shift to right for all the other elements.
  • Dictionary<Key, ListNode>: The problem of using a doubly linked list is that its lookup complexity is O(n). We can solve this bottleneck using a dictionary—which has a lookup complexity of O(1). We’ll use this dictionary to store the nodes of our list.

In the next section, we are going to see how to implement the doubly linked list. If you already know it, feel free to jump at the section Cache LRU.

Doubly Linked List

For this article, we don’t need a complete doubly linked list implementation. For this reason, we’ll implement only the methods used in the Cache.

The first step is to create a new class DoublyLinkedList which accepts a generic value T to store inside the nodes:

Then, we must create a class for the nodes:

In this implementation, we use a nested Node class. If you use a Swift version older than 3.1, you must create this class outside DoublyLinkedList. Nested classes with generic values are supported from Swift 3.1.

Then, we must provide the information of how many elements are stored in the list:

The operations on a linked list may be sometimes complex to implement. For this reason, we can store the first and last elements to keep our life easier:

Now, we can start implementing the list methods:

addHead

We need a method to add a new element in the list. We add it in the head to be compliant with the Cache LRU policy—a new element is the recently used:

moveToHead

The concept of a Cache LRU is keeping the recently element used at the beginning of our list. For this reason, we need a method to move a node at the head:

removeLast

When our Cache is full, we need a method to remove the last element—which is the least recently used:

  1. The value of this tail is not the same of self.tail. It’s the value of the old tail which comes from the optional binding in the guard at the beginning of this method.

Finally, we can add a typealias for our Node type to use in the Cache implementation:

The final version of our list implementation should be like this:

Cache LRU

It’s time to implement our Cache. We can start creating a new CacheLRU class:

The generic value Key must be Hashable since it’s the key of the value stored in the doubly linked list.

A Cache stores data associated to keys like a dictionary. Unfortunately, our doubly linked list accepts only a value payload and not also a key. To solve this problem, we can create a struct which wraps the value and its key. In this way, our list nodes will store the object CachePayload which contains both value and key:

Then, we should add the two data structures—a doubly linked list and a dictionary:

As we saw in Introduction, Cache LRU has a limited capacity. We can inject this capacity in the init method and store it in a private property:

We use the method max to avoid invalid capacity values less than zero.

Now, we can implement the two Cache methods to get and set the elements:

setValue

With the method set, we can add/update an element for a specific key. The value is always moved at the beginning of the list as recently used element:

  1. Create a payload object to wrap key and value to be stored in the list.
  2. If the list already stores an element for that specific key, we update the value and move it at the beginning of the list. Otherwise, we create a new node and add it as head of the list.
  3. If we exceeded the capacity of the cache adding the new element, we remove the last element of the list.

getValue

With the method get, we can retrieve an element for a specific key. Every time we retrieve an element, it is moved at the beginning of the list as recently used element:

The final version of our Cache implementation should be this:

We can use this cache like this:

You can find a Gist with the Cache LRU implementation here.

Conclusion

That’s all for our Cache LRU.

Nowadays, we have a lot of memory available for our Apps. Despite this, we may need a Cache with a limited capacity to save memory space. For example, when we have to cache objects which are space-consuming like the images.

Update:

I’ve figured out that Array is faster than linked list. Since the pure version of Cache LRU uses a doubly linked list, I leave the current implementation. But, keep in mind that with a Swift Array we would have a faster implementation.

You can watch an interesting video about Array and linked list here:

Reference Links