LRU Cache Design and Java Implementation with O(1) Operations

Recently, many internet companies have increased internship recruitment, and algorithm interview questions such as LeetCode 146 (LRU Cache) appear frequently.

Problem Description

Design and implement an LRU (Least Recently Used) cache with the following API:

LRUCache(int capacity) – initialize the cache with a positive integer capacity.

int get(int key) – return the value associated with key if it exists; otherwise return -1.

void put(int key, int value) – insert or update the key‑value pair; if the cache exceeds its capacity, evict the least recently used entry.

Both get and put must run in average O(1) time.

Solution Overview

The solution combines a HashMap for fast key lookup with a doubly linked list to maintain usage order. The linked list’s head represents the most recently used item, while the tail represents the least recently used one.

ALNode Class

An inner class representing a node of the doubly linked list, containing an integer val and pointers nextNode and preNode .

LRUCache Class

Map<Integer, Object[]> maps – stores each key together with its node and value.

ALNode head, tail – sentinel nodes that simplify insertion and deletion.

int capacity – maximum number of entries.

int length – current number of entries.

Constructor

Creates sentinel head and tail , links them, initializes the hash map and sets the capacity.

get(int key)

If the key exists, the corresponding node is moved to the front of the list to mark it as recently used, and its value is returned; otherwise -1 is returned.

put(int key, int value)

If the key already exists, its value is updated and the node is moved to the front. If the key is new and the cache is full, the node just before tail is removed from both the list and the map. The new node is then inserted right after head and the map is updated.

Reference Code

// 使用双向链表来实现
class ALNode{
    // 节点值
    public int val;
    // 当前节点的下一个节点
    public ALNode nextNode;
    // 当前节点的上一个节点
    public ALNode preNode;
    // 构造
    ALNode(int val){
        this.val = val;
    }
}

public class LRUCache {
    // 利用哈希表来存储元素
    public Map
maps;
    // 头节点（哨兵）
    public ALNode head;
    // 尾节点（哨兵）
    public ALNode tail;
    // 实际容量，意味着最多存储这么多节点
    private int capacity;
    // 当前缓存长度
    public int length;

    public LRUCache(int capacity) {
        head = new ALNode(-1);
        tail = new ALNode(-1);
        maps = new HashMap<>();
        this.capacity = capacity;
        head.nextNode = tail;
        tail.preNode = head;
    }

    public int get(int key) {
        if (maps.containsKey(key)) {
            ALNode cur = (ALNode) maps.get(key)[0];
            ALNode preNode = cur.preNode;
            ALNode nextNode = cur.nextNode;
            preNode.nextNode = nextNode;
            nextNode.preNode = preNode;
            // move cur to front
            ALNode tmp = head.nextNode;
            head.nextNode = cur;
            cur.nextNode = tmp;
            tmp.preNode = cur;
            cur.preNode = head;
            return (Integer) maps.get(key)[1];
        }
        return -1;
    }

    public void put(int key, int value) {
        if (maps.containsKey(key)) {
            ALNode cur = (ALNode) maps.get(key)[0];
            ALNode preNode = cur.preNode;
            ALNode nextNode = cur.nextNode;
            preNode.nextNode = nextNode;
            nextNode.preNode = preNode;
            // move cur to front
            ALNode tmp = head.nextNode;
            head.nextNode = cur;
            cur.nextNode = tmp;
            tmp.preNode = cur;
            cur.preNode = head;
            maps.put(key, new Object[]{cur, value});
            return;
        }
        if (length == capacity) {
            ALNode delNode = tail.preNode;
            ALNode delPreNode = delNode.preNode;
            delPreNode.nextNode = tail;
            tail.preNode = delPreNode;
            maps.remove(delNode.val);
            length--;
        }
        ALNode cur = new ALNode(key);
        ALNode tmp = head.nextNode;
        head.nextNode = cur;
        cur.nextNode = tmp;
        tmp.preNode = cur;
        cur.preNode = head;
        maps.put(key, new Object[]{cur, value});
        length++;
    }
}