LRU Кеш без HashMap?

Мне нужно реализовать систему кэширования LRU в Java, в которой все операции выполняются в O(1), и все примеры в сети используют HashMap, и мы можем использовать только очереди, стеки, списки и массивы. Может кто-нибудь, пожалуйста, объясните теорию позади реализации? Я тоже не совсем понял...