重学数据结构(三)——使用单链表实现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;
    }

}

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

查看所有标签

猜你喜欢:

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

算法设计与分析

算法设计与分析

王红梅 / 清华大学 / 2006-7 / 23.00元

《算法设计与分析》(普通高校本科计算机专业特色教材精选)将计算机经典问题和算法设计技术很好地结合起来,系统地介绍了算法设计技术及其在经典问题中的应用。全书共12章,第1章介绍了算法的基本概念和算法分析方法,第2章从算法的观点介绍了NP完全理论,第3章~~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术,第12章基于图灵机计算模型介绍......一起来看看 《算法设计与分析》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

SHA 加密
SHA 加密

SHA 加密工具