重学数据结构(三)——使用单链表实现LRU淘汰缓存机制

栏目: IT技术 · 发布时间: 4年前

使用单链表实现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;
    }

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

像计算机科学家一样思考Python (第2版)

像计算机科学家一样思考Python (第2版)

[美] 艾伦 B. 唐尼 / 赵普明 / 人民邮电出版社 / 2016-7 / 49.00

本书以培养读者以计算机科学家一样的思维方式来理解Python语言编程。贯穿全书的主体是如何思考、设计、开发的方法,而具体的编程语言,只是提供了一个具体场景方便介绍的媒介。 全书共21章,详细介绍Python语言编程的方方面面。本书从基本的编程概念开始讲起,包括语言的语法和语义,而且每个编程概念都有清晰的定义,引领读者循序渐进地学习变量、表达式、语句、函数和数据结构。书中还探讨了如何处理文件和......一起来看看 《像计算机科学家一样思考Python (第2版)》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试