重學數據結構（三）——使用單鏈表實現LRU淘汰快取機制

• 2020 年 7 月 23 日
• 筆記
• 數據結構

使用單鏈表實現LRU（Least Recently Used）淘汰快取機制

需求：存在一個單鏈表，在單鏈表尾部的都是越早之前添加的元素。

1. 當元素被訪問到時，會添加進快取（也就是這個單鏈表中）。
2. 如果這個元素在之前已經被快取到了鏈表中，則將這個元素從原來的位置刪除，用頭插法放到鏈表的頭部。
3. 如果這個元素不在鏈表中，則根據鏈表的容量進行判斷
   1. 快取容量未滿時，直接用頭插法，放到鏈表的頭部
   2. 快取容量已滿時，首先刪除鏈表尾部的元素，再將元素進行插入到頭部。

創建Node對象

package com.codezs.datastruct.mylinkedlist;

public class Node<T> {
    T data;
    Node<T> next;

    Node(Node<T> next) {
        this.next = next;
    }

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    public T getData(){
        return data;
    }
    public Node<T> getNext(){
        return next;
    }
    public void setNext(Node<T> next){this.next = next;};
    
}

對單鏈表實現LRU淘汰快取機制的實現

package com.codezs.datastruct.mylinkedlist;

public class MyLinkedList<T> {

    //默認鏈表容量
    private final static Integer DEFAULT_CAPACITY = 10;

    //頭結點
    private Node head;

    //鏈表長度
    private Integer length;

    //鏈表容量
    private Integer capacity;


    public MyLinkedList() {
        this.capacity = DEFAULT_CAPACITY;
        this.head = new Node(null);
        this.length = 0;
    }

    public MyLinkedList(Integer capacity) {
        this.capacity = capacity;
        this.head = new Node(null);
        this.length = 0;
    }

    public Node getHead(){
        return head;
    }

    //添加新的元素
    public void add(T data){
        Node<T> preNode = findPreNode(data);

        if (preNode != null){
            remove(preNode);
            insertNode(data);
        } else {
            if (length >= this.capacity){
                deleteNodeAtEnd();
            }
            insertNode(data);
        }
    }

    //獲取查找到元素的前一個節點
    private Node<T> findPreNode(T data){
        Node node = head;
        while(node.getNext() != null){
            if (data.equals(node.getNext().getData())){
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    //刪除node結點下一個元素
    private void remove(Node preNode){
        Node node = preNode.getNext();
        preNode.setNext(node.getNext());
        node = null;
        length--;
    }

    //頭插法
    private  void insertNode(T data){
        Node node = head.getNext();
        head.setNext(new Node(data,node));
        length++;
    }

    //刪除鏈表中最後一個元素
    private void deleteNodeAtEnd(){
        Node node = head;

        if (node.getNext() == null) {
            return;
        }

        while (node.getNext().getNext() != null) {
            node = node.getNext();
        }
        Node nextNode = node.getNext();
        node.setNext(null);
        nextNode = null;
        length--;
    }


    public boolean isEmpty(){
        return length == 0;
    }

    public int size(){
        return length;
    }

}