使用单链表实现LRU缓存

 1/**
 2 * 使用单链表实现一个LRU（Least Recent Use）缓存
 3 *
 4 * @author wangy
 5 * @version 1.0
 6 * @date 2021/6/23 / 16:11
 7 */
 8public class ListLRU {
 9
10    private static final int CAPACITY = 10;
11
12    private static final NodeList<Integer> LIST = new NodeList<>();
13
14    /**
15     * 使用缓存
16     * <p>
17     * 平均时间复杂度：O(n^2)
18     * </p>
19     *
20     * @param s element to cache
21     */
22    static void cache(Integer s) {
23        // check whether s is cached
24        int index;
25        if ((index = LIST.getIndex(s)) != -1) {
26            // 将元素移动到队首
27            LIST.remove(index);
28        } else {
29            // check size
30            if (LIST.size() >= CAPACITY) {
31                // full, remove tail and then insert s to head
32                LIST.remove(CAPACITY-1);
33            }
34        }
35        LIST.insertHead(s);
36    }
37
38    public static void main(String[] args) {
39        for (int i = 0; i < 9 ; i++) {
40            ListLRU.cache(i);
41        }
42        ListLRU.LIST.printAll();
43        ListLRU.cache(9);
44        ListLRU.LIST.printAll();
45        ListLRU.cache(0);
46        ListLRU.LIST.printAll();
47        ListLRU.cache(99);
48        ListLRU.LIST.printAll();
49    }
50}