再学習データ構造(三):単一チェーンテーブルを使用してLRU淘汰キャッシュメカニズムを実現する

単一チェーンテーブルを使用してLRU(Least Recently Used)淘汰キャッシュメカニズムを実現
需要:単一チェーンテーブルが存在し、単一チェーンテーブルの末尾に以前に追加された要素があります.

要素がアクセスされると、キャッシュ(つまり、この単一チェーンテーブル)に追加されます.

この要素が以前にチェーンテーブルにキャッシュされていた場合、この要素を元の位置から削除し、ヘッドプラグ法でチェーンテーブルのヘッダに配置します.

この要素がチェーンテーブルにない場合、チェーンテーブルの容量に基づいて判断する

キャッシュ容量が満たされていない場合は、直接ヘッドプラグ法でチェーンテーブルのヘッダ

に置く.

キャッシュ容量が満たされている場合は、まずチェーンテーブルの末尾の要素を削除し、要素をヘッダに挿入します.

ノードオブジェクトの作成

package com.codezs.datastruct.mylinkedlist;

public class Node {
    T data;
    Node next;

    Node(Node next) {
        this.next = next;
    }

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

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

単一チェーンテーブルに対するLRU淘汰キャッシュメカニズムの実現

package com.codezs.datastruct.mylinkedlist;

public class MyLinkedList {

    //      
    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 preNode = findPreNode(data);

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

    //             
    private Node 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;
    }

}